1
$\begingroup$

I'm trying to count the number of integral solutions to the set of equations and inequalities

\begin{equation} \begin{split} a_0 + a_1+a_2+a_3+a_4 = C \\ a_i \geq 0 \quad i \in\{0,1,2,3,4\} \\ a_0 \geq a_1 \geq a_2 \\ a_0 \geq a_3 \geq a_4 \\ \end{split} \end{equation}

I know that the number of integral solutions for the first two equations is $\binom{C+4}{4}$. I've also seen when the $a_i$ are bounded by constants which has a nice generating function formulation. But I am stuck in figuring it out with the multivariable constraints.

I would greatly appreciate any help or ideas in how to solve this problem.

$\endgroup$
9
  • $\begingroup$ en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$ – Dave Dec 27 '19 at 5:56
  • 1
    $\begingroup$ Hi Dave, anything more specific? $\endgroup$ – WorkerBee Dec 27 '19 at 6:04
  • $\begingroup$ What you're looking for is the number of integer partitions of $C$ with at most five parts (it is at most since you are allowing zeros). See en.wikipedia.org/wiki/… specifically. $\endgroup$ – Dave Dec 27 '19 at 6:06
  • $\begingroup$ First, while I think the problems are related, they are not exactly the same since the solutions I'm looking for allow for different order of summands which partition theory ignores, unless you have a link where they don't. Second, I am not just trying to partition into 5 parts but also constraint the size of each part dependent on the sizes of the others. $\endgroup$ – WorkerBee Dec 27 '19 at 6:12
  • $\begingroup$ The constraint that $a_0\geq a_1\geq\cdots\geq a_4$ takes care of the order. An equivalent definition of a partition of $C$ is a sequence $(a_j)_{j\geq 0}$ such that $a_j\geq a_{j+1}$ and $\sum_j a_j=C$. $\endgroup$ – Dave Dec 27 '19 at 6:14
0
$\begingroup$

Let us define $f(n)$ as the number you are looking for, with $C$ replaced by $n$.

The sequence $(f(n))_n$ satisfies the linear recurrence relation: $$f(n) - f(n-1) - f(n-2) + f(n-5) + f(n-6) + f(n-7) - f(n-8) - f(n-9) - f(n-10) + f(n-13) + f(n-14) - f(n-15) = 0.$$

From here, you can use any of your favorite method to solve it.

The characteristic polynomial decomposes as $$(x - 1)^5(x + 1)^2(x^2 + 1)(x^2 + x + 1)(x^4 + x^3 + x^2 + x + 1).$$ It can also be written as $(x - 1)(x^2 - 1)(x^3 - 1)(x^4 - 1)(x^5 - 1)$. Notice that every root is a root of unity, with common multiple $60$. Hence the $60$ subsequences $(f(60n + k))_n$ are all polynomials (of degree $4$) in $n$.

