31
$\begingroup$

I want to find the number of nonnegative integer solutions to $$x_1+x_2+x_3+x_4=22$$ which is also the number of combinations with replacement of $22$ items in $4$ types.

How do I apply stars and bars for this? What if there is an inequality or the lower bounds on the $x_i$ are not zero?

More generally, what do I use if the $x_i$ are multiplied by integer constants, such as in this equation? $$3x_1+2x_2+x_3+x_4=47$$

$\endgroup$
2
  • 2
    $\begingroup$ Do the $x_i$ need to be all positive, or just non-negative? $\endgroup$
    – amWhy
    Aug 27, 2014 at 11:39
  • $\begingroup$ Sorry, yes they are natural numbers $\endgroup$ Aug 27, 2014 at 11:41

5 Answers 5

33
$\begingroup$

Yes, the Stars-and-Bars approach works great here, but you should know that there are two "versions" of the Stars-and-Bars approach. In both versions, we look for the number of distinct integer solutions to an equation such as yours.

In the first version, we require that every $x_i$ must be a positive integer.

In the second version, the restriction eases to include all non-negative $x_i$.

So, for example in your case, $x_1= 0, x_2=9, x_3=0, x_4=13$ would be one distinct solution in the second version, but would not be a solution in the first version.

I. positive integers $x_i$

For any pair of positive integers n and k, the number of distinct k-tuples of positive integers whose sum is $n$ is given by the binomial coefficient $${n - 1\choose k-1}.$$

In your case, $k = 4, n=22$. So the number of distinct solutions $(x_1, x_2, x_3, x_4)$ where the $x_i \in \mathbb Z, x_i>0$ is given by $$\binom{22-1}{4-1} = \binom{21}{3} = \frac{21!}{3!18!} = 1330$$


II. non-negative integers $x_i$

For any pair of natural numbers n and k, the number of distinct k-tuples of non-negative integers (which includes the possibility that one or more of the $x_i$ are zero) whose sum is $n$ is given by the binomial coefficient $$\binom{n + k - 1}{n} = \binom{n+k-1}{k-1}.$$

In your problem, $k = 4, n = 22.$ Here, the distinct solutions $(x_1, x_2, x_3, x_4)$ will include those from $I.$, but also allows 4-tuples in which one or more of the $x_i$ are zero: $x_i \in \mathbb Z, x_i\geq 0$.

$$\binom{22 + 4 -1}{22} = \binom{25}{22} = \dfrac{25!}{22!3!} = 2300$$

$\endgroup$
5
  • $\begingroup$ Could you help me with my newer stars and bars problem? Noone has seen it $\endgroup$ Aug 28, 2014 at 12:52
  • 1
    $\begingroup$ Isn't the formula (n+k-1) choose k and not choose n? The equivalent would be (n+k-1) choose (n+k-1-k = n-1)? $\endgroup$
    – thbcm
    Feb 21, 2015 at 22:54
  • $\begingroup$ See how I've defined n, k. See Wikipedia $\endgroup$
    – amWhy
    Feb 21, 2015 at 23:36
  • 1
    $\begingroup$ @inggumnator No, sorry. I think you're mixing up $n$ and $k$. The desired sum is $n$; $k$ is the number of $x_i$ (variables) whose sum is $n$. Go to the link I've posted above to re-educate yourself. Note that $$\binom{n+k-1}{n} = \binom{n+l -1}{k-1}$$ $\endgroup$
    – amWhy
    Dec 2, 2016 at 22:39
  • 1
    $\begingroup$ How did you decide what is $n$ and what is $k$? $\endgroup$
    – Archer
    Dec 18, 2017 at 8:55
19
$\begingroup$

The star method: consider 22 balls and 3 separations (because you have 4 boxes). I denote $*$ for the balls and $\Big |$ for the separation. Then it's the number of permutation of:

$$\left\{\underbrace{*\ *\ \cdots *\ }_{22\ balls}\Big|\hspace{0.5cm}\Big|\hspace{0.5cm} \Big|\hspace{0.5cm}\right\}$$

