PERMUTATION

[Saumyojit]

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?

 

[pka]

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?

This is a simple stars & bars problem: $\displaystyle \bf{*~*~*~*~*~*~*~|~|~|}$

 

[Dr.Peterson]

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]

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]

This is a simple stars & bars problem: $\displaystyle \bf{*~*~*~*~*~*~*~|~|~|}$

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) :-

7 0 0 0 -> $\displaystyle \bf{*~*~*~*~*~*~*~|~|~|}$
0 0 0 7 -> $\displaystyle \bf{|~|~|*~*~*~*~*~*~*~}$
0 6 1 0 -> $\displaystyle \bf{|~*~*~*~*~*~*~|~*~|~}$

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

 

[Saumyojit]

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.

 

[pka]

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

From your original post, I took it to mean that you had studied the stars&bars method.
The seven selections are the stars, there are seven identical things. The four types of pastries are represented by three bars.
In general, the number of ways to place $\displaystyle N$ identical objects into $\displaystyle K$ distinct cells rquals $\displaystyle \dfrac{(N+K-1)!}{N!(K-1)!}$
The selection are the identical objects and the pastries are the distinct cells.

 

[Saumyojit]

@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]

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:

*******|||​

|||*******​

||*******|​

|******|*|​

So each possibility can be modeled as a permutation of 7 identical *'s and 3 identical |'s. You can also model this as choosing 3 of 10 positions in the line to fill with |, with the rest being *. So you can use either permutations (of a multiset), or combinations to do the calculation, but neither permutations nor combinations of the 7 cakes themselves will work.

 

[pka]

@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.

What is wrong? Everything!
Order has absolutely nothing to do with this problem
The answer is $\displaystyle \frac{10!}{(7!)(3!)}$

 

[Cubist]

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...

         Ways to permute
7 0 0 0  4!/3!
6 1 0 0  4!/2!
5 2 0 0  4!/2!
5 1 1 0  4!/2!
4 3 0 0  4!/2!
4 2 1 0  4!
4 1 1 1   ?
3 3 1 0   ?
3 2 2 0   ?
3 2 1 1   ?
2 2 2 1   ?
         ======
         SUM THE ABOVE

 

[Saumyojit]

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...

         Ways to permute
7 0 0 0  4!/3!
6 1 0 0  4!/2!
5 2 0 0  4!/2!
5 1 1 0  4!/2!
4 3 0 0  4!/2!
4 2 1 0  4!
4 1 1 1   ?
3 3 1 0   ?
3 2 2 0   ?
3 2 1 1   ?
2 2 2 1   ?
         ======
         SUM THE ABOVE

IS this 120 coming plzz check

 

[Saumyojit]

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...

         Ways to permute
7 0 0 0  4!/3!
6 1 0 0  4!/2!
5 2 0 0  4!/2!
5 1 1 0  4!/2!
4 3 0 0  4!/2!
4 2 1 0  4!
4 1 1 1   ?
3 3 1 0   ?
3 2 2 0   ?
3 2 1 1   ?
2 2 2 1   ?
         ======
         SUM THE ABOVE

How 5 1 1 0
Can be 4p2 it should be 4p3..

 

[Cubist]

How 5 1 1 0
Can be 4p2 it should be 4p3..

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]

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

I am choosing 3 type of cake out of 4 . So 4p3 .

 

[Cubist]

I am choosing 3 type of cake out of 4 . So 4p3 .

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]

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".

Yes we are choosing 3 types out of 4 cakes in this combination 5,1,1,0
4p3 ....

 

[Cubist]

Yes we are choosing 3 types out of 4 cakes in this combination 5,1,1,0
4p3 ....

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]

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 [MATH]\frac{n!}{n_1!n_2!...n_k!}[/MATH], where [MATH]n[/MATH] is the total number of letters, and [MATH]n_i[/MATH] is the number of copies of the same ith letter out of k distinct letters. This was demonstrated in post #14.

 

[Saumyojit]

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 [MATH]\frac{n!}{n_1!n_2!...n_k!}[/MATH], where [MATH]n[/MATH] is the total number of letters, and [MATH]n_i[/MATH] 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?