# How can I count solutions to $x_1 + \ldots + x_n = N$?

I am interested in how many non-negative integer solutions there are to:

$$x_1 + \ldots + x_N = B$$

where at least $K$ of the variables $x_1, \ldots , x_N \geq C$

For example when: $B = 5, N = 3, K = 2, C = 2$

I want to count the solutions to:

$$x_1 + x_2 + x_3 = 5$$

where at least $2$ of the variables are $\geq 2$.

I found the total number of candidate solutions using the $\binom{B+N-1}{B} = 21$

However, only $9$ of them have two variables $\geq 2$.

\begin{align*} 2+0+3& =5\\ 2+1+2& =5\\ 3+0+2& =5\\ 1+2+2& =5\\ 3+2+0& =5\\ 0+2+3& =5\\ 0+3+2& =5\\ 2+3+0& =5\\ 2+2+1& =5 \end{align*}

I feel there is a connection to the Associated Stirling numbers of the second kind. But I can't place it :(

EDIT:

Here is my code for enumerating them all to count the number of ways of select B elements from a set of N (uniformly with replacement), such that you have at least C copies of K elements - also shows the output for this question I'm asking here as it's the core piece. Obviously can't be run for very large values of the parameters - that's why I'm here :) Code is here

Here is another example for B = 6, N = 3, C = 2 and K = 2 there are 16 solutions:

\begin{align*} 0+2+4& = 6\\ 0+3+3& = 6\\ 0+4+2& = 6\\ 1+2+3& = 6\\ 1+3+2& = 6\\ 2+0+4& = 6\\ 2+1+3& = 6\\ 2+2+2& = 6\\ 2+3+1& = 6\\ 2+4+0& = 6\\ 3+0+3& = 6\\ 3+1+2& = 6\\ 3+2+1& = 6\\ 3+3+0& = 6\\ 4+0+2& = 6\\ 4+2+0& = 6\\ \end{align*}

There are a number of different and correct solutions below. I don't know which to accept.

• Please read this tutorial on how to typeset mathematics on this site. Dec 28, 2015 at 19:16
• @nickponline I have a result now, can you check it?
– mvw
Dec 28, 2015 at 21:47
• Sure will check it now. I have some code for enumerating all the solutions Dec 28, 2015 at 23:20

Without loss of generalization, let us consider $x_1,x_2,\ldots,x_k \geq C$.

Then let

$$y_i = \begin{cases}x_i - C &i\leq k\\ x_i & i > k \end{cases}$$

Solving

