A question about the Pigeonhole Principle and linear equations over $\mathbb{Z}$

Question

This may be a bit trivial (apologies if it is), but I was wondering if there was an elementary way to compute the cardinality of the solution set in the following situation:

How many solutions would exist to the equation $$2a + 2b + 4c + 4d = 8$$ if $a,b,c,d$ are distinguishable nonnegative integers?

---

Just to clarify, when I say "distinguishable", I mean that even if $a = b$, they represent different objects, and thus the solutions $(2,0,1,0)$, $(2,0,0,1)$, $(0,2,1,0)$, and $(0,2,0,1)$ are all distinct.

---

My real question, for which the trivial case above is just a motivating example, is:

More generally, if we are given $r$ strictly positive integers $p_1,\ldots,p_r$ (not necessarily distinct), how many solutions exist to the following equation for some moderately large $n\in\mathbb{N}$? $$\sum_{i=1}^r p_i a_i = n$$ if $a_1,\ldots,a_r$ are distinguishable nonnegative integers?

---

I want to say that this is related to the pigeonhole principle, because using that, I was able to count exactly 14 such solutions in the trivial case of 4 nonnegative integers. That being said, I'm not sure about the more general case.

Answer 1

There's a simple recursive algorithm to compute this. Let $N(p_1,\ldots,p_r,n)$ be the number of nonnegative integer solutions to $\sum\limits_{i=1}^r p_ia_i=n$. Then $$\begin{align} N(p_1,n) &=\begin{cases}1&\text{if } p_1\mid j\\ 0&\text{otherwise}\end{cases} \\ N(p_1,\ldots,p_r,n) &= \sum_{j=0}^{\lfloor n/p_r\rfloor}N(p_1,\ldots,p_{r-1},n-p_rj) \end{align}$$ While naive implementation of this algorithm has exponential runtime in $r$, using dynamic programming we can get the runtime down to $O(n^2r)$. In pseudocode:

Initialize $N$ as an $r\times (n+1)$ array ($N[i][j]$ is the number of solutions to $\sum_{k=1}^i p_ka_k=j$)

For $j = 0$ to $n$:

$\;$ $N[1][j] = \begin{cases}1&\text{if } p_1\mid j\\ 0&\text{otherwise}\end{cases}$

For $i = 1$ to $r - 1$:

$\;$ For $j = 0$ to $n$:

$\;\;$ $N[i+1][j] = \sum_{k=0}^{\lfloor j/p_{i+1}\rfloor}N[i][j-p_{i+1}k]$

Return $N[r][n]$

In Python:

import numpy as np

def numSolutions(p, n):

N = np.zeros((len(p), n + 1))

for j in range(n + 1):

       if (j % p[0] == 0):

               N[0,j] = 1

       else:

               N[0,j] = 0

for i in range(len(p) - 1):

       for j in range(n + 1):

               for k in range(int(j/p[i+1]) + 1):

                       N[i+1,j] += N[i,j-p[i+1]*k]

return N[len(p)-1,n]

As a test, numSolutions([2,2,4,4],8) returns 14.

Answer 2

Use generating functions. First of all, you can divide through by 2: $$ a + b + 2 c + 2 d = 4 $$ Now represent each variable by a term $z^a$, thus (disregarding the limit) for $a$ you get: $$ 1 + z + z^2 + \cdots = \frac{1}{1 - z} $$ Similarly for $b$, while $c$ and $d$ give: $$ 1 + z^2 + z^4 + \cdots = \frac{1}{1 - z^2} $$ In all, you want the combinations that add up to 4: \begin{align} [z^4] &\frac{1}{(1 - z)^2 (1 - z^2)^2} \\ &= [z^4] \left( \frac{1}{8 (1 + z)} + \frac{1}{16 (1 + z)^2} + \frac{1}{8 (1 - z)} + \frac{3}{16 (1 - z)^2} + \frac{1}{4 (1 - z)^3} + \frac{1}{4 (1 - z)^4} \right) \\ &= \frac{1}{8} + \frac{1}{16} \binom{-2}{4} + \frac{1}{8} + \frac{3}{16} \binom{-2}{4} (-1)^4 + \frac{1}{4} \binom{-3}{4} (-1)^4 + \frac{1}{4} \binom{-4}{4} (-1)^4 \\ &= 14 \end{align}

Going to the general question posed at the end, it can be solved by this technique. But it rapidly gets very hairy. For small values of the sum it might be easier/faster to just try all posibilities (via backtracking). If you get handed lucky parameters (and the example certainly counts as such ;-) an analytic solution might be possible (in the example, it isn't too hard to derive a general formula giving the number of solutions for different sums).