It is possible to write down a list of all these polynomials. They will look like: \begin{eqnarray*} f(60n + 0) &=& 27000n^4 + 8100n^3 + 855n^2 + 39n\\ f(60n + 1) &=& 27000n^4 + 9900n^3 + 1305n^2 + 71n\\ f(60n + 2) &=& 27000n^4 + 11700n^3 + 1845n^2 + 127n + 2\\ f(60n + 3) &=& 27000n^4 + 13500n^3 + 2475n^2 + 195n + 5\\ f(60n + 4) &=& 27000n^4 + 15300n^3 + 3195n^2 + 293n + 9\\ f(60n + 5) &=& 27000n^4 + 17100n^3 + 4005n^2 + 409n + 14\\ f(60n + 6) &=& 27000n^4 + 18900n^3 + 4905n^2 + 561n + 23\\ f(60n + 7) &=& 27000n^4 + 20700n^3 + 5895n^2 + 737n + 33\\ f(60n + 8) &=& 27000n^4 + 22500n^3 + 6975n^2 + 955n + 48\\ f(60n + 9) &=& 27000n^4 + 24300n^3 + 8145n^2 + 1203n + 65\\ f(60n + 10) &=& 27000n^4 + 26100n^3 + 9405n^2 + 1499n + 88\\ f(60n + 11) &=& 27000n^4 + 27900n^3 + 10755n^2 + 1831n + 115\\ f(60n + 12) &=& 27000n^4 + 29700n^3 + 12195n^2 + 2217n + 150\\ f(60n + 13) &=& 27000n^4 + 31500n^3 + 13725n^2 + 2645n + 189\\ f(60n + 14) &=& 27000n^4 + 33300n^3 + 15345n^2 + 3133n + 238\\ f(60n + 15) &=& 27000n^4 + 35100n^3 + 17055n^2 + 3669n + 294\\ f(60n + 16) &=& 27000n^4 + 36900n^3 + 18855n^2 + 4271n + 361\\ f(60n + 17) &=& 27000n^4 + 38700n^3 + 20745n^2 + 4927n + 436\\ f(60n + 18) &=& 27000n^4 + 40500n^3 + 22725n^2 + 5655n + 526\\ f(60n + 19) &=& 27000n^4 + 42300n^3 + 24795n^2 + 6443n + 625\\ f(60n + 20) &=& 27000n^4 + 44100n^3 + 26955n^2 + 7309n + 741\\ f(60n + 21) &=& 27000n^4 + 45900n^3 + 29205n^2 + 8241n + 869\\ f(60n + 22) &=& 27000n^4 + 47700n^3 + 31545n^2 + 9257n + 1016\\ f(60n + 23) &=& 27000n^4 + 49500n^3 + 33975n^2 + 10345n + 1178\\ f(60n + 24) &=& 27000n^4 + 51300n^3 + 36495n^2 + 11523n + 1362\\ f(60n + 25) &=& 27000n^4 + 53100n^3 + 39105n^2 + 12779n + 1562\\ f(60n + 26) &=& 27000n^4 + 54900n^3 + 41805n^2 + 14131n + 1788\\ f(60n + 27) &=& 27000n^4 + 56700n^3 + 44595n^2 + 15567n + 2034\\ f(60n + 28) &=& 27000n^4 + 58500n^3 + 47475n^2 + 17105n + 2308\\ f(60n + 29) &=& 27000n^4 + 60300n^3 + 50445n^2 + 18733n + 2604\\ f(60n + 30) &=& 27000n^4 + 62100n^3 + 53505n^2 + 20469n + 2933\\ f(60n + 31) &=& 27000n^4 + 63900n^3 + 56655n^2 + 22301n + 3287\\ f(60n + 32) &=& 27000n^4 + 65700n^3 + 59895n^2 + 24247n + 3677\\ f(60n + 33) &=& 27000n^4 + 67500n^3 + 63225n^2 + 26295n + 4096\\ f(60n + 34) &=& 27000n^4 + 69300n^3 + 66645n^2 + 28463n + 4554\\ f(60n + 35) &=& 27000n^4 + 71100n^3 + 70155n^2 + 30739n + 5045\\ f(60n + 36) &=& 27000n^4 + 72900n^3 + 73755n^2 + 33141n + 5580\\ f(60n + 37) &=& 27000n^4 + 74700n^3 + 77445n^2 + 35657n + 6150\\ f(60n + 38) &=& 27000n^4 + 76500n^3 + 81225n^2 + 38305n + 6769\\ f(60n + 39) &=& 27000n^4 + 78300n^3 + 85095n^2 + 41073n + 7428\\ f(60n + 40) &=& 27000n^4 + 80100n^3 + 89055n^2 + 43979n + 8139\\ f(60n + 41) &=& 27000n^4 + 81900n^3 + 93105n^2 + 47011n + 8894\\ f(60n + 42) &=& 27000n^4 + 83700n^3 + 97245n^2 + 50187n + 9707\\ f(60n + 43) &=& 27000n^4 + 85500n^3 + 101475n^2 + 53495n + 10568\\ f(60n + 44) &=& 27000n^4 + 87300n^3 + 105795n^2 + 56953n + 11491\\ f(60n + 45) &=& 27000n^4 + 89100n^3 + 110205n^2 + 60549n + 12467\\ f(60n + 46) &=& 27000n^4 + 90900n^3 + 114705n^2 + 64301n + 13510\\ f(60n + 47) &=& 27000n^4 + 92700n^3 + 119295n^2 + 68197n + 14611\\ f(60n + 48) &=& 27000n^4 + 94500n^3 + 123975n^2 + 72255n + 15785\\ f(60n + 49) &=& 27000n^4 + 96300n^3 + 128745n^2 + 76463n + 17020\\ f(60n + 50) &=& 27000n^4 + 98100n^3 + 133605n^2 + 80839n + 18334\\ f(60n + 51) &=& 27000n^4 + 99900n^3 + 138555n^2 + 85371n + 19716\\ f(60n + 52) &=& 27000n^4 + 101700n^3 + 143595n^2 + 90077n + 21181\\ f(60n + 53) &=& 27000n^4 + 103500n^3 + 148725n^2 + 94945n + 22719\\ f(60n + 54) &=& 27000n^4 + 105300n^3 + 153945n^2 + 99993n + 24347\\ f(60n + 55) &=& 27000n^4 + 107100n^3 + 159255n^2 + 105209n + 26053\\ f(60n + 56) &=& 27000n^4 + 108900n^3 + 164655n^2 + 110611n + 27855\\ f(60n + 57) &=& 27000n^4 + 110700n^3 + 170145n^2 + 116187n + 29741\\ f(60n + 58) &=& 27000n^4 + 112500n^3 + 175725n^2 + 121955n + 31729\\ f(60n + 59) &=& 27000n^4 + 114300n^3 + 181395n^2 + 127903n + 33807\\ \end{eqnarray*}


