Articles

2.5: Stars and Bars - Mathematics

2.5: Stars and Bars - Mathematics


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Investigate!

Suppose you have some number of identical Rubik's cubes to distribute to your friends. Imagine you start with a single row of the cubes.

  1. Find the number of different ways you can distribute the cubes provided:
    1. You have 3 cubes to give to 2 people.
    2. You have 4 cubes to give to 2 people.
    3. You have 5 cubes to give to 2 people.
    4. You have 3 cubes to give to 3 people.
    5. You have 4 cubes to give to 3 people.
    6. You have 5 cubes to give to 3 people.
  2. Make a conjecture about how many different ways you could distribute 7 cubes to 4 people. Explain.
  3. What if each person were required to get at least one cube? How would your answers change?

Consider the following counting problem:

You have 7 cookies to give to 4 kids. How many ways can you do this?

Take a moment to think about how you might solve this problem. You may assume that it is acceptable to give a kid no cookies. Also, the cookies are all identical and the order in which you give out the cookies does not matter.

Before solving the problem, here is a wrong answer: You might guess that the answer should be (4^7) because for each of the 7 cookies, there are 4 choices of kids to which you can give the cookie. This is reasonable, but wrong. To see why, consider a few possible outcomes: we could assign the first six cookies to kid A, and the seventh cookie to kid B. Another outcome would assign the first cookie to kid B and the six remaining cookies to kid A. Both outcomes are included in the (4^7) answer. But for our counting problem, both outcomes are really the same – kid A gets six cookies and kid B gets one cookie.

What do outcomes actually look like? How can we represent them? One approach would be to write an outcome as a string of four numbers like this:

egin{equation*} 3112, end{equation*}

which represent the outcome in which the first kid gets 3 cookies, the second and third kid each get 1 cookie, and the fourth kid gets 2 cookies. Represented this way, the order in which the numbers occur matters. 1312 is a different outcome, because the first kid gets a one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But the answer is not (7^4 ext{.}) We need the sum of the numbers to be 7.

Another way we might represent outcomes is to write a string of seven letters:

egin{equation*} mbox{ABAADCD} , end{equation*}

which represents that the first cookie goes to kid A, the second cookie goes to kid B, the third and fourth cookies go to kid A, and so on. In fact, this outcome is identical to the previous one—A gets 3 cookies, B and C get 1 each and D gets 2. Each of the seven letters in the string can be any of the 4 possible letters (one for each kid), but the number of such strings is not (4^7 ext{,}) because here order does not matter. In fact, another way to write the same outcome is

egin{equation*} mbox{AAABCDD} . end{equation*}

This will be the preferred representation of the outcome. Since we can write the letters in any order, we might as well write them in alphabetical order for the purposes of counting. So we will write all the A's first, then all the B's, and so on.

Now think about how you could specify such an outcome. All we really need to do is say when to switch from one letter to the next. In terms of cookies, we need to say after how many cookies do we stop giving cookies to the first kid and start giving cookies to the second kid. And then after how many do we switch to the third kid? And after how many do we switch to the fourth? So yet another way to represent an outcome is like this:

egin{equation*} ***|*|*|** end{equation*}

