7
$\begingroup$

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, ri 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 xR in the following equation:

(1+x+x2+..+xr1)(1+x+x2+..+xr2).....(1+x+x2+..+xrk)

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?

$\endgroup$
  • 2
    $\begingroup$ For at most $R$, just sum all the coefficients of $x^k$ for $k\le R$. $\endgroup$ – Daniel Robert-Nicoud Jun 21 '17 at 19:43
  • $\begingroup$ Surely that would work, but I was looking for a different approach. $\endgroup$ – Erric Jun 21 '17 at 20:22
  • $\begingroup$ Another way to formulate essentially the same idea is the following: the number of combinations of $R$ objects equals to the number of ways to partition $R$ into $k$ summands $R = s_1 + s_2 + \cdots + s_k$ subject to $0 \le s_i \le r_i$. $\endgroup$ – Smylic Jun 23 '17 at 13:43
  • $\begingroup$ Yes, as s1,s2,etc. simply stands for how many are selected from each class. But is there a direct formula? Surely this is not a first of its kind problem? $\endgroup$ – Erric Jun 24 '17 at 13:00
  • 2
    $\begingroup$ For at most R, introduce a (k+1) th dummy object, that can take values 0 thru R, and solve as before. $\endgroup$ – true blue anil Jun 27 '17 at 4:37
3
$\begingroup$

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)]

$\endgroup$
  • $\begingroup$ Interesting, but I could not understand the tableu. Could you give an expression for the element in the ith row and jth column, rij? $\endgroup$ – Erric Jun 28 '17 at 7:37
  • 1
    $\begingroup$ I have added more detail. $\endgroup$ – Andrew Woods Jun 28 '17 at 8:04
2
+50
$\begingroup$

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). $$

$\endgroup$
  • $\begingroup$ Good one, but I was looking for a confirmation that there's no direct formula that yields the result or an interpretation that leads to one if it exists. My combinatorics is a little rusty, so I want to be sure that I'm not missing anything – $\endgroup$ – Erric Jun 27 '17 at 8:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Appreciate the insights. But I was already discussing the problem where the ri were distinct. Also strings are not necessarily words when it comes to programming and I mention "all possible combinations of characters" (not permuatations). Here's the program I wrote: repl.it/IxHz/2 $\endgroup$ – Erric Jun 27 '17 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.