Now Our Question is: six identical balls into three identical bins(empty allowed) which is same as partition 6 into atmost 3 parts (as sum of integers).
i.e. No. of ways
=P(6,1)+P(6,2)+P(6,3)
(Using P(n,k) = summation of P(n-k,r) for r = 1,2,3,...,k )
= 1+P(4,1)+P(4,2)+P(3,1)+P(3,2)+P(3,3)
=1+1+2+1+1+1
=7.
Explaination:
Distribution of identical Balls into identical Bins is closely related with partitioning off integer.
Let us define Partition function P(n) as partioning n (>=0) as sum of integers in unique ways ( for e.g n=3, 1+2 and 2+1 is treated same partition) then P(n) is equivalent to no. of distribution of n identical balls into any no. of identical bins.
n=1 partion set {1} P(1)=1
n=2 partion set {1+1,2} P(2)=2
n=3 partition set {1+1+1,1+2,3} => P(3)= 3
n=4 =>{1+1+1+1,1+1+2,1+3,2+2,4} => P(4)=5
Here you notice that partition size varies from 1,2,3...,n i.e we counting all possible partition.
Let Define Partition of n into size of k as P(n,k)=Partion of n as sum of k integers (uniquely).
for e.g (i) n=5 and k=2 P(5,2)={1+4,2+3}=2 (ii) P(6,3)={1+1+4,1+2+3,2+2+2}=3.
for k>n no ways P(n,k)=0 where k>n e.g. we can't partion 4 in 5 or more parts.
for k=1 1 ways as n => P(n,1)=1.
for k=n 1 ways as all 1 i.e 1+1+... +1 => P(n,n)=1
for k=2 to n-1 we can write a Recurrence Relation P(n,k) = summation of P(n-k,r) for r = 1,2,3,...,k.
for e.g. P(6,3)=P(3,1)+P(3,2)+P(3,3)=P(3,1)+P(1,1)+P(1,2)+P(3,3) =1+1+0+1=3
Above P(n,k) i.e Partion of n as sum of k integers is same as distribution of n identical balls into k identical bins (non-empty).
Note: if every bin should have atleast one ball (i.e. non-empty bins) then
Number of ways = partion 6 into size of 3 i.e. P(6,3)=P(3,1)+P(3,2)+P(3,3)=1+1+1=3 ways.
Bonus: Partition of n into size of k P(n,k) = summation of P(n-k,r) for r = 1,2,3,...,k.
(Proof: Put 1 balls in each bins (to make bins non-empty) then rest n-k balls treat that bins are empty and we can put in any number of boxes (r) where r = 1,2,3,..,k.)
