Skip to main content
DE
Published in:

26-10-2021 | Original Paper

# On restricted partitions of numbers

Author: H. F. Mattson Jr.

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config

## 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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 102.000 Bücher
• über 537 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Business IT + Informatik
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 67.000 Bücher
• über 340 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Business IT + Informatik
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 67.000 Bücher
• über 390 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Business IT + Informatik
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
Later we’ll place these polynomials in the context of quasi-polynomials.

2
Briefly reviewed in the Appendix

3
Priority for the result, however, is DeMorgan’s [13].

4
DeMorgan’s proof is in [13]. Another proof is in [26, p. 130].

5
All “large numbers” stated as values of $$p_k(n)$$ in the paper are taken from or verified against a table of $$p_k(n)$$ computed using the recurrence (20).

6
On the ordering: each block of d ordered pairs (ij) with $$1 \le i$$ and $$i+j = d$$, corresponding to all the terms of total degree d, may be ordered in any way. The only essential is to order these blocks linearly by d.

7
Department of strange coincidences: 17/72 is the coefficient of $$1/(1-x)$$ in $$P_4(x)$$ as partial fractions; 25/144 is the coefficient of $$n+2$$ in the nearest-integer formula for $$p_4(n)$$ in [19, p. 3].

8
Again, for $$t=1$$: 11/64 is the coefficient of $$n+2$$ in the nearest-integer formula for $$p_5(n)$$ in [19, p. 3].

9
Calculated as decimals; equations were then multiplied by 4320 = lcm{432, 96, 6!}.

10
In [22] it is written that Munagi has computed exact formulas for $$p_k(n)$$ for k up to 18 in his PhD thesis, but it is apparently not published.

11
E.g., $$a = 1350/1036800.$$

12
Presumably the same results would hold for Cayley polynomials if we had Cayley’s workout for $$k= 6,7,8$$.

13
Actually Bell proved it in the slightly more general case we’re calling, in II.E, “Making Change”.

14
I do recognize that [11] is focused on a different problem than the one Bell posed.

15
For a proof of the converse, see [21].

16
Sylvester writes “Mr. Cayley was led to the use of prime circulators from a perception of their affording the best analytical means of giving determinateness to the representation of the results; in my method they offer themselves spontaneously, and cannot be rejected.”

17
These Victorian gentlemen almost never cited works of others or themselves. In [26] there is no citation to [25], which I found thanks only to Cayley; it was his one citation in [12]. In [26] is one citation, to Cayley: Sylvester corrects him on a point. They were a small club, publishing letters to each other.

18
After setting the problem in terms of partial fractions, Newman writes “For obvious reasons we [omit] the remaining details.” He suggests readers complete a similar example with more “reasonable” numbers.

19
A contribution of error-correcting codes to mathematics: Nijenhuis and Wilf [20] base their proof of minimum period on a 1968 result of Berlekamp [9].

20
Also note that the k zeros at the top of the period are even more obvious: they are the initial k zeros in $$\{p_k^*(n)\}$$.

Literature
1.
Ahlgren, S., Ono, K.: Addition and counting: the arithmetic of partitions. Not. Am. Math. Soc. 48(9), 978–984 (2001)
2.
Andrews, G.E.: The Theory of Partitions. Addison-Wesley, London (1976)MATH
3.
Andrews, G.E.: Partitions: at the interface of q-series and modular forms. Ramanujan J. 7, 385–400 (2003)
4.
Arkin, J.: Researches on partitions. Duke Math. J. 37, 403–409 (1970)
5.
Auluck, F.C., Kothari, D.S.: Statistical mechanics and the partitions of numbers. Math. Proc. Cambridge Philos. Soc. 42(03), 272–277 (1946). https://​doi.​org/​10.​1017/​S030500410002303​3
6.
Bak, J., Newman, D.J.: Complex: Analysis, 3rd edn., pp. 279–282. Springer, Berlin (2010)
7.
Bateman, P., Kalb, J., Stegner, A.: Problem 10797 and solution. Amer. Math. Monthly 109(4), 393–394 (2002)CrossRef
8.
Bell, E.T.: Interpolation of denumerants and Lambert series. Am. J. Math. 65, 382–386 (1943)
9.
Berlekamp, E.R.: Algebraic Coding Theory, p. 151. McGraw-Hill, New York (1968)MATH
10.
Cahen, P.-J., Chabert, J.-L.: What you should know about integer-valued polynomials. Amer. Math. Monthly 123(4), 311–337 (2016)
11.
Castillo, A., Flores, S., Hernandez, A., Kronholm, B., Larsen, A., Martinez, A.: Quasipolynomials and maximal coefficients of Gaussian polynomials. Ann. Comb. 23, 589–611 (2019)
12.
Cayley, A.: Researches on the Partition of Numbers. Collect. Math. Pap. 2, 235–249 (1898)
13.
DeMorgan, A.: On a new form of difference equation. Cambridge Math. J. 4, 87–90 (1843)
14.
Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison-Wesley, Reading (1994)MATH
15.
Kronholm, B.: Generalized congruence properties of the restricted partition function $$p(n, m)$$. Ramanujan J. 30, 425–436 (2013)
16.
Kwong, Y.H.: Minimum periods of partition functions modulo $$M$$. Utilitas Mathematica 35, 3–8 (1989)
17.
MacMahon, P.A.: Combinatory Analysis, vol. 2. Cambridge University Press, Cambridge (1960)MATH
18.
Manschot, Jan: Partition Functions for Supersymmetric Black Holes. Amsterdam University Press, Amsterdam (2008)CrossRef
19.
Munagi, A.: Computation of $$q$$-partial fractions. Electron. J. Comb. Number Theory 7, 25 (2007)
20.
Nijenhuis, A., Wilf, H.S.: Periodicites of partition functions and Stirling numbers modulo $$p$$. J. Number Theory 25, 308–312 (1987)
21.
Cormac O’Sullivan, Partitions and Sylvester waves, arXiv:​1702.​03611v2 [math.NT] 30 March 2018 (pp. 31)
22.
Sills, A.V., Zeilberger, D.: Formulae for the number of partitions of $$n$$ into at most $$m$$ parts (using the quasi-polynomial ansatz). Adv. Appl. Math. 48(5), 640645 (2012)
23.
Stanley, R.P.: Enumerative Combinatorics, vol. I, 2ed, edn. Cambridge University Press, Cambridge (2012)MATH
24.
Stanley, R.P.: Combinatorics and Commutative Algebra. Birkhauser, Boston (1983)
25.
Sylvester, J.J.: On the partition of numbers. Q. J. Pure Appl. Math. 1, 141–152 (1855)
26.
Sylvester, J.J.: On subinvariants …… partitions. Am. J. Math. 5, 79–136 (1882)CrossRef
Metadata
Title
On restricted partitions of numbers
Author
H. F. Mattson Jr.
Publication date
26-10-2021
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 5/2023
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-021-00524-5