Number of combinations with sets of identical items

Question

I was trying to write a python program which takes a string and prints out all possible combinations of characters from it and in turn figure out the number of such possible combinations of a string to verify it's correctness

This made me think about the following problem: Given N total objects of k distinct kinds such that for i = 1 to k, r_i objects are of the same kind, what are the total number of combinations of containing R objects?

The problem of permutations containing all N objects is much simpler and intuitive, however, I am interested in R < N.

I did some research and could only find this article discussing the problem, where it was suggested that the answer would be the coefficient of x^R in the following equation:

(1+x+x²+..+x^r₁)(1+x+x²+..+x^r₂).....(1+x+x²+..+x^r_k)

Is this the only way to solve this problem? Also how would one solve the problem when the combination length is specified to be at most R instead of exactly R?

Answer 1

All methods of solving the problem are equivalent to finding the appropriate coefficient in the polynomial. It is possible, using elementary algebra, to construct a formula with no more than $2^k$ terms (as shown below), but simply multiplying out the original polynomial is usually easier and less error-prone.

The given polynomial is $$\prod_{i=1}^k1+x+x^2+\cdots+x^{r_i}=\prod_{i=1}^k\frac{1-x^{r_i+1}}{1-x}=(1-x)^{-k}\prod_{i=1}^k1-x^{r_i+1}$$

Now, $$(1-x)^{-k}=\sum_{i=0}^\infty\binom{k-1+i}ix^i$$

and $$\prod_{i=1}^k1-x^{r_i+1}=\sum_{S\subset\{r_1\cdots r_k\}}(-1)^{|S|}x^{\sum_{\alpha\in S}(\alpha+1)}$$ which means $1$, minus all $x^{r_i+1}$ taken one at a time, plus all $x^{r_i+r_j+2}$ taken two at a time, minus all $x^{r_i+r_j+r_k+3}$ taken three at a time, etc.

Putting it together, let $U_n$ be the multiset of all submultisets $S$ of $\{r_1+1,r_2+1,\cdots r_k+1\}$ such that the sum $s(S)=\sum_{\alpha\in S}\alpha$ is always less than or equal to $n$. Then the formula is $$\sum_{S\in U_n}(-1)^{|S|}\binom{k-1+n-s(S)}{n-s(S)}$$ which is equivalent to the one given by san.

In the example of $r_1=2,\ r_2=1,\ r_3=2,\ n=3$ we get $U_3=\{\emptyset,\{3\},\{2\},\{3\}\}$ and $$\binom53-\binom20-\binom31-\binom20=10-1-3-1=5$$ as expected.

Instead of all that, we could just multiply out in a tableau. For example, take the $r$-values $5,3,2$:

$$\begin{array}{ccccccccccc}1&1&1&1&1&1\\1&2&3&4&4&4&3&2&1\\1&3&6&9&11&12&11&9&6&3&1\end{array}$$ The first row $(A_{1,j})$ contains $r_1+1$ ones. For $i>1$, the $i$th row is formed by summing each group of $r_i+1$ adjacent numbers in the preceding row: $$A_{i,j}=\sum_{k=0}^{r_i}A_{i-1,j-k}$$assuming everything out-of-range to be zero. For example, the third row is formed as $$0+0+1,\ 0+1+2,\ 1+2+3,\ 2+3+4,\ 3+4+4,\ 4+4+4,\ldots$$

Immediately we can read off that there are $11$ combinations of $6$ objects, etc. In Python you could write something like newrow = [sum(row[max(0,i-r):i+1]) for i in range(len(row)+r)]

Answer 2

I think the presentation as coefficients of that polynomial is the simplest possible answer. A more geometric presentation is as the number of integer points of the intersection of the hyperplane $\mathcal{P}: x_1+\dots+x_k=R$ in $\Bbb{R}^k$ with the parallelepiped $I_1\times\dots\times I_k$, where $I_i=[0,r_i]$. That is, $$ \# \ \Bbb{N}_0^k\cap (I_1\times\dots\times I_k) \cap \mathcal{P} $$

$\textbf{EDIT:}$

