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

Question

I HAVE SEEN stars and bars reference from this sum. But still I dont get it .

I dont get it whether it is permutation or combination.

I have done the sum in this way. All arrangements

C1 C2 C3 C4

7 0 0 0. = 4p1 (from 4 cakes choosing one)

5 2 0 0. = 4p2 (from 4 cakes choosing two)

6 1 0 0 = 4p2 (from 4 cakes choosing 2)

5 1 1 0= 4p3

4 2 1 0 = 4p3

4 1 1 1= 4p4

3 3 1 0= 4p3

3 2 2 0 = 4p3

3 2 1 1 = 4p4

2 2 2 1 = 4p4

Summing all of these will give me the correct answer???

Answer 1

The problem that you have stated is a combination problem. This is because the order in which the pastries are arranged does not matter. Now suppose you had to give $7$ pastries to $7$ different children. Here the order does matter as for the same set of pastries, each kid can get different arrangements. You could swap the pastries of two kids while maintaining the same number of each pastry being picked. The second problem is one of permutations. The two problems require different approaches to solve them.

Let $a, b, c, d$ denote the $4$ types of pastries. The solution to your problem would be the number of whole number solutions for this equation- $$a+b+c+d=7$$ Think about this for a bit. This is equivalent to the stars and bars problem. I leave you to calculate the number of solutions for this equation.

$C={{7+4-1}\choose {4-1}}={10\choose 3}=\frac {10!}{7!\cdot3!}$

Now, for the permutations problem, each kid may get any of the $4$ pastries. Hence for each kid, you have $4$ options. Hence the permutations will be $P=4\times 4\times4 \cdots \text{7 times}=4^7$

Answer 2

You can simply think of this as a combination of several cases.
Case I: You buy only one kind of pastry in $4\choose1$ ways.

Case II: You buy only two types of pastries. You choose two types of pastries in $4\choose 2$ ways.
Secondly, you can buy $(1,6),(2,5)...$ pastries to get a total of seven in ${7-1}\choose{2-1}$ ways. [Do you know why we wrote ${7-1}\choose{2-1}$?]

Case III: Buy three kinds of pastries in $4\choose 3$ ways. Buy $(1,1,5),(1,2,4)...$ pastries in ${7-1}\choose{3-1}$ ways.

Case IV: Buy all four kinds in one way. Buy $(1,1,1,4),(1,1,2,3)...$ pastries in ${7-1}\choose{4-1}$ ways.

Total number of ways = ${4\choose{1}}+{4\choose2}\cdot{6\choose1}+{4\choose3}\cdot{6\choose2}+1\cdot{6\choose3}=120$ ways

Answer 3

What matters here is how many of each type of pastry are selected. Selecting three pecan pies, two apple strudel, one croissant, and one baklava is different from selecting four baklava, two apple strudels, and one pecan pie.

Let's label the types of pastries 1, 2, 3, and 4. Let $x_i$, $1 \leq i \leq 4$, be the number of pastries of type $i$ that are selected. Since a total of seven pastries are selected from the four types, $$x_1 + x_2 + x_3 + x_4 = 7 \tag{1}$$ The number of ways the pastries can be selected is the number of solutions of equation 1 in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of three addition signs in a row of seven ones. For instance, $$1 1 + 1 1 1 + 1 + 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 3$, $x_3 = 1$, $x_4 = 1$, while $$1 + + 1 1 1 1 + 1 1$$ corresponds to the solution $x_1 = 1$, $x_2 = 0$, $x_3 = 4$, $x_4 = 2$.

The number of solutions of equation 1 in the nonnegative integers is the number of ways $4 - 1 = 3$ addition signs can be placed in a row of $7$ ones, which is $$\binom{7 + 4 - 1}{4 - 1} = \binom{10}{3}$$ since we must select which three of the ten positions required for seven ones and three addition signs will be filled with addition signs.

What was wrong with your attempt?

The partitions of $7$ into at most four parts are \begin{align*} 7 & = 7\\ & = 6 + 1\\ & = 5 + 2\\ & = 5 + 1 + 1\\ & = 4 + 3\\ & = 4 + 2 + 1\\ & = 4 + 1 + 1 + 1\\ & = 3 + 3 + 1\\ & = 3 + 2 + 2\\ & = 3 + 2 + 1 + 1\\ & = 2 + 2 + 2 + 1 \end{align*}

Your counts are correct for the cases in which a different number of each type of pastry is selected. However, they are incorrect when the same number of pastries are selected from two or more types.

$5 + 1 + 1$: There are four ways to select the type of pastry from which five pieces of pastry will be selected. There are $\binom{3}{2}$ ways to select the two types of pastry from which one piece of pastry each will be selected. Hence, there are $$\binom{4}{1}\binom{3}{2}$$ such selections.

$3 + 3 + 1$: There are $\binom{4}{2}$ ways to select the two types of pastries from which three pieces of pastry will be drawn and two ways to select the type of pastry from which one piece of pastry will be drawn. Hence, there are $$\binom{4}{2}\binom{2}{1}$$ such selections.

Notice that $$\binom{4}{1}\binom{3}{2} = \binom{4}{2}\binom{2}{1}$$ This is because in both the $5 + 1 + 1$ case and the $3 + 3 + 1$ case, there are three types of pastry drawn, with equal amounts of exactly two of them. We could have done the $3 + 3 + 1$ case by first selecting the type of pastry from which one piece of pastry will be drawn, then selecting from which two of the three types of pastry three pieces of pastry each would be drawn, which would have yielded the count $$\binom{4}{3}\binom{3}{2}$$

$3 + 2 + 2$: The argument above shows that there are also $$\binom{4}{1}\binom{3}{2}$$ such cases.

$4 + 1 + 1 + 1$: There are four ways to select the type of pastry from which four pieces will be selected. We must select one of each the other types. Hence, there are $$\binom{4}{1}$$ such selections.

$2 + 2 + 2 + 1$: There are four ways to select the type of pastry from which one piece will be selected. We must select two pieces each from each of the remaining types of pastry. Hence, there are $$\binom{4}{1}$$ such selections.

$3 + 2 + 1 + 1$: There are four ways to select the type of pastry from which three pieces will be drawn and three ways to select the type of pastry from which two pieces will be drawn. We must select one piece each from each of the remaining types of pastry. Hence, there are $$\binom{4}{1}\binom{3}{1}$$ such selections.

With these corrections, we obtain a total of $$\binom{4}{1} + \binom{4}{1}\binom{3}{1} + \binom{4}{1}\binom{3}{1} + \binom{4}{1}\binom{3}{2} + \binom{4}{1}\binom{3}{1} + \binom{4}{1}\binom{3}{1}\binom{2}{1} + \binom{4}{1} + \binom{4}{2}\binom{2}{1} + \binom{4}{1}\binom{3}{2} + \binom{4}{1}\binom{3}{1} + \binom{4}{1} = \binom{10}{3}$$ ways to select seven pastries of four types.

What type of problem is this?

This is a combination with repetition problem since we are selecting $k$ objects from $n$ types of objects, where we may take the same type of object repeatedly.