Combinatory

[annayurevych]

11th grade
Find: "The number of ways of distributing n distinct things in 3 identical boxes (empty boxes are allowed)"

I think that in total we have 3^n options (if the boxes were different). Something else needs to be added to this option. And divide all this by 3! (because the boxes are the same)

 

[blamocur]

11th grade
Find: "The number of ways of distributing n distinct things in 3 identical boxes (empty boxes are allowed)"

I think that in total we have 3^n options (if the boxes were different). Something else needs to be added to this option. And divide all this by 3! (because the boxes are the same)

But 3^n is not divisible by 3!

 

[pka]

11th grade
Find: "The number of ways of distributing n distinct things in 3 identical boxes (empty boxes are allowed)"
I think that in total we have 3^n options (if the boxes were different). Something else needs to be added to this option. And divide all this by 3! (because the boxes are the same)

First I must say, this decidedly not a question for any eleventh grade that I have ever known.
This is one of a class of questions known as Occupancy Problems. How many ways can N items occupy K cells The items can be distinct or identical. The cells can be distinct or identical. Some of the cells can be empty or all of the cells must be occupied. There is a class of numbers called Stirling Numbers of the first or second kind that is used the count the various combinations of putting the N items put into the K cells. You can be assured that the concepts only appear in advanced discrete mathematics textbooks. In the posted question has N distinct items with only three identical cells some of which can be empty. If an eleventh grader wants to tackle this question I suggest the text DISCRETE MATHEMATICS by James A. Anderson Ch12.

 

[blamocur]

I am no expert on the 11th grade math, but putting together the formula for the number of k-combinations [imath]C(n,k)[/imath] with the Newton Binomial Theorem does produce the answer of [imath]3^n[/imath], at least assuming that the boxes are not interchangeable.

 

[pka]

11th grade
Find: "The number of ways of distributing n distinct things in 3 identical boxes (empty boxes are allowed)"

I am no expert on the 11th grade math, but putting together the formula for the number of k-combinations [imath]C(n,k)[/imath] with the Newton Binomial Theorem does produce the answer of [imath]3^n[/imath], at least assuming that the boxes are not interchangeable.

It is given that the boxes are identical therefore they are interchangeable.
We do know that the items distinct. But all we know is there are n items.
How do you think we can count the number of ways the n distinct items can occupy the three identical cells?

 

[blamocur]

Actually, the boxes don't matter. It is all about the number of ways that a set of [imath]n[/imath] elements can be broken into 3 subsets, allowing empty subsets.
For each [imath]0\leq k \leq n[/imath] there are [imath]C(n,k)[/imath] ways to choose the first subset, and for each of those first subsets there are [imath]2^{n-k}[/imath] ways to break the remaining [imath]n-k[/imath] elements into two subsets.
Come to think of it, this problem can be generalized from 3 to arbitrary [imath]m[/imath] boxes/subsets.

 

[Cubist]

Actually, the boxes don't matter. It is all about the number of ways that a set of [imath]n[/imath] elements can be broken into 3 subsets, allowing empty subsets.
For each [imath]0\leq k \leq n[/imath] there are [imath]C(n,k)[/imath] ways to choose the first subset, and for each of those first subsets there are [imath]2^{n-k}[/imath] ways to break the remaining [imath]n-k[/imath] elements into two subsets.
Come to think of it, this problem can be generalized from 3 to arbitrary [imath]m[/imath] boxes/subsets.

I agree with PKA, but I'll try to argue my point in a more diplomatic way

Consider what happens when n=1. The ways to choose the first subset using your method is C(1,0)+C(1,1) = 2. Taking all three subsets into consideration, when we have k=0, ways are 1+1 AND k=1, 1 way. The total is three ways. In ascii graphics these 3 options could be shown as:-

@ O       O @         O O
 O         O           @

Where O is an empty box and @ is a box containing the single item. But if the boxes are identical, how would you distinguish between these three options? If you walked into a room that had these identical boxes on the floor, where would you stand in order to determine which of the three apply (imagine walking around the boxes)?

Therefore I believe that there's actually only 1 way to arrange 1 item into 3 identical boxes.

The OP could be due to a teacher making up a question themselves and accidentally (or unknowingly) using words that create a much more difficult problem than they intended.

 

[blamocur]

I agree with PKA, but I'll try to argue my point in a more diplomatic way

Consider what happens when n=1. The ways to choose the first subset using your method is C(1,0)+C(1,1) = 2. Taking all three subsets into consideration, when we have k=0, ways are 1+1 AND k=1, 1 way. The total is three ways. In ascii graphics these 3 options could be shown as:-

@ O       O @         O O
 O         O           @

Where O is an empty box and @ is a box containing the single item. But if the boxes are identical, how would you distinguish between these three options? If you walked into a room that had these identical boxes on the floor, where would you stand in order to determine which of the three apply (imagine walking around the boxes)?

Therefore I believe that there's actually only 1 way to arrange 1 item into 3 identical boxes.

The OP could be due to a teacher making up a question themselves and accidentally (or unknowingly) using words that create a much more difficult problem than they intended.

Thank you Cubist for your clear and very convincing counterexample. But, unless I've made another mistake, the answer with interchangeable boxes [imath]\left(\frac{3^{n-1}+1}{2}\right)[/imath] is not too difficult to figure out either.

 

[Cubist]

But, unless I've made another mistake, the answer with interchangeable boxes [imath]\left(\frac{3^{n-1}+1}{2}\right)[/imath] is not too difficult to figure out either.

