What are the number of ways of distributing n objects(mixture of distinct and identical objects) into r groups of different sizes?

Question

Example: lets say each object can be identified by a unique numerical I.D.

What are the number of ways of distributing 1,1,1,1,1,0,0,2,2,2,3 into 4 groups of size 4,2,2 and 3.

Answer 1

Your question is equivalent to the counting the matrices with prescribed sums of rows and columns, which can be formulated as:

Given two vectors $M=(M_1,M_2,\dots, M_m)$ and $N=(N_1,N_2,\dots, N_n)$ with positive integer elements $M_i,N_i>0$, such that $$\sum_{i=1}^mM_i=\sum_{j=1}^nN_j$$ how many $m\times n$ matrices with non-negative integer elements $A_{ij}\ge0$ do exist, such that $$\sum_{j=1}^n A_{ij}=M_i\text{ and } \sum_{i=1}^m A_{ij}=N_j.$$

The matrices are often referred to as 2-way contingency tables. In your problem $m$ and $n$ are the number of different object types and that of groups, respectively.

Unfortunately the above question has no simple answer. For example in a quite recent paper the authors state:

The enumeration of integer-matrices has been the subject of considerable study and it is unlikely that a simple formula exists.

On the other hand for small matrices the recursive calculation of the number of possible distributions does not represent a problem. The following Mathematica code:

count[a_,b_]:=Module[{c},
  If[Length[b]==1,1,c=Select[Combinatorica`Compositions[b[[1]],Length[a]],Min[a-#]>=0&];
  Sum[count[a-c[[i]],b[[2;;]]],{i,Length[c]}]]
]

gives for your example the answer:

count[{1,2,3,5},{2,2,3,4}]
431

Answer 2

By Polya.

Suppose we have four sorts of objects denoted by $$e, i, h, l$$ that come in the quantities of 1, 2, 3 respectively 5 items.

then a group may contain (without the size restriction)

$$ group := (1+we)(1+wi+w^2i^2)(1+wh+w^2h^2+w^3h^3)(1+wl+\cdots+w^5l^5) $$

where $w$ is a counter (weight) for the number of items, independently of their sort.

First group has 4 items so we are interested in

$$ group_1 := coeff (group, w^4) $$

and for the rest of the groups

$$ group_2 := coeff (group, w^2) $$ $$ group_3 := coeff (group, w^2) $$ $$ group_4 := coeff (group, w^3) $$

The whole partition is described by

$$partition := group_1\cdot group_2\cdot group_3\cdot group_4$$

We are now interested in

$$coeff (e^1 i^2h^3l^5, partition)$$

which indicates the number of configurations that contains 1,2,3 and 5 given items and it is $431$

See also Spelling Bee - real combinatorics example