$$\left\{\begin{array}[lll] xx_1 + x_2 + \ldots + x_n &=& N\\ x_i \geq 0& & \\ x_1,x_2,\ldots,x_k& \geq & C\end{array}\right.$$ is equivalent to just solving $$\left\{\begin{array}[lll] yy_1 + y_2 + \ldots + y_n &=& N-kC\\ y_i \geq 0& &\end{array}\right.$$ The number of solutions excluding permutations is the number of partitions of $N-kC$ into $m$ integers where $m \leq n$.

For each of this solutions, adding $C$ to $k$ of them would yield a solution of your original problem. There are $n\choose k$ ways to do thus but we are overcounting some solutions if there are $i,j$ such that $y_i = y_j$ or if $y_i + C = y_j$. For each of this solutions we have at most $n!$ distinct solutions (including permutations), again we are overcounting some if there are $i,j$ such that $y_i = y_j$ or if $y_i + C = y_j$. This gives us a somewhat close upper bound on the amount of solutions:

$${n\choose k} n!\sum_{m=1}^n P_m(N-kC)$$

• But this example includes permutations since $(x_1, \dots, x_n)$ is an ordered pair. Order matters here. (Hence the discussion of partitions is also not needed)
– MT_
Dec 28, 2015 at 18:10
• Also, as I say on the other post, it's not so easy to just say "without loss of generality" and assume $x_1, \dots, x_k \geq C$. Since they're ordered, you also have to consider cases where different variables are included in the "at least K." And, this is NOT so easy as just multiplying the term by ${n \choose k}$ since this causes double counting when $N - CK > C$.
– MT_
Dec 28, 2015 at 18:12
• Is there a way to exclude the double counted solutions by find an expression for them and subtracting it? Dec 28, 2015 at 19:38

A tailor-made approach by analytic combinatorics. The coefficient of $x^B$ in

$$\frac{1}{(1-x)^N} = \left(1+x+x^2+x^3+\ldots\right)^N$$ obviously counts the number of ways of representing $B$ as a sum of $N$ non-negative integers. By stars and bars, or by the (negative) binomial theorem, such number is $\binom{N+B-1}{N-1}$. We may use an extra variable to mark the terms with exponent $\geq C$, and consider: $$g(z,x) = \left(1+x+x^2+\ldots+x^{C-1}+ z x^{C}+z x^{C+1}+ z x^{C+2}+\ldots\right)^N$$ that is: $$g(z,x) = \left(\frac{1-x^C}{1-x}+z\cdot\frac{x^C}{1-x}\right)^N = \frac{(1+(z-1) x^C)^N}{(1-x)^N}.$$ Now the coefficient of $x^B$ in $g(z,x)$ is a polynomial in the $z$ variable, $h_B(z)$, and we are interested in summing the monomials of $h_B(z)$ whose degree is $\geq K$. That sum evaluated at $z=1$ gives the answer to our problem. However, I suspect there is no nice closed formula for summarizing the process, since even the computation of $h_B(z)$ involves a convolution. Are you fine with an integral representation of the answer? That is not hard to achieve through Cauchy's integral formula.

If $B=5,N=3, C=2$ and $K=2$, we have $h_B(z)=12z+\color{red}{9}z^2$, hence the answer is $\color{red}{9}$ as you checked. The general form of the answer is given by:

$$\begin{eqnarray*} [x^B]\sum_{D\geq K}[z^D]\frac{\left((1-x^C)+z x^C\right)^N}{(1-x)^N}&=&[x^B]\frac{1}{(1-x)^N}\sum_{D\geq K}\binom{N}{D}x^{CD}(1-x^C)^{N-D}\\&=&\sum_{D\geq K}\binom{N}{D}[x^{B-CD}]\frac{(1-x^C)^{N-D}}{(1-x)^N}\\&=&\color{red}{\sum_{D\geq K}\binom{N}{D}\sum_{h=0}^{N-D}\binom{N-D}{h}(-1)^h\binom{N+B-CD-Ch-1}{N-1}}, \end{eqnarray*}$$

rather ugly.

• @mvw: not so much, once one may learn from the best: math.upenn.edu/~wilf/DownldGF.html Dec 29, 2015 at 1:10
• Wow, I wanted to remark that the originality of its title is akin to the "A=B" book, and now I see it is from the same author. Sad to see he passed.
– mvw
Dec 29, 2015 at 1:24
• This is interesting. Just give me a minute to work through it :) Dec 29, 2015 at 1:33
• @nickponline: oh, wait, I got it. Here I am using the convention that $\binom{a}{b}$ equals zero if $a<b$, but that is not universal, for instance Mathematica returns $-4$ for $\binom{-2}{3}$. That makes sense if we think to $\binom{a}{b}$ as a polynomial with degree $b$ in the $a$ variable, but here I am using the "counting definition" of the binomial coefficient. Dec 29, 2015 at 1:49
• @nickponline: the Mathematica command $$\sum _{E=2}^3 \text{Binomial}[3,E]\sum _{h=0}^{3-E} \text{Binomial}[3-E,h](-1){}^{\wedge}h \text{Binomial}[3+6-2 E-2 h-1,2]\text{HeavisideTheta}[6-2 E-2 h+1/2]$$ returns the right answer, $16$. I modified the definition of the binomial coefficient in order to have $\binom{a}{b}=0$ for $a<b$. Dec 29, 2015 at 2:09

Let $A_i$ be the set of solutions in nonnegative integers to $x_1+\cdots+x_n=B$ with $x_i\ge C$, for $1\le i\le n$,

and let $T_l=\sum\big|A_{i_1}\cap\cdots\cap A_{i_l}\big|$, where the sum is taken over all $l$-subsets of $\{1,\cdots,n\}$, for $1\le l\le n$.

Using Inclusion-Exclusion, the number of elements in at least k of $A_1,\cdots,A_n$ is given by

$\displaystyle\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}T_i=\color{blue}{\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}\binom{n}{i}\binom{B-Ci+n-1}{n-1}}$

since $T_i$ is the sum of $\binom{n}{i}$ terms, each of which has the value $\binom{B-Ci+n-1}{n-1}$.

Here are a few examples, which have been verified by considering cases:

$\textbf{1)}$ $B=6, n=3, C=2, k=2$:

$\displaystyle\sum_{i=2}^3(-1)^{i-2}\binom{i-1}{1}\binom{3}{i}\binom{8-2i}{2}=\binom{1}{1}\binom{3}{2}\binom{4}{2}-\binom{2}{1}\binom{3}{3}\binom{2}{2}=18-2=\color{blue}{16}$

$\textbf{2)}$ $B=12, n=5, C=4, k=2$:

$\displaystyle\sum_{i=2}^5(-1)^{i-2}\binom{i-1}{1}\binom{5}{i}\binom{16-4i}{4}=\binom{1}{1}\binom{5}{2}\binom{8}{4}-\binom{2}{1}\binom{5}{3}\binom{4}{4}=700-20=\color{blue}{680}$

$\textbf{3)}$ $B=18, n=6, C=3, k=4$:

$\displaystyle\sum_{i=4}^6(-1)^{i-4}\binom{i-1}{3}\binom{6}{i}\binom{23-3i}{5}=\binom{3}{3}\binom{6}{4}\binom{11}{5}-\binom{4}{3}\binom{6}{5}\binom{8}{5}+\binom{5}{3}\binom{6}{6}\binom{5}{5}=\color{blue}{5,596}$