From this geometric interpretation one can get a combinatoric expresion for the number, which we will call $N(r_0,\dots,r_k,R)$. For this, it is convenient to consider $k+1$ sets, with $r_0,\dots,r_k$ elements respectively (it makes the formula look nicer). Then define $$ F=\{J\subset \{0,\dots,k\}, \text{such that } S_J:=\sum_{i\in J}r_i\le R-|J|\}, $$ and we have $$ N(r_0,\dots,r_k,R)=\sum_{J\in F}(-1)^{|J|}\binom{R-S_J-|J|+k}{k} $$

You can verify the formula for example in the case that for all $i$ we have $r_i\ge R$, where it gives the correct number $\binom{R+k}{k}$ (since $\emptyset\in F$ and $S_{\emptyset}=0$); and also in the case where only one $r_i<R$ (lets assume for example $r_0$), where it gives the correct number $\binom{R+k}{k}-\binom{R-r_0-1+k}{k}$.

The idea of the proof is that you start with a $k$-simplex with $\binom{R+k}{k}$ integer points and each $r_i<R$ cuts out a smaller $k$-simplex (of sidelength $R-r_0-1$), which you have to substract, but if $r_i+r_j\le R-2$, then you have to add the points in a smaller $k$-simplex (with sidelength $R-(r_i+r_j)-2$), which you have substracted twice and you continue with the same method for all $J\in F$.

With regard to the question "Also how would one solve the problem when the combination length is specified to be at most R instead of exactly R", note that $$ \sum_{r=0}^{R}N(r_0,\dots,r_k,r)=N(r_0,\dots,r_k,R,R). $$

Answer 3

You start the post by mentioning string, i.e words, which formally are considered distinct also according to the order of their characters.
Then you put the question "Given N total objects of k distinct kinds such that for i = 1 to k, ri objects are of the same kind, what are the total number of combinations of containing R objects?" and citing the answer in the reference you found, it seems that you are actually interested in the number of subsets with limited repetition, where the order of the elements does not matter, e.g. $\{ACAB\}=\{AABC\}$.

I am developing my answer according to the latter assumption.

If the $r_i$ were all equal to $r$, then the solution would given by $N_b(R,r,k)$ where $$ \bbox[lightyellow] { N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right. } \tag{1} $$ and $$ \bbox[lightyellow] { N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m \hfill \\ k \hfill \\ \end{gathered} \right)\left( \begin{gathered} s + m - 1 - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} } \tag{2} $$ whose z-Tranform is in fact $$ \bbox[lightyellow] { F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)^m } \tag{3} $$ as explained in this other post.

If the $r_i$ assume only two values $r_1$ and $r_2$, and there are $k_1$ and $k_2$ distinct sets in each class, then $$ \bbox[lightyellow] { F_b (x,r_{\,1} ,r_{\,2} ,k_{\,1} ,k_{\,2} ) = \left( {1 + x + \cdots + x^{\,r_{\,1} } } \right)^{\,k_{\,1} } \left( {1 + x + \cdots + x^{\,r_{\,2} } } \right)^{\,k_{\,2} } } $$ and you can get the coefficients by operating the convolution in $s=R$ of the two respective $N_b$'s.
Same scheme if the $r_i$'s can be grouped into a "few" different values.

If instead there are "many" $r_i$'s, and quite scattered in value, then from the computational point of view you have better and obtain the coefficients from the convolution of the $k$ binary strings $$ \bbox[lightyellow] { \left[ {0 \le n \le r_{\,i} } \right] } $$ where $[P]$ is the Iverson bracket $$ \bbox[lightyellow] { \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. } $$

I am not aware of a closed formula for that.

However, depending on the actual application, on the distribution of the $k$'s and $r$'s values, etc. the binary strings may be considered as discrete (in the limit $\to$ continuous) sequences, that is as unit square pulses of duration $r_i$ (or $r_{i}+1$, depending on how the $0$-th term is accounted for).
So they may be considered as the sum of two Heaviside functions, or the integral of two Delta functions, and be manipulated via Fourier or Laplace transform. That helps to obtain some asymptotic expansions, and in any case the inverse transform of the product of the single terms is providing a global formula.

Finally, for large $k$ the problem will approach that of the sum of many casual variables, uniformly distributed over the interval $[0,r_i]$ and so can be handled with the instruments of Probability Theory.