Having a problem on a paradoxical answer

39 Views Asked by At

Suppose that we have PN objects (disks for an example) and we have P slots (or boxes),how many ways can we distribute those PN objects on those P slots so that each slot has exactly N object? i saw a law somewhere that states that the number of ways of distributions is $\dbinom{PN}{N} *\dbinom{(P-1)N}{N}*.....*\dbinom{2N}{N} $

Is this true? and if it is how can i prove it?

let suppose now that we have 4 objects and 2 slots,with the same law i stated above the answer should be $\dbinom{2*2}{2}=6$,but it can be solved in another way,since we are distributing 4 objects on two slots,with each slot having exactly 2 objects,then first we need to choose a slot from the two we have,after that we need to choose 2 objects to put in the slot we chose,then choose another 2 for the other slot,the answer with this way is $\dbinom{2}{1}*\dbinom{4}{2}*\dbinom{2}{2}=12$ which doesn't make sense,this is confusing me so what's wrong? me,the law or everything all together?

2

There are 2 best solutions below

3
On

It is true if the slots are distinguishable but the position within the slots are not. An inductive proof over $P$ would say that there is clearly $1$ solution if $P=1$ (your expression has an empty product), while in the general case you have ${PN \choose N}$ possibilities for the first box, leaving $(P-1)N$ items and $P-1$ boxes for which the inductive hypothesis would give the solution.

Your calculations of $4$ or $8$ in your second paragraph both have errors for $P=2,N=2$. If the items are $A,B,C,D$ then the possibilities for the two slots are

  • $(\{A,B\},\{C,D\})$
  • $(\{A,C\},\{B,D\})$
  • $(\{A,D\},\{B,C\})$
  • $(\{B,C\},\{A,D\})$
  • $(\{B,D\},\{A,C\})$
  • $(\{C,D\},\{A,B\})$

which is $6=\frac{4!}{2! \times 2!} = {4 \choose 2} = {2 \times 2 \choose 2}$

0
On

Multiplying the term $$ \dbinom{2}{1} $$ ensures that the solution counts each slot once. Hence, your approach is equivalent to taking each slot and putting all possible pairs of objects in it with the other two placed in the other box.

Here, you forgot to note that you have put a pair of objects $$(B_1,B_2)$$ in slot 1 and $$(B_3,B_4)$$ in slot 2 and achieved the exact arrangement once again while dealing with the second box. This means you have two of each arrangement of objects in hand.

The total number of objects will be $$\frac{12}{2} = 6$$.