Possible ways to have $n$ bounded natural numbers with a fixed sum [duplicate]

Question

Is it possible to count in an easy way the solutions of the equations and inequalities $x_1+x_2+\cdots+x_n = S$ and $x_i\leq c_i$ if all $x_i$ and $c_i$ are natural numbers?

Answer 1

We know that the number of non-negative integral solutions to the system:

$\begin{cases} x_1+x_2+x_3+\dots+x_n = S\\ 0\leq x_1\\ 0\leq x_2\\ \vdots\\ 0\leq x_n\end{cases}$

is $\binom{S+n-1}{n-1}$, seen by stars-and-bars counting. In the event that you do not consider zero to be a natural number, then it is as though you have a lower bound of $1\leq x_i$ for each so make a change of variable as $y_i=x_i-1$ to get it into the above form.

Denote all solutions where upper bounds are ignored as $\Omega$ and designate this as our universal set. With upper bounds on each, continue via inclusion-exclusion. Let $A_i\subset \Omega$ be the event that $x_i>c_i$, I.e. $x_i\geq c_i+1$. The set of solutions that you are interested in then is $(\bigcup A_i)^c$. The total being $|(\bigcup A_i)^c| = |\Omega|-|(\bigcup A_i)|$

This can be broken apart further as you wish, but becomes tedious to write in a compact formula. Counting $|A_1\cap A_2\cap A_3|$ for example will be solutions to the system:

$\begin{cases} x_1+x_2+\dots+x_n = S\\ c_1+1\leq x_1\\ c_2+1\leq x_2\\ c_3+1\leq x_3\\ 0\leq x_4\\ \vdots\\ 0\leq x_n\end{cases}~~~~~~\Leftrightarrow \begin{cases} y_1+y_2+\dots+y_n = S-c_1-c_2-c_3-3\\ 0\leq y_1\\ 0\leq y_2\\ \vdots\\ 0\leq y_n\end{cases}$

using the change of variable $y_i = x_i-c_i-1$ for $i\in\{1,2,3\}$ and $y_i = x_i$ otherwise.

An attempt to write in a compact form, using indexing set notation for intersections and sums, and letting $N=\{1,2,3,\dots,n\}$

$$\sum\limits_{\Delta\subseteq N}\left((-1)^{|\Delta|}|\bigcap_{i\in\Delta}A_i|\right) = \sum\limits_{\Delta\subseteq N}\left((-1)^{|\Delta|}\binom{S+n-1-|\Delta|-\sum\limits_{i\in\Delta}c_i}{n-1}\right)$$

of course, using that $\binom{n}{r} = 0$ whenever $n<r$ or $n<0$ or $r<0$, i.e. the original form of the binomial coefficient, not the generalized form.

Answer 2

Assume that $\sum_{i=1}^n c_i \ge S$. The Question asks about "natural numbers", so there is a bit of ambiguity about whether $x_i = 0$ is allowed. We will assume it is, but if not, then the problem may be transformed by asking for nonnegative integers $y_i = x_i - 1 \le c_i - 1$ to sum to $S-n$. Then $y_i \ge 0$ guarantees $x_i \ge 1$.

It may help to put the Question ("Is it possible to count in an easy way..."?) and the helpful expressions given by JMoravitz in context to note that this is equivalent to counting the $2$-row contingency tables where the top row (of nonnegative integers $x_i$) sums to $S$ and the bottom row to $\left(\sum_{i=1}^n c_i \right) - S$, and the $i$th column adds to $c_i$.

Dyer, Kannan, and Mount (1995), Sampling Contingency Tables, showed that such counting problems are $\#P$-complete. So, barring some unforeseen breakthrough in the theory of algorithms, these can be exponentially hard computations.

The earliest appearance of "formulas" equivalent to counting these I know of are in the papers of Percy MacMahon assembled as Combinatory Analysis in 1915.