There is $25!$ permutations but the permutation of the balls together and the permutations of the separation together doesn't give a new combinaison, so you have to divide $25!$ by $3!22!$ and it gives $$\frac{25!}{3!22!}=\binom{25}{3}$$ different solutions.

$\endgroup$
5
  • 1
    $\begingroup$ To me, $\mathbb N=\{0,1,2,3,...\}$ and so $0\in\mathbb N$. If $0$ wouldn't be included, he would write $x_i\in\mathbb N^*$. $\endgroup$
    – idm
    Aug 27, 2014 at 13:30
  • $\begingroup$ @idm Did you know how to solve my newest question? It is a continuation of this one $\endgroup$ Aug 28, 2014 at 8:35
  • $\begingroup$ What is the new question ? I don't see it. $\endgroup$
    – idm
    Aug 28, 2014 at 8:37
  • $\begingroup$ @idm math.stackexchange.com/questions/911618/… $\endgroup$ Aug 28, 2014 at 8:43
  • $\begingroup$ can you extend this answer for N* using same logic? $\endgroup$
    – Fawad
    Nov 2, 2019 at 16:09
7
$\begingroup$

How to use the stars and bars method?

For $x_i\ (i=1,2,3,4)\in\mathbb N$, we have $$x_1+x_2+x_3+x_4=22\iff (x_1-1)+(x_2-1)+(x_3-1)+(x_4-1)=18.$$

Here, note that $x_i-1\ (i=1,2,3,4)$ are non-negative integers.

Choosing $4-1=3$ places (for bars) from $18+(4-1)$ places (for bars and stars) leads the answer is $\binom{18+(4-1)}{4-1}=\binom{21}{3}=1330.$

$\endgroup$
5
  • $\begingroup$ Why does your answer differ to that of idm? $\endgroup$ Aug 27, 2014 at 12:28
  • $\begingroup$ @user1341841914820412812412: If I'm note mistaken, idm thinks that $x_i$ are non-negative integers. $\endgroup$
    – mathlove
    Aug 27, 2014 at 12:30
  • $\begingroup$ So he has permitted $0$, and you have not? $\endgroup$ Aug 27, 2014 at 12:30
  • $\begingroup$ @user1341841914820412812412: Yes, exactly. $\endgroup$
    – mathlove
    Aug 27, 2014 at 12:30
  • $\begingroup$ That's fine, having the contrast is actually quite nice. $\endgroup$ Aug 27, 2014 at 12:32
3
$\begingroup$

Inequalities

To count nonnegative integer solutions of $$x_1+x_2+x_3+x_4\le22$$ add a slack variable $x_5$ to the left-hand side representing the gap between $x_1+x_2+x_3+x_4$ and $22$, which is by definition nonnegative: $$x_1+x_2+x_3+x_4+x_5=22$$ Stars and bars then gives $\binom{22+4}4=14950$ solutions.

General bounds

To count integer solutions of $$x_1+x_2+x_3+x_4=22$$ with $-2\le x_1\le7$ and all other $x_i$ bounds unchanged from the basic problem, first add $2$ to both sides and set $y=x_1+2$ with $0\le y\le9$: $$y+x_2+x_3+x_4=24$$ Without $y$'s upper bound, stars and bars gives $\binom{24+3}3=2925$ solutions. We need to remove solutions with $y\ge10$; we count these unwanted solutions like the lower bound case, by defining another nonnegative integer variable $z=y-10$ and simplifying: $$z+x_2+x_3+x_4=14$$ There are $\binom{14+3}3=680$ solutions to this, so the final answer is $2925-680=2245$.

Multiple nonzero lower bounds can be handled independently. Multiple upper bounds need to be handled using inclusion–exclusion. In particular, the number of ways $n$ ordered dice with faces from $0$ to $k-1$ can sum to $b$ is $$\sum_{i=0}^n(-1)^i\binom ni\binom{b-ki+n-1}{n-1}$$


Generating functions

Both of the above generalisations are themselves special cases of the generating function method, where the number of solutions to $\sum_ia_ix_i=n$ is found as the $x^n$ coefficient of a polynomial or power series whose factors encode information about a corresponding monomial.

