On the m-ary partition numbers

We give explicit formulas and recurrences for the m-ary partition numbers and relate them to Toeplitz-Hessenberg determinants. Some of these results are direct analogues of similar statements for the classical (unrestricted) partition numbers.

Gespeichert in:
Bibliographische Detailangaben
Datum:2015
Hauptverfasser: Kachi, Y., Tzermias, P.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2015
Schriftenreihe:Algebra and Discrete Mathematics
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/152788
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:On the m-ary partition numbers / Y. Kachi, P. Tzermias // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 67-76. — Бібліогр.: 39 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-152788
record_format dspace
spelling irk-123456789-1527882019-06-13T01:25:35Z On the m-ary partition numbers Kachi, Y. Tzermias, P. We give explicit formulas and recurrences for the m-ary partition numbers and relate them to Toeplitz-Hessenberg determinants. Some of these results are direct analogues of similar statements for the classical (unrestricted) partition numbers. 2015 Article On the m-ary partition numbers / Y. Kachi, P. Tzermias // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 67-76. — Бібліогр.: 39 назв. — англ. 1726-3255 2010 MSC:05A17, 11P81 http://dspace.nbuv.gov.ua/handle/123456789/152788 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description We give explicit formulas and recurrences for the m-ary partition numbers and relate them to Toeplitz-Hessenberg determinants. Some of these results are direct analogues of similar statements for the classical (unrestricted) partition numbers.
format Article
author Kachi, Y.
Tzermias, P.
spellingShingle Kachi, Y.
Tzermias, P.
On the m-ary partition numbers
Algebra and Discrete Mathematics
author_facet Kachi, Y.
Tzermias, P.
author_sort Kachi, Y.
title On the m-ary partition numbers
title_short On the m-ary partition numbers
title_full On the m-ary partition numbers
title_fullStr On the m-ary partition numbers
title_full_unstemmed On the m-ary partition numbers
title_sort on the m-ary partition numbers
publisher Інститут прикладної математики і механіки НАН України
publishDate 2015
url http://dspace.nbuv.gov.ua/handle/123456789/152788
citation_txt On the m-ary partition numbers / Y. Kachi, P. Tzermias // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 67-76. — Бібліогр.: 39 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT kachiy onthemarypartitionnumbers
AT tzermiasp onthemarypartitionnumbers
first_indexed 2025-07-14T04:16:58Z
last_indexed 2025-07-14T04:16:58Z
_version_ 1837594436987518976
fulltext Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 19 (2015). Number 1, pp. 67–76 © Journal “Algebra and Discrete Mathematics” On the m-ary partition numbers Yasuyuki Kachi and Pavlos Tzermias Communicated by R. I. Grigorchuk Abstract. We give explicit formulas and recurrences for the m-ary partition numbers and relate them to Toeplitz-Hessenberg determinants. Some of these results are direct analogues of similar statements for the classical (unrestricted) partition numbers. 1. Introduction Let m be a fixed integer such that m > 2. For a positive integer n, let bm(n) denote the number of m-ary partitions of n, i.e. the number of ways of writing n as a sum of powers of m using non-negative exponents with repetitions allowed and the order of the summands not being taken into account. We also set bm(0) = 1. The special case of binary partitions, i.e. the case m = 2, was appar- ently first studied by Euler in 1750. The recurrence formulas b2(2n + 1) = b2(2n), b2(2n) = b2(2n − 1) + b2(n), for n > 0 are well-known. The sequence {b2(n) : n ∈ N} is labelled A018819 in the On-Line Encyclopedia of Integer Sequences (available at http://oeis.org/AO18819). Various number-theoretic properties as well as the asymptotic behavior of the m-ary partition sequence {bm(n) : n ∈ N} and some of its variants 2010 MSC: 05A17, 11P81. Key words and phrases: m-ary partition numbers, generating functions, Toeplitz- Hessenberg determinants. 68 m-ary partition numbers (for the binary and for the general case) have been extensively studied in the literature. We refer the reader to the work of Alkauskas [1,2], Andrews [4], Calkin and Wilf [8], Churchhouse [10], de Bruijn [12], Flajolet and Sedgewick [15], Gupta [17–19], Hirschhorn and Loxton [21], Hirschhorn and Sellers [22], Mahler [23–25], Meinardus [27], Murty and Murty [29, Ch. 7], Pennington [30], Richmond [33], Rödseth [34], Rödseth and Sellers [35,36] for more information, emphasizing the fact that the latter list is by no means exhaustive. The generating function for the sequence {bm(n) : n ∈ N} is fm(x) = ∞ ∑ n=0 bm(n)xn = ∞ ∏ n=0 ∞ ∑ i=0 ximn = ∞ ∏ n=0 (1 − xmn )−1, which implies the functional equation fm(xm) = (1 − x)fm(x). Besides its combinatorial importance, the generating function fm(x) is of special interest in transcendental number theory. For example, as Mahler has shown in [25] (see also its corrigendum [24]), the values of f2(x) are always transcendental for every algebraic number x such that 0 < |x| < 1. In this paper we give explicit formulas and recurrence relations for the sequence {bm(n) : n ∈ N}. We also relate these formulas to Toeplitz- Hessenberg determinants (first introduced in [37] and [20]). Some of these results are direct analogues of similar statements for the classical (unrestricted) partition numbers. For a positive integer n, let ξm(n) denote the sum of all divisors of n that are powers of m with non-negative exponent. Note that ξm(1) = 1 and ξm(n) > 1, for all n > 1. We also define ξm(0) = 1. The sequence {ξm(n) : n ∈ N} is the m-ary analogue of the classical sum-of-divisors sequence. Our first result in this paper is an elementary yet explicit formula for bm(n) given below. We are not aware of any other formula in the existing literature that concretely expresses the integer bm(n) as a finite sum of rational numbers. For more profound analogous results for the classical partition function we refer the reader to the formulas of Rademacher in [31] and [32] and of Bruinier and Ono in [7]. It would be interesting to look for m-ary analogues of the latter formulas, if such analogues exist. Theorem 1. For every positive integer n, the m-ary partition number bm(n) is expressed as the finite sum bm(n) = ∑ n1+2n2+3n3+···=n ξm(1)n1ξm(2)n2ξm(3)n3 · · · n1! n2! n3! · · · 1n12n23n3 · · · . Y. Kachi, P. Tzermias 69 Remark 1. It is a well-known and easy to prove fact that the number of summands on the right-hand side of the latter formula equals p(n), i.e. the number of partitions of the integer n. Now, for a positive integer n, let dm(n) ∈ N be defined as follows: If n is not the sum of distinct powers of m, let dm(n) = 0. If n is the sum of an even number of distinct powers of m, let dm(n) = 1. If n is the sum of an odd number of distinct powers of m, let dm(n) = −1. We also set dm(0) = 1. Note that ∞ ∑ n=0 dm(n) xn = ∞ ∏ n=0 (1 − xmn ) = 1 fm(x) . Note also that, in the binary case, we have d2(n) = (−1)t(n), where t(n) is the n-th term of the Prouhet-Thue-Morse sequence, which is discussed extensively in [3]. We now express the m-ary partition numbers bm(n) as determinants of certain Toeplitz-Hessenberg matrices with entries in the set {−1, 0, 1}, specifically with entries given by the numbers dm(n). This is the m-ary analogue of a formula obtained by Malenfant [26] for the classical partition function. Conversely, we can also express the numbers dm(n) as determinants of certain Toeplitz-Hessenberg matrices with entries given by the numbers bm(n): Theorem 2. For every positive integer n, we have bm(n) = (−1)ndet         dm(1) 1 0 · · · 0 dm(2) dm(1) 1 · · · 0 ... ... ... . . . ... dm(n − 1) dm(n − 2) dm(n − 3) · · · 1 dm(n) dm(n − 1) dm(n − 2) · · · dm(1)         . Similarly, dm(n) = (−1)ndet         bm(1) 1 0 · · · 0 bm(2) bm(1) 1 · · · 0 ... ... ... . . . ... bm(n − 1) bm(n − 2) bm(n − 3) · · · 1 bm(n) bm(n − 1) bm(n − 2) · · · bm(1)         . Remark 2. The proof of Theorem 1.2 is very simple and based on Cramer’s rule for solving linear systems. To be more specific, the fact 70 m-ary partition numbers that the coefficients of the reciprocal of a formal power series can be expressed as determinants of certain Toeplitz-Hessenberg matrices whose entries are functions of the coefficients of the original formal power series is well-known and simple to prove (e.g. page 157 in Comtet’s book [11]). The same fact has recently been applied in a number of similar contexts and settings by Chen [9], Malenfant [26] and Vella [38]. On the other hand, what is far from simple is an ingenious and quite general method employed by Brioschi [6] relating Toeplitz-Hessenberg determinants to complete homogeneous forms in the roots of a given polynomial and leading to a general formula expressing these determinants in terms of multinomial coefficients. The same formula was apparently discovered earlier by Fergola [14] using a different method. We refer the reader to Muir’s book [28] for an extensive and substantiated survey of the historical development of the theory of determinants. An excellent (albeit significantly shorter) account of the Brioschi-Fergola general formula is also described in the preprint [13] by Fera and Talamini, where two different proofs of the formula are presented. In light of what appears to be a resurgence of recent interest around this circle of ideas, we believe that the Brioschi-Fergola formula deseves to be more widely known. We would also like to point out that, to the best of our knowledge and ability, the Brioschi-Fergola formula applied to the particular setting of Theorem 1.2 does not immediately reduce to the formula given in Theorem 1.1 in any obvious way; for one thing, the summands in the formula given in Theorem 1.1 are not necessarily integers, while those given by the Brioschi-Fergola formula are. We also give recurrence formulas for the numbers bm(n) and dm(n). The recurrence relation for bm(n) is the m-ary analogue of a rather well known recurrence relation for the classical partition function (see [5], Entry 52, page 108): Theorem 3. For n > 1, we have bm(n) = 1 n n−1 ∑ j=0 ξm(n−j) bm(j) and dm(n) = −1 n n−1 ∑ j=0 ξm(n−j) dm(j). 2. Proofs Proof of Theorem 1. As usual, let log(·) denote the natural logarithm. As formal power series, we have log(fm(x)) = log ( ∞ ∏ n=0 (1 − xmn )−1 ) = − ∞ ∑ n=0 log(1 − xmn ) Y. Kachi, P. Tzermias 71 = ∞ ∑ n=0 ∞ ∑ i=1 ximn i = ∞ ∑ n=0 ∞ ∑ i=1 ximn imn mn. Define integers ak, for k ∈ {1, 2, . . .}, by setting ak = k, if k is a power of m, and ak = 0, if k is not a power of m. Then log(fm(x)) = ∞ ∑ k=1 xk k ∑ d|k ad = ∞ ∑ k=1 xk k ξm(k). Therefore, fm(x) = elog(fm(x)) = ∞ ∑ n=0 1 n! ( ∞ ∑ k=1 xk k ξm(k) )n . For a sequence of natural numbers n1, n2, . . ., with only finitely many non-zero terms, the multinomial coefficient ( n1 + n2 + · · · n1, n2, · · · ) = (n1 + n2 + · · · )! n1! n2! · · · makes sense and one can use the “infinite version" of the multinomial theorem ( ∞ ∑ k=1 yk )n = ∑ n1+n2+···=n ( n n1, n2, · · · ) ∞ ∏ k=1 yk nk , to get fm(x) = ∞ ∑ n=0 1 n! ∑ n1+n2+···=n ( n n1, n2, · · · ) ∞ ∏ k=1 ( xk k ξm(k) )nk = ∞ ∑ n=0 1 n! ∑ n1+n2+···=n ( n n1, n2, · · · ) ∞ ∏ k=1 xknk knk ξm(k)nk = ∞ ∑ n=0 1 n! ∑ n1+n2+···=n ( n n1, n2, · · · ) xn1+2n2+··· 1n12n2 · · · ξm(1)n1ξm(2)n2 · · · = ∞ ∑ r=0   ∑ n1+2n2+···=r ( n1 + n2 + · · · n1, n2, · · · ) ξm(1)n1ξm(2)n2 · · · (n1 + n2 + · · · )!1n12n2 · · ·  xr = ∞ ∑ r=0   ∑ n1+2n2+3n3+···=r ξm(1)n1ξm(2)n2ξm(3)n3 · · · n1! n2! n3! · · · 1n12n23n3 · · ·  xr. 72 m-ary partition numbers For all r > 0, the coefficient of xr in the latter series must equal bm(r) and the theorem follows. Proof of Theorem 2. Comparing coefficients of the same powers of x on both sides of the equality ( ∞ ∑ i=0 dm(i) xi ) ( ∞ ∑ i=0 bm(i) xi ) = 1, gives the linear system r ∑ i=0 dm(r − i) bm(i) = 0, for every r > 1. Combining the latter equations for r = 1, . . . , n, with bm(0) = dm(0) = 1, results in the n × n linear system AX = B, where A =       dm(n − 1) dm(n − 2) · · · 1 dm(n − 2) dm(n − 3) · · · 0 ... ... . . . ... 1 0 · · · 0       , X =       bm(1) bm(2) ... bm(n)       , B =       −dm(n) −dm(n − 1) ... −dm(1)       . The determinant of A equals (−1) n(n+3) 2 . Also, the determinant of the matrix obtained from A by replacing its last column by B equals −det         dm(n − 1) dm(n − 2) · · · dm(1) dm(n) dm(n − 2) dm(n − 3) · · · 1 dm(n − 1) ... ... . . . ... ... dm(1) 1 · · · 0 dm(2) 1 0 · · · 0 dm(1)         = (−1)ndet         dm(n) dm(n − 1) dm(n − 2) · · · dm(1) dm(n − 1) dm(n − 2) dm(n − 3) · · · 1 ... ... ... . . . ... dm(2) dm(1) 1 · · · 0 dm(1) 1 0 · · · 0         Y. Kachi, P. Tzermias 73 (−1) n(n+1) 2 det         dm(1) 1 0 · · · 0 dm(2) dm(1) 1 · · · 0 ... ... ... . . . ... dm(n − 1) dm(n − 2) dm(n − 3) · · · 1 dm(n) dm(n − 1) dm(n − 2) · · · dm(1)         . Hence, by Cramer’s rule, the formula for bm(n) in Theorem 2 follows. A similar argument (interchanging the roles of bm(n) and dm(n)) establishes the formula for dm(n) in Theorem 2. Proof of Theorem 3. The idea of the proof is classically known and due to Euler (as explained by Fuchs and Tabachnikov in Section 3.5 of [16]). To prove the first recurrence formula, we argue as follows: As formal power series, we have −x d dx log ( 1 − xmk ) = x d dx ( ∞ ∑ i=1 ximk i ) = mk ∞ ∑ i=1 ximk . Therefore, x d dx log (fm(x)) = − ∞ ∑ k=0 x d dx log ( 1 − xmk ) = ∞ ∑ k=0 ∞ ∑ i=1 mkximk = ∞ ∑ n=1 ξm(n)xn. Hence, x d dx fm(x) = fm(x) ∞ ∑ n=1 ξm(n)xn, which implies that x d dx ∞ ∑ n=0 bm(n)xn = fm(x) ∞ ∑ n=1 ξm(n)xn. Hence, ∞ ∑ n=1 nbm(n)xn = ( ∞ ∑ n=0 bm(n)xn )( ∞ ∑ n=1 ξm(n)xn ) = ∞ ∑ n=1   n−1 ∑ j=0 bm(j) ξm(n − j)  xn, 74 m-ary partition numbers and the recurrence formula follows by comparing the coefficients of xn on both sides of the latter equality. The second recurrence formula can be proven by a similar argument: The relation (proven above) x d dx fm(x) = fm(x) ∞ ∑ n=1 ξm(n)xn, also implies that x d dx ( 1 fm(x) ) = −1 fm(x) ∞ ∑ n=1 ξm(n)xn. Therefore, x d dx ∞ ∑ n=0 dm(n)xn = −1 fm(x) ∞ ∑ n=1 ξm(n)xn, which implies that ∞ ∑ n=1 ndm(n)xn = − ( ∞ ∑ n=0 dm(n)xn )( ∞ ∑ n=1 ξm(n)xn ) = − ∞ ∑ n=1   n−1 ∑ j=0 dm(j) ξm(n − j)  xn, and the recurrence formula follows by comparing of the coefficients of xn on both sides of the latter equality. References [1] G. Alkauskas, Congruence properties of the function that counts compositions into powers of 2, J. Integer Seq., (5) N.13, Article 10.5.3, 2010, 9 pp. [2] G. Alkauskas, A generalization of the Rödseth-Gupta theorem on binary partitions, Lithuanian Math. J., (2) N.43, 2003, pp. 103-110. [3] J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: Ding, C. Helleseth, T., Niederreiter, H. (eds.) Sequences and their aplications, Proceedings of SETA ’98, 1999, Springer-Verlag, pp. 1-16. [4] G. Andrews, Congruence properties of the m-ary partition function, J. Number Theory, N.3, 1971, pp. 104-110. [5] B. Berndt, Ramanujan’s Notebooks, Part IV, 1994, Springer-Verlag, New York. [6] F. Brioschi, Sulle funzioni Bernoulliane ed Euleriane, Annali di Matematica Pura ed Applicada, 1858, pp. 260-263. Y. Kachi, P. Tzermias 75 [7] J.-H. Bruinier, K. Ono, Algebraic formulas for the coefficients of half-integral weight harmonic weak Maass forms, Adv. Math., N.246, 2013, pp. 198-219. [8] N. Calkin, H. Wilf, Recounting the rationals, Amer. Math. Monthly, (4) N.107, 2007, pp. 360-363. [9] K.-W. Chen, Inversion of generating functions using determinants, J. Integer Seq., (10) N.10, Article 07.10.5, 2007, 10 pp. [10] R.-F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc., N.66, 1969, pp. 371-376. [11] L. Comtet, Advanced Combinatorics, The art of finite and infinite expansions, 1974, D. Reidel Publishing Co., Dordrecht. [12] N.-G. de Bruijn, On Mahler’s partition problem, Indagationes Math., N.10, 1948, pp. 210-220. [13] G. Fera, V. Talamini, Explicit formulas using partitions of integers for numbers, preprint, 2013 (http://arxiv.org/pdf/1211.1440v2.pdf). [14] E. Fergola, Sopra lo sviluppo della funzione 1/(cex − 1), e sopra una nuova espressione dei numeri di Bernoulli, Memorie della Reale Accademia delle Scienze di Napoli, N.2, 1857, pp. 315-324. [15] P. Flajolet, R. Sedgewick, Analytic Combinatorics, 2009, Cambridge University Press, Cambridge. [16] D. Fuchs, S. Tabachnikov, Mathematical Omnibus, Thirty lectures on classic mathematics, 2007, American Mathematical Society, Providence, RI. [17] H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math., (1) N.18, 1976, pp. 1-5. [18] H. Gupta, A simple proof of the Churchhouse conjecture concerning binary parti- tions, Indian J. Pure Appl. Math., (5) N.3, 1972, pp. 791-794. [19] H. Gupta, Proof of the Churchhouse conjecture concerning binary partitions, Proc. Cambridge Philos. Soc., N.70, 1971, pp. 53-56. [20] K. Hessenberg, Behandlung linearer Eigenwertaufgaben mit Hilfe der Hamilton- Cayleyschen Gleichung, Bericht der Reihe Numerische Verfahren, IPM Darmstadt, 1940, 36pp. [21] M.-D. Hirschhorn, J.-H. Loxton, Congruence properties of the binary partition function, Math. Proc. Cambridge Philos. Soc., N.78, 1975, pp. 437-442. [22] M.-D. Hirschhorn, J.-A. Sellers, A different view of m-ary partitions, Australas. J. Combin., N.30, 2004, pp. 193-196. [23] K. Mahler, On a special functional equation, J. London Math. Soc., N.15, 1940, pp. 115-123. [24] K. Mahler, Berichtigung zu der Arbeit von K. Mahler: Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Math. Ann., N.103, 1930, pp. 532. [25] K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktion- algleichungen, Math. Ann., N.101, 1929, pp. 342-366. [26] J. Malenfant, Finite, closed-form expressions for the partition func- tion and for Euler, Bernoulli, and Stirling numbers, preprint, 2011 (http://arxiv.org/pdf/1103.1585.pdf). 76 m-ary partition numbers [27] G. Meinardus, Asymptotische Aussagenüber Partitionen, Math. Z., N.59, 1954, pp. 388-398. [28] T. Muir, The Theory of Determinants in the Historical Order of Development, Vol. II, The period 1841 to 1860, 1911, Macmillan and Co. London. [29] M. Ram Murty, V. Kumar Murty, The Mathematical Legacy of Srinivasa Ramanu- jan, 2013, Springer, New Delhi. [30] W.-B. Pennington, On Mahler’s partition problem, Annals of Math., N.57, 1953, pp. 531-546. [31] H. Rademacher, On the expansion of the partition function in a series, Annals of Math., N.44, 1943, pp. 416-422. [32] H. Rademacher, On the partition function p(n), Proc. London Math. Soc., (2) N.43, 1937, pp. 241-254. [33] B. Richmond, Mahler’s partition problem, Ars Combinatoria, N.2, 1976, pp. 169- 189. [34] Ö. Rödseth, Some arithmetical properties of m-ary partitions, Proc. Cambridge Philos. Soc., N.68, 1970, pp. 447-453. [35] Ö. Rödseth, J.-A. Sellers, Binary partitions revisited, J. Combin. Theory Ser. A, (1) N.98, 2002, pp. 33-45. [36] Ö. Rödseth, J.-A. Sellers, On m-ary partition function congruences: A fresh look at a past problem, J. Number Theory, (2) N.87, 2001, pp. 270-281. [37] O. Toeplitz, Zur Transformation der Scharen bilinearer Formen von unendlichvielen Veränderlichen, Nachr. der Kgl. Gesselschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse (1907), 110-115. [38] D. Vella, Explicit formulas for Bernoulli and Euler numbers, Integers, N.8, 2008, A01, 7 pp. [39] H. Wilf, Lectures on Integer Partitions, Pacific Institute for the Mathematical Sciences Distinguished Chair Lectures, University of Victoria, 2000 (http://www.math.upenn.edu/∼wilf/PIMS/PIMSLectures.pdf). Contact information Y. Kachi Department of Mathematics, University of Kansas, Lawrence, KS 66045-7523, USA E-Mail(s): kachi@ku.edu Web-page: www.math.ku.edu/∼kachi/ P. Tzermias Department of Mathematics, University of Pa- tras, 26500 Rion (Patras), Greece E-Mail(s): tzermias@math.upatras.gr Web-page: www.math.upatras.gr/∼tzermias/ Received by the editors: 02.09.2014 and in final form 24.12.2014.