Explanation on the recurrence relation:

It is possible to deduce that recurrence relation by hand.

Firstly, we calculate $f(n)$ by partitioning the set: there are four subsets, $A = \{a_2 = 0\}$, $B = \{a_4 = 0\}$, $C = \{a_2 = a_4 = 0\}$, $D = \{a_2 \neq 0 \neq a_4\}$. It is clear that $f(n) = |A| + |B| - |C| + |D|$.

It is also clear that $$|A| = |B| = |\{(a_0, a_1, a_2, a_3):a_0 + a_1 + a_2 + a_3 = n, a_0 \geq a_1 \geq a_2 \geq 0, a_0 \geq a_3 \geq 0\}|.$$We denote this number by $g(n)$.

We also have $$|C| = |\{(a_0, a_1, a_3):a_0 + a_1 + a_3 = n, a_0 \geq a_1 \geq 0, a_0 \geq a_3 \geq 0\}|.$$ We denote this number by $h(n)$.

Finally, by mapping every $a_i$ to $a_i - 1$, we see that $|D| = f(n - 5)$.

Thus we obtain: $f(n) = 2g(n) - h(n) + f(n - 5)$.

Now if we do the same analysis for $g(n)$ (i.e. partitioning into $\{a_2 = 0\}$, $\{a_3 = 0\}$, $\{a_2 = a_3 = 0\}$, $\{a_2 \neq 0 \neq a_3\}$), and also for $h(n)$, we get similar recurrence relations, but involving again new functions such as $|\{(a_0, a_1, a_2): a_0 + a_1 + a_2 = n, a_0 \geq a_1 \geq a_2 \geq 0\}|$.

Each step will reduce the problem to simpler functions. Repeating this procedure, we will finally arrive at a recurrence formula for the original function $f$.

While this is totally doable by hand, it's probably a complicated task and has to be done very carefully. Therefore, I didn't use this approach.

Instead, seeing that a linear recurrence relation (of reasonable order, say $< 100$) must exist, I wrote a program to generate the sequence and then found the recurrence relation directly, by solving linear equations. That's the result in the beginning of the answer.

$\endgroup$
4
  • $\begingroup$ Please tell me you used some kind of software to generate that list, and that you didn't type it all by hand... $\endgroup$ – Math1000 Dec 27 '19 at 7:23
  • 1
    $\begingroup$ I'm impressed but a little bit confused. Can you elaborate how you converted my problem into that recurrence relationship? $\endgroup$ – WorkerBee Dec 27 '19 at 8:15
  • $\begingroup$ @Math1000 Yes, some kind of software was used to generate that list (: $\endgroup$ – WhatsUp Dec 27 '19 at 15:07
  • $\begingroup$ @WorkerBee I'll add some explanation. $\endgroup$ – WhatsUp Dec 27 '19 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.