A monomial $a_ix_i$ where $0\le p\le x_i\le q$ and $a_i$ is a constant positive integer corresponds to the factor $$\sum_{k=p}^q(x^{a_i})^k=(x^{a_i})^p\frac{1-(x^{a_i})^{q-p+1}}{1-x^{a_i}}$$ where $x^{q-p+1}$ disappears if $q=\infty$. For example, the number of nonnegative integer solutions to $3x_1+2x_2+x_3+x_4=47$ is the $x^{47}$ coefficient of $$\frac1{(1-x^3)(1-x^2)(1-x)^2}$$ which is $3572$.

Modular considerations may help to simplify such a problem. The number of nonnegative integer solutions to $x_1+5x_2+10x_3+25x_4+50x_5+100x_6=147$ equals the number of nonnegative integer solutions to $x_2+2x_3+5x_4+10x_5+20x_6\le29$, because $x_1$ must be of the form $5k+2$, because all other multipliers are divisible by $5$.

$\endgroup$
3
  • $\begingroup$ [+1] Interesting. $\endgroup$
    – Jean Marie
    Sep 25, 2022 at 7:16
  • $\begingroup$ I appreciate the idea of turning this question into an abstract duplicate for all stars-and-bars question, BUT I think you made it a little too general. I think that this question should only address counting $x_1+\dots+x_k=n$, with lower limits $x_i\ge b_i$. The other part of the question, counting $a_1x_1+\dots+a_kx_k=n$, could be handled in a separate question, like this one. The two versions are so different, that it is awkward to have them in the same place. Do you disagree? $\endgroup$ Sep 17, 2023 at 18:22
  • $\begingroup$ [Generating Functions] How were you able to compute the coefficient of $x^{47}$ in $\frac{1}{(1−x^3)(1−x^2)(1−x)^2}$? $\endgroup$ Mar 5 at 11:20
2
$\begingroup$

My answer specifically deals with the last question, of counting nonnegative integer solutions to $$ a_1x_1+\dots+a_kx_k=n,\\ x_i\in\mathbb Z_{\ge 0},\quad i\in \{1,\dots,k\} $$ Let $h_n$ be the number of solutions to the above (the dependence on $k,a_1,\dots,a_k$ is suppressed to simplify notation). We can give an exact expression for $h_n$ using generating functions: $$ h_n=[t^{n}]\frac{1}{(1-t^{a_1})(1-t^{a_2})\cdots (1-t^{a_k})} $$ Here. $[t^n] f(t)$ means the coefficient of $t^c$ when $f$ is expanded as a power series centered at $t=0$. To see why this works, note that $(1-t^{a_i})^{-1}=\sum_{x_i=0}^\infty t^{a_ix_i}$, so $$ \prod_{i=1}^k (1-t^{a_i})^{-1} =\sum_{x_1=0}^\infty\sum_{x_2=0}^\infty \cdots \sum_{x_k=0}^\infty t^{a_1x_1+\dots+a_kx_k} $$ This means there is a contribution to $t^n$ for each way to write $n$ as $a_1x_1+\dots+a_kx_k$.

This gives a method to compute $h_n$ using a computer algebra system. Here is a piece of Mathematica code which computes $h_n$:

CoinGeneratingFunction[t_, CoinList_] := 
    1 / Product[(1 - t ^ CoinList[[i]]), {i, 1, Length[CoinList]}]
NumWaysMakeChange[TargetAmount_, CoinList_] := 
    SeriesCoefficient[ CoinGeneratingFunction[t, CoinList], {t, 0, TargetAmount}]

TargetAmount = 1000;
CoinList = List[2,3,6,8];

Print["There are ", NumWaysMakeChange[TargetAmount , CoinList], 
    " ways to make change for ", TargetAmount, 
    " using coins with values ", CoinList, "."]

See also my question on computer science stack exchange for more methods to compute $h_n$.

Thanks to Schur's theorem, we have a simple asymptotic expression for the number of solutions.

Schur's Theorem: As $n\to\infty$, $$h_n= \frac{n^{k-1}}{(k-1)!(a_1\cdot a_2 \cdots a_k)}(1+o(1)).$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .