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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

---

See also this answer https://math.stackexchange.com/a/362516 for a related version of Inclusion-Exclusion.

---

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}$

Answer 4

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.