Three cookies go to the first kid, then we switch and give one cookie to the second kid, then switch, one to the third kid, switch, two to the fourth kid. Notice that we need 7 stars and 3 bars – one star for each cookie, and one bar for each switch between kids, so one fewer bars than there are kids (we don't need to switch after the last kid – we are done).

Why have we done all of this? Simple: to count the number of ways to distribute 7 cookies to 4 kids, all we need to do is count how many stars and bars charts there are. But a stars and bars chart is just a string of symbols, some stars and some bars. If instead of stars and bars we would use 0's and 1's, it would just be a bit string. We know how to count those.

Before we get too excited, we should make sure that really any string of (in our case) 7 stars and 3 bars corresponds to a different way to distribute cookies to kids. In particular consider a string like this:

egin{equation*} |***||**** end{equation*}

Does that correspond to a cookie distribution? Yes. It represents the distribution in which kid A gets 0 cookies (because we switch to kid B before any stars), kid B gets three cookies (three stars before the next bar), kid C gets 0 cookies (no stars before the next bar) and kid D gets the remaining 4 cookies. No matter how the stars and bars are arranged, we can distribute cookies in that way. Also, given any way to distribute cookies, we can represent that with a stars and bars chart. For example, the distribution in which kid A gets 6 cookies and kid B gets 1 cookie has the following chart:

egin{equation*} ******|*|| end{equation*}

After all that work we are finally ready to count. Each way to distribute cookies corresponds to a stars and bars chart with 7 stars and 3 bars. So there are 10 symbols, and we must choose 3 of them to be bars. Thus:

egin{equation*} mbox{ There are } {10 choose 3}mbox{ ways to distribute 7 cookies to 4 kids.} end{equation*}

While we are at it, we can also answer a related question: how many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie? What can you say about the corresponding stars and bars charts? The charts must start and end with at least one star (so that kids A and D) get cookies, and also no two bars can be adjacent (so that kids B and C are not skipped). One way to assure this is to only place bars in the spaces between the stars. With 7 stars, there are 6 spots between the stars, so we must choose 3 of those 6 spots to fill with bars. Thus there are ({6 choose 3}) ways to distribute 7 cookies to 4 kids giving at least one cookie to each kid.

Another (and more general) way to approach this modified problem is to first give each kid one cookie. Now the remaining 3 cookies can be distributed to the 4 kids without restrictions. So we have 3 stars and 3 bars for a total of 6 symbols, 3 of which must be bars. So again we see that there are ({6 choose 3}) ways to distribute the cookies.

Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:

Example (PageIndex{1})

Your favorite mathematical pizza chain offers 10 toppings. How many pizzas can you make if you are allowed 6 toppings? The order of toppings does not matter but now you are allowed repeats. So one possible pizza is triple sausage, double pineapple, and onions.

Solution

We get 6 toppings (counting possible repeats). Represent each of these toppings as a star. Think of going down the menu one topping at a time: you see anchovies first, and skip to the next, sausage. You say yes to sausage 3 times (use 3 stars), then switch to the next topping on the list. You keep skipping until you get to pineapple, which you say yes to twice. Another switch and you are at onions. You say yes once. Then you keep switching until you get to the last topping, never saying yes again (since you already have said yes 6 times. There are 10 toppings to choose from, so we must switch from considering one topping to the next 9 times. These are the bars.

Now that we are confident that we have the right number of stars and bars, we answer the question simply: there are 6 stars and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so there number of pizzas possible is

egin{equation*} {15 choose 9}. end{equation*}


2018 AMC 10A Problems/Problem 11

When fair standard -sided dice are thrown, the probability that the sum of the numbers on the top faces is can be written as where is a positive integer. What is ?


Published by

PRESH TALWALKAR

I run the MindYourDecisions channel on YouTube, which has over 1 million subscribers and 200 million views. I am also the author of The Joy of Game Theory: An Introduction to Strategic Thinking, and several other books which are available on Amazon.

(As you might expect, the links for my books go to their listings on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.)

By way of history, I started the Mind Your Decisions blog back in 2007 to share a bit of math, personal finance, personal thoughts, and game theory. It's been quite a journey! I thank everyone that has shared my work, and I am very grateful for coverage in the press, including the Shorty Awards, The Telegraph, Freakonomics, and many other popular outlets.

I studied Economics and Mathematics at Stanford University.

People often ask how I make the videos. Like many YouTubers I use popular software to prepare my videos. You can search for animation software tutorials on YouTube to learn how to make videos. Be prepared--animation is time consuming and software can be expensive!

Feel free to send me an email [email protected] . I get so many emails that I may not reply, but I save all suggestions for puzzles/video topics.

MY BOOKS

If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.

Mind Your Decisions is a compilation of 5 books:

The Joy of Game Theory shows how you can use math to out-think your competition. (rated 4.2/5 stars on 200 reviews)


40 Paradoxes in Logic, Probability, and Game Theory contains thought-provoking and counter-intuitive results. (rated 4.1/5 stars on 30 reviews)


The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 4/5 stars on 17 reviews)


The Best Mental Math Tricks teaches how you can look like a math genius by solving problems in your head (rated 4.2/5 stars on 57 reviews)


Multiply Numbers By Drawing Lines This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 4.1/5 stars on 23 reviews)


