Question

Can anyone please explain how we can distribute n objects in m boxes if:
a) Objects were distinct and boxes were identical
b)Objects were identical and boxes were identical

Answer 1

@LastDayWork @Loser66 @Vincent-Lyon.Fr

Answer 2

Are there any constraints as to how many objects a box can hold? In other words can a box hold none or all objects?

Answer 3

^^ @MayankD

Answer 4

No

Answer 5

Yes it can hold any number from all to none

Answer 6

for (a) use Stirling numbers of the 2nd kind and for (b) use stars-and-bars

Answer 7

Reformat your question -
(a) Distribute m (identical) boxes in n (distinct) objects.
- Use the method of fictitious partition i.e., the method you'll use to find number of integral solutions of equation -
x + y + z + ...(r variables) = n (a natural number)

(b) In the previous distribution, divide by factorial(m) (why?)

PS: I know that putting boxes in objects sounds weird; try to use them as abstract entities.

Answer 8

never heard of the method of fictitious partitions but the problem is exactly
http://www.ams.org/bookstore/pspdf/stml-65-prev.pdf

Answer 9

http://math.stackexchange.com/questions/190820/distribute-distinct-objects-in-identical-boxes

Answer 10

Thanks i got it. For a) its use sterling no and for b use pascal number.

Answer 11

np :-) glad I could help. I knew these would be the right approaches

Answer 12

@oldrin.bataku stars and bars is for n identical objects and m distinct boxes. @LastDayWork The integral solution is the same as or rather a consequence of stars and bars

Answer 13

oh oops I misread (b)

Answer 14

Np! thanks for the help though

Answer 15

@MayankD
Agreed. I don't know much about terminologies :D

Answer 16

Anyway sterling and pascals no are only valid if no box is empty. In the case boxes are empty we have to take cases of distribution and ratios :(

Answer 17

if boxes can be empty then you just get sums of Stirling numbers of the 2nd kind i.e. Bell numbers

Answer 18

In the "method of fictitious partitions :P " we use the formula (n+r-1)C(r-1) and it includes blanks (please bear with my notation).

Answer 19

well actually that's not necessarily true that they're Bell but you do sum Stirling numbers

Answer 20

@LastDayWork Yea i know but that is for n identical objects and m distinct boxes. That is not my question

Answer 21

http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two that's more commonyl known as stars-and-bars @LastDayWork

Answer 22

@MayankD
Consider reversing the entities (boxes and objects)

Answer 23

@oldrin.bataku
Thanks for updating me.
What are Bell and Stirling numbers?

Answer 24

@LastDayWork that will generate an error. Since boxes and objects are two different kinds of entities. Objects in this case are unshareable and boxes are shareable. Therefore you cannot switch. If you switch you will also take into account a case in which one object holds two boxes which is absurd since object cannot be split

Answer 25

@LastDayWork the Bell number \(B_n\) is the number of partitions of an \(n\)-set

Answer 26

Stirling number of the 2nd kind \(S(n,k)\) is the number of ways to partition \(n\)-set into \(k\) non-empty partitions

Answer 27

@oldrin.bataku
Tell me what do you call this method (I call it Coefficient method :D )

Number of ways in which it is possible to make a selection from m+n+p=N things, where p are alike of one kind, m alike of second kind...
is given by the coefficient of x^r in the expansion of -
(1+x+x^2+...x^p)(1+x+x^2+...+x^m)(1+x+x^2+...+x^n)

And we finally use the formula (1-x)^(-n) = (n+r-1)C(r) ; n∈N

Answer 28

Selection of how many objects at a time? If its any number of objects the the answer is (m+1)*(p+1)*(n+1)

Answer 29

Selection of r objects (I somehow missed this line)

Answer 30

when it is "any number of objects" we can put x = 1 in the equation to get (what you already stated)
(m+1)*(p+1)*(n+1)

Answer 31

Yes

Answer 32

@MayankD
What do you call this method?

Answer 33

Nothing really. It's just a variation of the shuffling technique

Answer 34

I dunno it's straight-forward... probably an example of generating polynomials

Answer 35

It leads to the same formula as that of stars and bars.