Prev: Maple animation question
Next: Functional Equation
From: TCL on 14 May 2010 19:15
Suppose there are n boxes and r marbles. Find the number of ways the
marbles can be placed in the boxes in the following cases:

Case 1: (a) boxes are indistinguishable, (b) marbles are
indistinguishable, (c) any number of marbles in each box.

Case 2: (a) boxes are indistinguishable, (b) marbles are
distinguishable, (c) any number of marbles in each box.

Case 1 is equivalent to partitioning of r into a sum of n or less
numbers.
Since there are no explicit formulae for partition of an integer, I
think there are no
formulae for case 1 either.

Case 2 is even harder. But can it be expressed in terms of answer to
case 1?
From: christian.bau on 14 May 2010 19:47
On May 15, 12:15 am, TCL <tl...(a)cox.net> wrote:
> Suppose there are n boxes and r marbles. Find the number of ways the
> marbles can be placed in the boxes in the following cases:
>
> Case 1: (a) boxes are indistinguishable, (b) marbles are
> indistinguishable, (c) any number of marbles in each box.
>
> Case 2: (a) boxes are indistinguishable, (b) marbles are
> distinguishable, (c) any number of marbles in each box.
>
> Case 1 is equivalent to partitioning of r into a sum of n or less
> numbers.
> Since there are no explicit formulae for partition of an integer, I
> think there are no
> formulae for case 1 either.
>
> Case 2 is even harder. But can it be expressed in terms of answer to
> case 1?

Case 2 is easy. If the boxes were distinguishable, and the marbles as
well, then there would be n^r ways to put the marbles into the boxes.
But because the boxes are all the same, the can be swapped around in
n! ways. So there are (n^r) / n! ways. And I leave it to you to find
out the tiny mistake that I made to make it more interesting :-)
From: TCL on 14 May 2010 22:39
On May 14, 7:47 pm, "christian.bau" <christian....(a)cbau.wanadoo.co.uk>
wrote:
> On May 15, 12:15 am, TCL <tl...(a)cox.net> wrote:
>
>
>
>
>
> > Suppose there are n boxes and r marbles. Find the number of ways the
> > marbles can be placed in the boxes in the following cases:
>
> > Case 1: (a) boxes are indistinguishable, (b) marbles are
> > indistinguishable, (c) any number of marbles in each box.
>
> > Case 2: (a) boxes are indistinguishable, (b) marbles are
> > distinguishable, (c) any number of marbles in each box.
>
> > Case 1 is equivalent to partitioning of r into a sum of n or less
> > numbers.
> > Since there are no explicit formulae for partition of an integer, I
> > think there are no
> > formulae for case 1 either.
>
> > Case 2 is even harder. But can it be expressed in terms of answer to
> > case 1?
>
> Case 2 is easy. If the boxes were distinguishable, and the marbles as
> well, then there would be n^r ways to put the marbles into the boxes.
> But because the boxes are all the same, the can be swapped around in
> n! ways. So there are (n^r) / n! ways. And I leave it to you to find
> out the tiny mistake that I made to make it more interesting :-)- Hide quoted text -
>
> - Show quoted text -

I don't think it is that easy. Some boxes could be empty, so (n^r) /
n! is certainly wrong.
From: Arturo Magidin on 14 May 2010 23:02
On May 14, 6:15 pm, TCL <tl...(a)cox.net> wrote:
> Suppose there are n boxes and r marbles. Find the number of ways the
> marbles can be placed in the boxes in the following cases:
>
> Case 1: (a) boxes are indistinguishable, (b) marbles are
> indistinguishable, (c) any number of marbles in each box.
>
> Case 2: (a) boxes are indistinguishable, (b) marbles are
> distinguishable, (c) any number of marbles in each box.
>
> Case 1 is equivalent to partitioning of r into a sum of n or less
> numbers.
> Since there are no explicit formulae for partition of an integer, I
> think there are no
> formulae for case 1 either.
>
> Case 2 is even harder.

Actually, Case 2 is just the partitions of a set; this is given by the
Stirling numbers of the second kind if you want a specific number of
parts, and by the Bell numbers if you want all partitions.

--
Arturo Magidin
From: TCL on 14 May 2010 23:14
On May 14, 11:02 pm, Arturo Magidin <magi...(a)member.ams.org> wrote:
> On May 14, 6:15 pm, TCL <tl...(a)cox.net> wrote:
>
>
>
>
>
> > Suppose there are n boxes and r marbles. Find the number of ways the
> > marbles can be placed in the boxes in the following cases:
>
> > Case 1: (a) boxes are indistinguishable, (b) marbles are
> > indistinguishable, (c) any number of marbles in each box.
>
> > Case 2: (a) boxes are indistinguishable, (b) marbles are
> > distinguishable, (c) any number of marbles in each box.
>
> > Case 1 is equivalent to partitioning of r into a sum of n or less
> > numbers.
> > Since there are no explicit formulae for partition of an integer, I
> > think there are no
> > formulae for case 1 either.
>
> > Case 2 is even harder.
>
> Actually, Case 2 is just the partitions of a set; this is given by the
> Stirling numbers of the second kind if you want a specific number of
> parts, and by the Bell numbers if you want all partitions.
>
> --
> Arturo Magidin- Hide quoted text -
>
> - Show quoted text -

That is right. So the answer to Case 2 is

sum of S(r,k), k=1..n

 | 
Pages: 1
Prev: Maple animation question
Next: Functional Equation