Mind Your Puzzles is a collection of the three "Math Puzzles" books, volumes 1, 2, and 3. The puzzles topics include the mathematical subjects including geometry, probability, logic, and game theory.

Math Puzzles Volume 1 features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 75 reviews.

Math Puzzles Volume 2 is a sequel book with more great problems. (rated 4.3/5 stars on 21 reviews)

Math Puzzles Volume 3 is the third in the series. (rated 4.3/5 stars on 17 reviews)

KINDLE UNLIMITED

Teachers and students around the world often email me about the books. Since education can have such a huge impact, I try to make the ebooks available as widely as possible at as low a price as possible.

Currently you can read most of my ebooks through Amazon's "Kindle Unlimited" program. Included in the subscription you will get access to millions of ebooks. You don't need a Kindle device: you can install the Kindle app on any smartphone/tablet/computer/etc. I have compiled links to programs in some countries below. Please check your local Amazon website for availability and program terms.

MERCHANDISE

Grab a mug, tshirt, and more at the official site for merchandise: Mind Your Decisions at Teespring.


Distributing apples: At least one to each

The next problem has a little twist.

What we have discussed so far allowed for the possibility that some urns would be empty. What if we disallow that?

Clearly the (indistinguishable) apples will be represented by stars, and the (presumably distinguishable) children are the containers. Doctor Anthony took this first:

This looks like the same idea, but something is different. Doctor Mitteldorf saw that further explanation would be useful:

We have the same representation as before, but with the new requirement that no child can be empty-handed, we must require that no two bars can be adjacent. They must be separated by stars. So rather than just freely place bars anywhere, we now think of gaps between stars, and place only one bar (if any) in each gap. For 8 stars and 4 urns (3 bars), we can put bars in any of the 7 spaces between stars (not on the outside, because that would leave an empty urn):

This corresponds to the arrangement:

This method leads to the general formula (for (b) balls in (u) urns, again, where we put (u-1) bars into (b-1) gaps) $<choose> ext< or ><choose>.$

Again, we can check our work by either actually listing all possibilities, or by imagining doing so and using some shortcuts:


2.5: Stars and Bars - Mathematics

You are about to erase your work on this activity. Are you sure you want to do this?

Updated Version Available

There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?

Mathematical Expression Editor

We use the Inclusion-Exclusion Principle to enumerate sets.

Recall the Inclusion-Exclusion Principle for two sets:

In this section, we will generalize this to sets, but first, let’s extend it from two sets to three sets.

Proof Consider as one set and as the second set and apply the Inclusion-Exclusion Principle for two sets. We have: Next, use the Inclusion-Exclusion Principle for two sets on the first term, and distribute the intersection across the union in the third term to obtain: Now, use the Inclusion Exclusion Principle for two sets on the fourth term to get: Finally, the set in the last term is just , so we have the final form of the Inclusion-Exclusion Principle for three sets:

We now extend De Morgan’s Law to three sets.

Proof Using De Morgan’s Law for two sets twice yields the result:

The next example uses De Morgan’s Law (for three sets) in conjunction with the Rule for Complements and the Inclusion-Exclusion Principle (for three sets).

Let be the set of passwords that do not contain any digits let be the set of passwords that do not contain any special symbols and let be the set of passwords that do not contain any capital letters. Since our passwords must contain a digit, a special symbol and a capital letter, we seek . By De Morgan’s Law (for three sets), Then according to the Rule for Complements, where is the set of all possible passwords with no restrictions. Combining the two equations above with the Inclusion-Exclusion Principle (for three sets), we have Each of the terms on the right hand side can be computed using the Fundamental Principle of Counting. Since there are 70 different characters in total with 10 digits, 8 special symbols and 26 capital letters, In conclusion, the number of acceptable passwords is

