Published in:
26-10-2021 | Original Paper
On restricted partitions of numbers
Author:
H. F. Mattson Jr.
Published in:
Applicable Algebra in Engineering, Communication and Computing
|
Issue 5/2023
Log in
Abstract
This paper finds new quasi-polynomials over \({{\mathbb {Z}}}\) for the number \(p_k(n)\) of partitions of n with parts at most k. Methods throughout are elementary. We derive a small number of polynomials (e.g., one for \(k=3\), two for \(k = 4\) or 5, six for \(k=6\)) that, after addition of appropriate constant terms, take the value \(p_k(n)\). For example, for \(0\le r < 6\) and for all \(q \ge 0\), \(p_3(6q+r) = p_3(r)+\pi _0(q,r)\), a polynomial of total degree 2 in q and r. In general there are \(M_{\lfloor k/2 \rfloor } =\) lcm\(\{1,2,\ldots ,\lfloor k/2 \rfloor \}\) such polynomials. In two variables q and s, they take the form \(\sum a_{i,j}{q \atopwithdelims ()i}{s \atopwithdelims ()j}\) with \(a_{i,j} \in {{\mathbb {Z}}}\), which we call the proper form for an integer-valued polynomial. They constitute a quasi-polynomial of period \(M_{\lfloor k/2 \rfloor }\) for the sequence \((p_k(n)-p_k(r))\) with \(n \equiv r \pmod {M_k}\). For each k the terms of highest total degree are the same in all the polynomials and have coefficients dependent only on k. A second theorem, combining partial fractions and the above approach, finds hybrid polynomials over \({{\mathbb {Q}}}\) for \(p_k(n)\) that are easier to determine than those above. We compare our results to those of Cayley, MacMahon, and Arkin, whose classical results, as recast here, stand up well. We also discuss recent results of Munagi and conclude that circulators in some form are inevitable. At \(k=6\) we find serious errors in Sylvester’s calculation of his “waves.” Sylvester JJ (Q J Pure Appl Math 1:141–152, 1855). The results are generalized to the (not very different) problem called “making change,” where significant improvements to existing approaches are found. We find an infinitude of new congruences for \(p_k(n)\) for \(k= 3, 4\), and one new one for \(k=5\). Reduced modulo m the periodic sequence \((p_k(n))\) is investigated for periodicity and zeros: we find, from scratch, a simple proof of a known result in a special case.