Distributing elements into groups all variants

Grouping of elements into groups depends on 3 conditions

So we have 8 possible combinations of above 3 conditions.

1. Number of ways to distribute n identical elements into m distinct non-empty groups.

Number of ways to distribute 2 balls into a bag and a bucket such that no bag is empty.

{ { 1 in bucket,1 in bag } }

Number of ways to distribute 2 balls into a bag and a bucket { { 0 in bucket, 2 in bag }, { 1 in bucket, 1 in bag }, { 2 in bucket, 0 in bag } }
Stars and Bars Theorem 2

To divide 5 star into 3 groups you would need 2 bars.
⭐ ⭐ ❚ ⭐ ⭐ ❚ ⭐
Out of 7 possible position the bars can be at any two position.
Total number of ways = ⁷C₂
Total ways = ^(n+m-1) C _(m-1)

Number of ways to distribute a red ball and a blue ball into 2 bags such that no bag is empty { {both in different bags } }
Any other arrangement will either make one bag empty or will mirror above scenario since both bags are identical.
This is given by Stirling numbers of second kind S(n,m) which counts the number of ways to partition a set of n elements into m non-empty subsets.
S(n,m) = m * S(n-1,m) + S(n-1,m-1)
- m * S(n-1,m)
  This term refers to the case where the n-th element is added to one of the existing m sets that have already been formed from the n−1 elements.
- S(n-1,m-1)
  This term refers to the case where the n-th element is placed in its own new set, which means it becomes the only element in that set.
- Base Cases
  - S(0,0) = 1: There’s exactly one way to partition zero elements into zero sets (the empty partition).
  - S(n,0) = 0 for n>0: You cannot partition a non-zero number of elements into zero non-empty sets.
  - S(n,1) = 1: There’s exactly one way to partition n elements into 1 set (all elements in one set).
Total ways = S(n,m) = m * S(n-1,m) + S(n-1,m-1)

Number of ways to distribute a red ball and a blue ball into 2 bags. { { both in same bag }, { both in different bags } }
If some groups are empty, we can count the number of ways to distribute elements into remaining non-empty groups using the above result i.e. S(n, m - number of empty groups) ways. This can occur with no groups empty, 1 group empty, 2 groups empty, …. so on till m-1 groups.
Total ways = S(n,1) + S(n,2) + ….. + S(n,m)

This is closely related to the Bell Number (Bn) which counts the different ways to partitions a set of n elements into any number of groups. Bn = S(n,1) + S(n,2) + S(n,3) + …. S(n,n)

Number of ways to distribute 2 balls into 2 bags such that no bags are empty. { {1,1} }
Since elements are identical only the count of element in each group matters. and since the groups are identical the order of the groups do not matter. So {2,1} is same as {1,2} one way to achieve this is to keep the count in weakly decreasing order.
This situation is very similar to Integer Partition problem which counts all possible unordered set of positive numbers that have sum n.
A very nice visual explanation for the recursive relation is on Youtube
The recursive relation is defined as: P(n,m) = P(n-1,m-1) + P(n-m,m)
- If a group has 1 element , when we remove that group we get all possible ways to distriubte n-1 elements into m-1 groups given by P(n-1,m-1)
- If no group has 1 element i.e all groups have atleast 2 elements In this case removing 1 element from each group will give us all possible ways to distribute n-m elements into m groups given by P(n-m,m)
Total ways = P(n,m) = P(n-1,m-1) + P(n-m,m)

Number of ways to distribute 2 balls into 2 bags
{ {1,1}, {0,2} } Here, {2,0} is samse to {0,2} because groups are identical
Similar to case #4 If some groups are empty then we can count the number of ways to distribute elements into remaining non-empty groups using the above result i.e. P(n, m - number_of_empty_groups) ways. we can have no groups empty, 1 group empty , 2 groups empty, …. so on till m-1 groups.
Total ways = P(n,1) + P(n,2) + ….. + P(n,m)

Number of ways to distribute a red ball and a blue ball into a bucket and a bag.
{ { None in bucket, both in bag }, { both in bucket, None in bag },
{ red ball in bucket, blue ball in bag }, { blue ball in bucket, red ball in bag } } ,
For each element we have m groups to choose from.
Total Number of ways = m _ m _ m * m …. (n times) = mⁿ

Number of ways to distribute a red ball and a blue ball into a bucket and a bag such that neither is empty. { { red ball in bucket, blue ball in bag }, {blue ball in bucket, red ball in bag } }
Method 1: Using Inclusion-Exclusion Principle
- we know that we can have mⁿ ways if we allow empty groups
  from this we need to subtract number of ways in which some groups are empty.
- total ways of having empty groups can be expressed as
  no. of ways 1 group is empty - no. of ways 2 groups are empty + no. of ways 3 groups are empty - …… + (-1)^m * no. of ways m-1 groups are empty
- number of ways 1 group = ^mC₁ * (m-1)ⁿ
  ^mC₁ is the number of ways to choose any one group from m groups. And since we are left with m-1 groups number of ways to distribute is (m-1)ⁿ instead of mⁿ.
- Total ways = mⁿ - [ ^mC₁ * (m-1)ⁿ - ^mC₂ * (m-2)ⁿ + ^mC₃ * (m-3)ⁿ - …. + (-1) ^m * ^mC_m-1 * (1)ⁿ ]
  = mⁿ - ^mC₁ * (m-1)ⁿ + ^mC₂ * (m-2)ⁿ - ^mC₃ * (m-3)ⁿ + …. + (-1) ^m * ^mC_m-1 * (1)ⁿ
  
  = (i=0 to m)∑ (-1)ⁱ * ^mC_i * (m-i)ⁿ
Method 2: Using Stirlings Numbers of Second kind
- we know that Stirlings Number of Second kind is the number of ways to distribute n distinct items into m identical non-empty groups. we can multiply this number by m! which is the number of ways groups can be arranged since they are distinct.
- Total ways = m! * S(n,m)
Total ways = (i=0 to m) ∑ (-1)ⁱ * ^mC_i * (m-i)ⁿ = m! * S(n,m)

Written on October 27, 2024