The number of elements in is the number of permutations of the symbols MATH, I, S, F, U, N. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, IS, F, U, N. Since this is 8 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, I, S, FUN. Since this is 7 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, IS, F, U, N. Since this is 5 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, I, S, FUN. Since this is 4 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, IS, FUN. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, IS, FUN. Since this is 3 distinct symbols, . The number of elements in is . Hence, the total number of ways to permute the letters in the phrase MATH IS FUN which do not include any of the words MATH, IS or FUN is

Notice that in our computation we took advantage of the fact that certain sets had the same number of elements.

For four sets, the Inclusion-Exclusion Principle states:

At this point, the number of terms is becoming quite large, so summation notation is to be preferred:

Now, the Inclusion-Exclusion Principle (for four sets) gives: Since the conditions on the four variables is the same (), the number of elements in each intersection of a particular number of sets will be equal. Thus, for the six intersections of this form for the four intersections of this form and . Hence,

We are now ready to state and prove the general case of the Inclusion-Exclusion Principle.

Proof We will prove the proposition by induction on the number of sets, . The base case, was proved in section 2.1. For the induction hypothesis, we assume that the result is true for some number of sets . We then wish to show that the result is true for sets. We will do this in a manner similar to the way we began this section, obtaining the Inclusion-Exclusion Principle for three sets as a consequence of the result for two sets. Thus, we consider the union of the first sets to be a single set and we obtain: In the last term, we can distribute the intersection over the unions to obtain a union of sets: We can apply the induction hypothesis the number of elements in this union, and noting that , we obtain Inserting this back into the first equation, and applying the induction hypothesis to the first term in that equation, we get

We now present a second proof, using a counting argument used in the proof of the two set case.

Proof (combinatorial proof)
Let and suppose that is an element of of the sets, . We need to show that the proposed formula accounts for exactly once. We will analyze the accounting for term by term. The first term of the Inclusion-Exclusion Principle is and this term accounts for exactly times, since is an element of of the sets in the sum. Note that is also . The second term of the Inclusion-Exclusion Principle is and this term accounts for exactly times since for to be in , both of these sets must be among the sets that contain . Similarly, the third term of the Inclusion-Exclusion Principle is and this term accounts for exactly times. Lastly, the term of the Inclusion-Exclusion Principle involves the intersections of of the sets. In this term, is accounted for times. The remaining terms of the Inclusion-Exclusion formula contain more than intersections and hence they will not account for at all (or zero times). In total, the number of times is accounted for by the Inclusion-Exclusion formula is From the binomial theorem with and and replacing and with and respectively, we have Thus the Inclusion-Exclusion formula accounts for in way, as desired.


Solution 4(Alcumus Solution 1)

The numbers of the three types of cookies must have a sum of six. Possible sets of whole numbers whose sum is six are Every ordering of each of these sets determines a different assortment of cookies. There are 3 orders for each of the sets There are 6 orders for each of the sets There is only one order for . Therefore the total number of assortments of six cookies is .


Mathcounts notes

Please take a look at what that program is all about. It's team work, problem solving, fun, friendship building and lots and lots more. The majority of students we met at the Mathcounts Nationals all went to the most selected colleges and are thriving there.

Prime – a number which cannot be divided by any numbers other than 1 and itself.

Factors – all whole numbers which can evenly divide a given number

Factoring – the breakdown of any number into its prime components

Greatest Common Factor ( GCF )– the greatest number which is a factor of two or more given numbers

Least Common Multiple/Denominator (LCM)– the smallest number which is a multiple of two or more given numbers

Relatively Prime – two numbers with a GCF of 1

A prime , as stated in the list of useful definitions, is a number which cannot be divided by any numbers other than 1 and itself. The smallest prime is 2 . [Or, as some people claim, the oddest prime.]

Whole numbers which are not primes are called composite. The smallest composite number is 4 .

1 is the exception: it is considered to be neither a prime nor a composite number.

Given a chart of the whole numbers 2-100, the primes can be easily recognized:

The easiest thing to do is to the look at the smallest primes – namely, 2, 3, 5, 7 – and cross all multiples of them from the chart.

The numbers most commonly mistaken for primes are 51, 57 and 91 . The first two (51 and 57) as can be shown by adding up the digits, is divisible by 3, while 91 is equal to 7x13.

To decide whether or not a number is a prime, take its square root and try dividing the original number by all primes less than the square root . If it is not divisible by any of them, the number is a prime.


Planning Curriculum

Common Core State Standards Connections

ELA/Literacy

  • RI.5.1 - Quote accurately from a text when explaining what the text says explicitly and when drawing inferences from the text. (5-ESS1-1), (5-PS2-1)
  • RI.5.7 - Draw on information from multiple print or digital sources, demonstrating the ability to locate an answer to a question quickly or to solve a problem efficiently. (5-ESS1-1)
  • RI.5.8 - Explain how an author uses reasons and evidence to support particular points in a text, identifying which reasons and evidence support which point(s). (5-ESS1-1)
  • RI.5.9 - Integrate information from several texts on the same topic in order to write or speak about the subject knowledgeably. (5-ESS1-1), (5-PS2-1)
  • SL.5.5 - Include multimedia components (e.g., graphics, sound) and visual displays in presentations when appropriate to enhance the development of main ideas or themes. (5-ESS1-2)
  • W.5.1 - Write opinion pieces on topics or texts, supporting a point of view with reasons and information. (5-ESS1-1), (5-PS2-1)

Mathematics

  • 5.G.A.2 - Represent real world and mathematical problems by graphing points in the first quadrant of the coordinate plane, and interpret coordinate values of points in the context of the situation. (5-ESS1-2)
  • 5.NBT.A.2 - Explain patterns in the number of zeros of the product when multiplying a number by powers of 10, and explain patterns in the placement of the decimal point when a decimal is multiplied or divided by a power of 10. Use whole-number exponents to denote powers of 10. (5-ESS1-1)
  • MP.2 - Reason abstractly and quantitatively. (5-ESS1-1), (5-ESS1-2)
  • MP.4 - Model with mathematics. (5-ESS1-1), (5-ESS1-2)

Model Course Mapping

First Time Visitors


PERMUTATION

A pastry shop sells 4 kind of pastries. How many distinct sets of 7 pastries can one buy?

7,0,0,0
0,0,7,0 we can see that ordering matters as they are determining each unique set . SO if ordering matters then it should be permutation.
I have gone through stars and bars method. But I want to know the sum is on permu or combo?

Elite Member

Dr.Peterson

Elite Member

A pastry shop sells 4 kind of pastries. How many distinct sets of 7 pastries can one buy?

7,0,0,0
0,0,7,0 we can see that ordering matters as they are determining each unique set . SO if ordering matters then it should be permutation.
I have gone through stars and bars method. But I want to know the sum is on permu or combo?

Please show how you are applying stars and bars. What do the stars and the bars mean in your model of the problem?

In what way does order matter in your description?

I want to see what you are applying a permutation or combination to, which should answer the question for you. There are a couple different ways you could describe this, which can involve either permutations or combinations. Write back with your answer, and I'll show you what I mean. But I want to start with whatever you have been specifically taught.

Saumyojit

Full Member

First of all i dont know how to apply stars and bars in problemn.

what can be the possible ways of arrangemnt ?
C1 C2 C3 C4
7 0 0 0
0 0 0 7
0 0 7 0
0 6 1 0
As we can see ordering of cakes matter . If ordering did not matter first 3 arrangements should be considered as one .
Ordering means permutation.
now prove my logic wrong using simple detailed explanation

Cubist

Full Member

You need to work out the number of ways that the stars and bars in PKA's post can be arranged.

Other ways might be (corresponding with your examples) :-

How many stars are there? How many bars? Can you work out the total possible combinations now?

Saumyojit

Full Member

FIRST TELL ME WHAT is wrong here?

C1 C2 C3 C4
7 0 0 0
0 0 0 7
0 0 7 0
0 6 1 0
As we can see ordering of cakes matter . If ordering did not matter first 3 arrangements should be considered as one .
Ordering means permutation.

Elite Member

Saumyojit

Full Member

@pka
FIRST TELL ME WHAT is wrong here?

C1 C2 C3 C4
7 0 0 0
0 0 0 7
0 0 7 0
0 6 1 0
As we can see ordering of cakes matter . If ordering did not matter first 3 arrangements should be considered as one .
Ordering means permutation.

Dr.Peterson

Elite Member

FIRST TELL ME WHAT is wrong here?

C1 C2 C3 C4
7 0 0 0
0 0 0 7
0 0 7 0
0 6 1 0
As we can see ordering of cakes matter . If ordering did not matter first 3 arrangements should be considered as one .
Ordering means permutation.

First, since you said "I have gone through stars and bars method,", I assumed that you knew how to use it, and perhaps had attempted to do so. You are not using the method, which is the appropriate method. The main thing wrong here is that you are not actually doing anything yet to solve it. What answer did you get your way?

Ordering of types matters, but ordering of individual cakes within a type does not. So you can't use ordinary permutations or combinations directly here.

Here's how the stars and bars method applies here: If we indicate cakes by *, and put them into boxes representing the types, your four examples would be represented by

where | is a divider between boxes.

Ignoring empty space, this is:

Elite Member

Cubist

Full Member

You could do it the LONG WAY if you really want to. You'll get the same answer. But hopefully it will convince you that transforming the problem into bars and stripes is much quicker and the result is equivalent.

Always choose c1 ≥ c2 ≥ c3 ≥ c4 to keep these combinations unique when permuted.

Saumyojit

Full Member

You could do it the LONG WAY if you really want to. You'll get the same answer. But hopefully it will convince you that transforming the problem into bars and stripes is much quicker and the result is equivalent.

Always choose c1 ≥ c2 ≥ c3 ≥ c4 to keep these combinations unique when permuted.

Saumyojit

Full Member

You could do it the LONG WAY if you really want to. You'll get the same answer. But hopefully it will convince you that transforming the problem into bars and stripes is much quicker and the result is equivalent.

Always choose c1 ≥ c2 ≥ c3 ≥ c4 to keep these combinations unique when permuted.

Cubist

Full Member

If I write out the multisets, you have
2 of '1'
1 of '0'
1 of '5'

Permutations = 4! / ( 2! * 1! * 1!) = 4!/2!=12 or listed out.
0115 , 1150
0151 , 1501
0511 , 1510
1015 , 5011
1051 , 5101
1105 , 5110

Saumyojit

Full Member

If I write out the multisets, you have
2 of '1'
1 of '0'
1 of '5'

Permutations = 4! / ( 2! * 1! * 1!) = 4!/2!=12 or listed out.
0115 , 1150
0151 , 1501
0511 , 1510
1015 , 5011
1051 , 5101
1105 , 5110

Cubist

Full Member

You asked about the line "5 1 1 0". This means c1=5, c2=1, c3=1,c4=0 meaning 5 cakes of type "c1", 1 cake of type "c2", 1 cake of type "c3", and NO cakes of type "c4"

There are 12 ways that these same quantities can be used to buy cakes. For example, one of the other ways is "0151" -> NO cakes of type "c1", 1 cake of type "c2", 5 cake of type "c3", and 1 cake of type "c4".

Saumyojit

Full Member

You asked about the line "5 1 1 0". This means c1=5, c2=1, c3=1,c4=0 meaning 5 cakes of type "c1", 1 cake of type "c2", 1 cake of type "c3", and NO cakes of type "c4"

There are 12 ways that these same quantities can be used to buy cakes. For example, one of the other ways is "0151" -> NO cakes of type "c1", 1 cake of type "c2", 5 cake of type "c3", and 1 cake of type "c4".

Cubist

Full Member

You are answering the question, "how many ways can I buy 3 cake types from 4 cake types".

But to perform the calculation in post#11 the question is "how many ways can I buy 5 cakes of one cake type, along with one cake of a different type, AND one cake of another different type".

If you don't understand this then I recommend that you seek some face-to-face tuition from someone.

Dr.Peterson

Elite Member