• What are c_i values? Dec 28, 2015 at 23:49
• sorry - I had a slight typo; (I have only checked it in the case you gave, and the case B=12, n=5, k=2, C=4) Dec 28, 2015 at 23:50
• In my example C is 2 does this mean all the C_i are 2 as well? Dec 28, 2015 at 23:51
• No, the last factor in this case is $\binom{5-2i+2}{2}=\binom{7-2i}{2}$ Dec 28, 2015 at 23:53
• Ah i see sorry i though it was a subscript Dec 28, 2015 at 23:59

You could move to new variables $x_i' = x_i - C \ge 0$ for the variables with the minimum value $C$. Then the equation transforms to $$x'_1 + \ldots x'_K + x_{K+1} + \ldots x_N = B - K \, C$$ assuming WLOG GRUMBL MUMBL that those variables are the first $K$ ones.

This is a problem of the form $$n_1 + \ldots + n_N = n \quad (n_i \ge 0) \quad (*)$$ which is related to compositions from combinatorics. A composition of $n$ is a way to write $n$ as sum of integers $n_i \ge 1$. We need weak composition of $n$, which allows terms $n_i \ge 0$, but only those which have $N$ terms. The number of compositions of $n$ into $N$ parts is $\binom{n-1}{N-1}$, the number of weak compositions of $n$ into $N$ parts follows from looking at the number of compositions of $n+N$ into $N$ parts (and subtracting $1$ for each of the $N$ parts on both sides), so equation $(*)$ has $$\binom{n+N-1}{N-1} = \binom{B-K\,C+N-1}{N-1}$$ solutions.

Your example turns into $$x'_1 + x'_2 + x_3 = 5-2\cdot 2 = 1$$ and should have $\binom{1+3-1}{3-1}=\binom{3}{2}=3!/(2!1!)=3$ solutions. We find $$(x'_1, x'_2, x_3) \to (x_1, x_2, x_3) \\ (1,0,0) \to (3,2,0) \\ (0,1,0) \to (2,3,0) \\ (0,0,1) \to (2,2,1)$$ The found solution in $x'_i$ has then to be transformed back via $x_i = x'_i + C$, see the right side above.

Update: The above assumed the constraints were at fixed positions and attached the constraints $x_i \ge C$ to the variables $1$ to $K$. It should be clear that if the constraints were assigned to a different subset of variables indexed by $I = \{ I_1, \ldots, I_K \} \subset \{1, \ldots, N \}$ we end up with the same solutions, albeit permutated, along to the permutation of the indices.

E.g. for the example we have: $$(x_1, x'_2, x_3') \to (x_1, x_2, x_3) \\ (1,0,0) \to (1,2,2) \\ (0,1,0) \to (0,3,2) \\ (0,0,1) \to (0,2,3)$$ and $$(x_1', x_2, x_3') \to (x_1, x_2, x_3) \\ (1,0,0) \to (3,0,2) \\ (0,1,0) \to (2,1,2) \\ (0,0,1) \to (2,0,3)$$ These are all $9$ solutions.

What we need here are combinations, as we are interested only in the chosen subset, not in what order the elements were chosen. There are $\binom{N}{K}$ $K$-combinations from a set of $N$ elements.

Note: This part needs $C \ge 1$, otherwise the resulting tuples are not distinct. There might be further conditions to watch, to justify this factor, see the comments.

Result:

There should be $$\binom{N}{K} \binom{B-K\,C +N-1}{N-1}$$ solutions to the original problem. Caution: This might degrade to an upper bound, see the comments.

• But the variables are different, no? So going with $(x_1, x_2, x_3)$ with $2$ of them greater than $2$ and sum equals to 5, the answers (2, 2, 1) and (1, 2, 2) are different. And you can't just multiply the whole thing by ${n \choose k}$ since that will certainly cause double-counting in situations where $B - KC > C$.
– MT_
Dec 28, 2015 at 18:07
• I'm saying your answer is not taking into account order, essentially. You're missing many solutions, namely (1, 2, 2), (0, 2, 3), (0, 3, 2), (2, 1, 2), (2, 0, 3), (3, 0, 2).
– MT_
Dec 28, 2015 at 18:18
• And you may be tempted to multiply your number by ${n \choose k}$ but this leads to double-counting (not in this particular situation, since $B - KC < C$.
– MT_
Dec 28, 2015 at 18:19
• Agreed. The WLOG needs to be explained more... though this might be in a right direction. Dec 28, 2015 at 19:05
• @Soke Despite the two warnings I could not resist :-) Do you have a nice example which can illustrate the problem? I need a break and try later to understand, why you deem $B - KC$ vs $C$ critical.
– mvw
Dec 28, 2015 at 22:14