I think this answer works very well! Numerically it seems to give the same result as S(n,1) + S(n,2) + S(n,3) which is the same as 1 + S(n,2) + S(n,3) where the function S gives the Stirling number of the second kind. I'll see if I can figure out how to obtain your result later - a nice puzzle.

 

[pka]

I think this answer works very well! Numerically it seems to give the same result as S(n,1) + S(n,2) + S(n,3) which is the same as 1 + S(n,2) + S(n,3) where the function S gives the Stirling number of the second kind. I'll see if I can figure out how to obtain your result later - a nice puzzle.

Here is an example. How many ways can we place seven(7) objects into three(3) boxes if: the objects are distinguishable, the boxes are indistinguishable, and boxes may be empty. The answer is the sum of Stirling Numbers of the second kind.
[imath]\mathcal{S}_1^{(7)}+\mathcal{S}_2^{(7)}+\mathcal{S}_3^{(7)}=1+63+301=\bf{365} [/imath]

 

[annayurevych]

But 3^n is not divisible by 3!

First I must say, this decidedly not a question for any eleventh grade that I have ever known.
This is one of a class of questions known as Occupancy Problems. How many ways can N items occupy K cells The items can be distinct or identical. The cells can be distinct or identical. Some of the cells can be empty or all of the cells must be occupied. There is a class of numbers called Stirling Numbers of the first or second kind that is used the count the various combinations of putting the N items put into the K cells. You can be assured that the concepts only appear in advanced discrete mathematics textbooks. In the posted question has N distinct items with only three identical cells some of which can be empty. If an eleventh grader wants to tackle this question I suggest the text DISCRETE MATHEMATICS by James A. Anderson Ch12.

I agree with PKA, but I'll try to argue my point in a more diplomatic way

Consider what happens when n=1. The ways to choose the first subset using your method is C(1,0)+C(1,1) = 2. Taking all three subsets into consideration, when we have k=0, ways are 1+1 AND k=1, 1 way. The total is three ways. In ascii graphics these 3 options could be shown as:-

@ O       O @         O O
 O         O           @

Where O is an empty box and @ is a box containing the single item. But if the boxes are identical, how would you distinguish between these three options? If you walked into a room that had these identical boxes on the floor, where would you stand in order to determine which of the three apply (imagine walking around the boxes)?

Therefore I believe that there's actually only 1 way to arrange 1 item into 3 identical boxes.

The OP could be due to a teacher making up a question themselves and accidentally (or unknowingly) using words that create a much more difficult problem than they intended.

Do you know how to solve a problem without "S" or other complicated formulas? This is the 11th grade.

 

[Cubist]

I just verified @blamocur 's post#8 answer for all cases using algebra

S(n,1)=1
S(n,2)=(2^n-2)/2
S(n,3)=(3^n - 3*2^n + 3)/6

Therefore S(n,1) + S(n,2) + S(n,3)
= 1 + (2^n-2)/2 + (3^n - 3*2^n + 3)/6
= 6/6 + (3*2^n-6)/6 + (3^n - 3*2^n + 3)/6
= (6 + 3*2^n - 6 +3^n - 3*2^n + 3)/6
= (3^n + 3)/6
= (3^(n - 1) + 1)/2

@blamocur did you obtain this result via a different, simpler, method?

 

[blamocur]

I just verified @blamocur 's post#8 answer for all cases using algebra

S(n,1)=1
S(n,2)=(2^n-2)/2
S(n,3)=(3^n - 3*2^n + 3)/6

Therefore S(n,1) + S(n,2) + S(n,3)
= 1 + (2^n-2)/2 + (3^n - 3*2^n + 3)/6
= 6/6 + (3*2^n-6)/6 + (3^n - 3*2^n + 3)/6
= (6 + 3*2^n - 6 +3^n - 3*2^n + 3)/6
= (3^n + 3)/6
= (3^(n - 1) + 1)/2

@blamocur did you obtain this result via a different, simpler, method?

Yes I did. Almost every distribution belongs to a group of 6 equivalent ones. The exception is a group of 3 distributions with 2 empty sets each.

 

[blamocur]

Do you know how to solve a problem without "S" or other complicated formulas? This is the 11th grade.

Yes I do: please see the hint in my previous post (a reply to a question by Cubist).

 

[Cubist]

Yes I did. Almost every distribution belongs to a group of 6 equivalent ones. The exception is a group of 3 distributions with 2 empty sets each.

That's a great hint! @annayurevych here's an extra hint if you need it...

Spoiler: extra hint

Here's an example with items a,b,c with non-identical boxes...

First group, "Almost every distribution belongs to a group of 6 equivalent ones"

  a  |b  |c
  a  |c  |b
  b  |a  |c
  b  |c  |a
  c  |a  |b
  c  |b  |a

  ab |c  |
  ab |   |c
  c  |ab |
  c  |   |ab
     |ab |c
     |c  |ab

  ac |b  |
  ac |   |b
  b  |ac |
  b  |   |ac
     |ac |b
     |b  |ac

  a  |bc |
  a  |   |bc
  bc |a  |
  bc |   |a
     |a  |bc
     |bc |a

Second group, "The exception is a group of 3 distributions with 2 empty sets each."

  abc|   |
     |abc|
     |   |abc

Let g be the number of distributions in the first group. In the example g=24. Can you see that for any n the following is true...

3^n = g + 3

Now continue by writing an expression, in terms of g, for the total number of distributions with identical boxes...