A couple of us have mentioned multisets. That is what this case (5,1,1,0) is it is not a set for which the standard permutation method works.

If you have seen problems that ask for the number of words you can make from a word with duplicate letters, such as GOOD, that is what you need to do here. The formula is (displaystyle frac), where (displaystyle n) is the total number of letters, and (displaystyle n_i) is the number of copies of the same ith letter out of k distinct letters. This was demonstrated in post #14.

Saumyojit

Full Member

A couple of us have mentioned multisets. That is what this case (5,1,1,0) is it is not a set for which the standard permutation method works.

If you have seen problems that ask for the number of words you can make from a word with duplicate letters, such as GOOD, that is what you need to do here. The formula is (displaystyle frac), where (displaystyle n) is the total number of letters, and (displaystyle n_i) is the number of copies of the same ith letter out of k distinct letters. This was demonstrated in post #14.

I got it what are u saying . 5,1,1,0
u are saying due to repetition of 2 1's u need to divide 2fact from all 4 fact ways .
But in 5,1,1,0 two 1's are of two different cakes . like 5 of c1 1 of c2 1 of c3

and in 5,0,1,1 5 are of first cake,zero of cake 2 ,one of cake 3 ,one of cake 4 .
They are of different cakes .

are u saying that : 5,0,1,1 & 0,5,1,1
these two unique arrangements are including replication of c3 and c4 in both the cases?


Can someone please explain the 'Stars and Bars' method for counting # of arrangements with repetitions?

Let's assume I have want to determine the number of possible solutions this equation could be satisfied.

x is only non-negative integers.

So okay, I can plug this stuff into the nice adorable formula and get the answer but I don't really get how the stars and bars formula work. Throw me a curb ball with an inequality or a different restriction and I'm at a loss. How do I approach these problems?

You can probably find a visual explanation online.

I can give a proof without stars-and-bars. First I'll state the theorem: with k>0, n>=0, there are C(n+k-1,k-1) k-tuples (x1. xk) in Z k satisfying x1. xk>=0, and x1+. +xk = n.

I'll induct on n+k, with base cases n=0 or k=1. When n=0, there's only solution (0,0. 0), and C(0+k-1,k-1) = 1. When k=1, there's only solution (n), and C(n+1-1,1-1) = 1.

Then with n>0 and k>1 break the solutions into two cases, x1=0, or x1>0. In the first case, solutions (0,x2,x3. xk) correspond to solutions (x2,x3. xk) of the same problem with n and k-1, and inductively there are C(n+k-2,k-2) solutions. In the second case, solutions (x1,x2. xk) correspond to solutions (x1-1,x2. xk) of the problem with n-1 and the same k, so C(n+k-2,k-1) solutions.

Using Pascal's recurrence for binomial coefficients,

This is beautifully done however I wouldn't be able to do any proofs by induction until. six more weeks. :-)

Bookmarked and will refer to it once I get to the point of being allowed to use induction on tests.

Here is an "easy" proof for stars and bars.

First, let us represent the equation sum(k-tuple X)=n (xi >= 0 is integer) in graphical form: n objects placed in k boxes.

And again, let's represent that in a different way: as stars (objects) and bars (separations between boxes) in a sequence. As an example, with k = 4 and n = 5, we have 3 bars and 5 stars:
**||**|*
This represents 2 objects in the first box, 0 in the second, 2 in the third, and 1 in the fourth.

We can count the number of possible orderings of stars and bars assuming both stars and bars are distinct: (n + k - 1)!
This is simply because there are (n) + (k - 1) distinct objects.
However, neither stars nor bars are distinct, so to get the number of possible orderings of stars and bars, we need to divide this ordering by (n)! and (k - 1)!, which are the number of orders of distinct stars and bars respectively.

Thus, the number of orderings of stars and bars, and thus the number of solutions to the equation, is (n + k - 1)!/(n)!(k - 1)!, which is equal to C(n + k - 1, k - 1).


Watch the video: γ Λυκείου μαθηματικά κατεύθυνσης κανόνες παραγώγισης μέρος 6ό (May 2022).