On partitions with K corners not containing the staircase with one more corner

Discrete Applied Mathematics 314 (2022) 162–168 Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam Note On partitions with kcorners not containing the staircase with one more corner Emmanuel Briand1 Departamento Matemática Aplicada I, Escuela Técnica Superior de Ingeniería Informática, Avda. Reina Mercedes, S/N, 41012 Sevilla, Spain article info Article history: Received 29 October 2020 Received in revised form 5 January 2022 Accepted 21 February 2022 Available online 21 March 2022 Keywords: Integer partitions abstract We give three proofs of the following result conjectured by Carriegos, De Castro-García and Muñoz Castañeda in their work on enumeration of control systems: when (k+1 2)≤ n<(k+2 2), there are as many partitions of nwith kcorners as pairs of partitions (α, β) such that (k+1 2)+ |α|+|β| = n. ©2022 Elsevier B.V. All rights reserved. 1. Introduction Integer partitions (finite weakly decreasing sequences of positive integers) are fundamental objects in enumerative combinatorics. The terms of a partition are called its parts. Several parameters are attached to a partition, such as: its length, its weight (the sum of its parts), its largest part, the size of its Durfee square (i.e. the maximum ksuch that the partition has kparts ≥k) ...Another parameter is the number of distinct sizes of its parts. It is also the number of corners in the diagram of the partition. For instance, the partition (7,4,4,2,2,2,1) has parts of 4 different sizes (7,4,2, and 1). Accordingly, its diagram has 4 corners, as shown in Fig. 1(a). We will call for short partitions with k corners the partitions with parts of kdifferent sizes. Recently, the problem of counting partitions with kcorners has arised in the context of the enumeration of linear control systems with coefficients in a commutative rings, in papers by Carriegos, De Castro-García and Muñoz Castañeda [4,5]. The present note is devoted to proving the following result that they conjectured. Theorem 1 ([4, Conjecture 30]).When (k+1 2)≤n<(k+2 2), there are as many partitions of n with k corners as pairs of partitions (α, β)such that |α|+|β| = n−(k+1 2). Note that (k+1 2)is the size of the staircase partition of length k, which is (k,k−1,k−2,...,1); see Fig. 2. We actually give three proofs of Theorem 1. The first one (Section 3) is based on generating series. The second one (Section 4) is based on an identity due to Fine on some statistics on partitions. The last one (Section 5) is a bijective proof of the following more general result. Theorem 2. For any k ≥0and m ≥0, there are as many pairs of partitions (α, β)with |α| + |β| = m whose lengths fulfill ℓ(α)+ℓ(β)≤k, as partitions of m+(k+1 2)with k corners whose diagrams do not contain the diagram of the staircase partition with length k +1. E-mail address: [email protected]. 1Funding: Partially supported by MTM2016-75024-P and FEDER, PID2020-117843GB-I00, and Proyectos I+D+i FEDER Andalucía US-1262169. https://doi.org/10.1016/j.dam.2022.02.012 0166-218X/©2022 Elsevier B.V. All rights reserved. E. Briand Discrete Applied Mathematics 314 (2022) 162–168 Fig. 1. The diagrams of the partitions λ=(7,4,4,2,2,2,1) and λ′=(7,6,3,3,1,1,1), which are conjugate of each other. Each point (i,j) of a diagram is represented as a square box centered at (i,j). Fig. 2. The diagram of (5,4,3,2,1), which is the staircase partition of length 5. Proof of Theorem 1 from Theorem 2.Consider n<(k+2 2)and set m=n−(k+1 2). Then m≤k. Observe now that all pairs of partitions (α, β) with |α| + |β| = mfulfill ℓ(α)+ℓ(β)≤ |α| + |β| = m≤k. Also, the diagram of a partition of n cannot contain the diagram of the staircase partition of length k+1, since nis smaller than (k+2 2)=1+2+ · · · + (k+1). Theorem 1 follows. □ 2. Basic facts and notations 2.1. Partitions and their diagrams In this section, we recall classical operations and notations for integer partitions. See [11], [9, I.1], [12, p. 58] or [2, Ch. I] for further details, basic definitions and general presentations. Given a partition λ=(λ1, λ2, . . .), its diagram is the set of integer points (i,j) such that 1 ≤j≤ℓ(λ) and 1 ≤i≤λj. In graphical representations, the points of the diagram of λare often drawn as square boxes centered at that point. The conjugate of λis the partition, denoted λ′, whose diagram is obtained from the diagram of λby applying the reflection that swaps the coordinates. The parts of λare the nonzero terms λ1,λ2...and the length of λ, denoted with ℓ(λ), is the number of nonzero terms (non-necessarily distinct). By λ⊢nwe mean that λis a partition of n. We call nthe weight of λ, and denote it with |λ|. For instance, the partition λ=(7,4,4,2,2,2,1) is a partition of 7 +4+4+2+2+2+1=22 (so |λ| = 22 and λ⊢22), with length 7 (denoted ℓ(λ)=7) and parts 7, 4, 4, 2, 2, 2 and 1. Its conjugate partition is λ′=(7,6,3,3,1,1,1). The diagrams of λand λ′are shown in Fig. 1. In sequences and partitions, we will make use of the notation pmfor ‘‘moccurrences of p’’. For instance, the partition (7,4,4,2,2,2,1) will be also denoted (7,42,23,1). Weakly decreasing sequences of non-negative integers with trailing zeros will be identified with the partition obtained by deleting the trailing zeros. For instance, (7,4,4,2,2,2,1,0,0,0) will be identified to the partition (7,4,4,2,2,2,1). Consider two partitions α=(α1, α2, . . .) and β=(β1, β2, . . .). Their sum is the partition α+β=(α1+β1, α2+β2, . . .). For each i, let ai(resp. bi) be the multiplicity of iin α(resp. in β). The union of the partitions αand βis the partition (denoted α∪β) in which the multiplicity of iis ai+bi. For instance, if α=(7,4,4,2,2,2,1) and β=(4,2,1) then α+β=(7 +4,4+2,4+1,2+0,2+0,2+0,1+0) =(11,6,5,2,2,2,1) and α∪β=(7,4,4,4,2,2,2,2,1,1). The two operations are related by the identity (α+β)′=α′∪β′. 163 E. Briand Discrete Applied Mathematics 314 (2022) 162–168 2.2. Generating series Given any nonnegative integer k, the product k ∏ i=1 1 1−qi expands as ∑ a1,a2,...,ak q1a1+2a2+···+kak, where the sum is carried over all k–tuples (a1,a2,...,ak) of nonnegative integers. Interpreting each integer aias the multiplicity of ias a part of a partition with weight 1a1+2a2+· · · +kak, we see that the series also writes ∑λq|λ|, where the sum is over all partitions λwhose parts are all ≤k. It is thus the generating series for these partitions, according to their weight (i.e. for each n, the coefficient of qnin this series is the number of partitions of nwhose parts are all ≤k). Similarly, the infinite product ∞ ∏ i=1 1 1−qi is the generating series of all partitions, according to their weight,. 2.3. Corners of partitions Acorner of (the diagram of) λis a point (i,j) in the diagram of λ, such that neither (i+1,j) nor (i,j+1) is in the diagram of λ. The partitions with parts of kdistinct sizes are exactly the partitions whose diagram has kcorners. We will denote with ν(n;k) the number of partitions of nwith kcorners. Let ρk=(k,k−1,...,1). This partition is called the staircase partition of length k.Fig. 2 shows the diagram of the staircase partition of length 5. The staircase partition of length kis the smallest partition with kcorners, in a sense made precise by the following lemma, that we will use implicitly in the sequel. Lemma 3. For any k ≥0, the diagram of any partition with k corners contains the diagram of ρk. Proof. Let k≥0 and let λbe a partition with kcorners. Then λis of the form (pm1 1pm2 2· · · pmk k) with p1>p2>· · · >pk>0 and all mi>0. For each i, set µi=pi−(k−i+1). Therefore, for all i<k, we have µi−µi+1=pi−pi+1−1≥0. We have also µk=pk−1≥0. This shows that µ=(µ1, µ2, . . . , µk) is a partition. We have: λ=(ρk+µ)∪(pm1−1 1pm2−1 2· · · pmk−1 k). This shows that the diagram of λcontains the diagram of ρk.□ We will also make repeated use of the following converse of Lemma 3. Lemma 4. Let k ≥0, and let λbe a partition. If the diagram of λdoes not contain the diagram of ρk+1, then λhas at most k corners. This is the case in particular for any partition λof weight less than (k+2 2). 2.4. References on partitions with k corners It has been remarked in [1] that the number of corners is a statistic on partitions that has been seldom considered. A notable and early exception is the work of MacMahon [10] relating the enumeration of partitions according to their number of corners with number theory. MacMahon’s work was expanded by Andrews [3] with a focus on asymptotics. MacMahon provided a formula for the generating series of partitions according to their weight and number of corners (identity (1) below in Section 3, where we make use of it). Refinements for this generating series were studied by Alladi [1]. Let us mention also that part of MacMahon’s results on this topic have been rediscovered by some authors unaware of his work (for instance [8]). The sequence counting the partitions of nwith kcorners is number A116608 in The On-Line Encyclopedia of Integer Sequences [6]. Note finally that another possible name for the partitions with kcorners could have been ‘‘partitions with kdistinct parts’’, but this name is already taken and widely used for the partitions with kdistinct parts all of multiplicity 1, famous for having the same generating function as the partitions in odd parts. 164 E. Briand Discrete Applied Mathematics 314 (2022) 162–168 3. Proof with generating series In this section, we prove Theorem 1 using the generating series of the numbers ν(n;k), of partitions of nwith kcorners, which is defined as F(x,q)=∑ k,n ν(n;k)xkqn. Our starting point will be the following expression for F, due to MacMahon. Theorem 5 ([10, p. 90]; or see (3.2) in Andrews’ account [3]).The generating series F is given by F(x,q)= ∞ ∑ j=0 (x−1)jq(j+1 2) (1 −q)(1 −q2)· · · (1 −qj)· ∞ ∏ i=1 1 1−qi·(1) Proof of Theorem 1 from Theorem 5.Consider nand kas in Theorem 1. The number ν(n;k) is the coefficient of xnqkin F(x,q). In the right-hand side of (1), the summands with indices j<khave degree in xat most k−1, and thus do not contribute to the coefficient of xkqn. The expansions of the summands with indices j>kinvolve only monomials xmqd with d≥(k+2 2)>n, and thus these summands do not contribute to the coefficient of xkqn. Therefore, ν(n;k) is the coefficient of xkqnin the summand with index j=k, which is (x−1)kq(k+1 2) (1 −q)(1 −q2)· · · (1 −qk)· ∞ ∏ i=1 1 1−qi· After expanding (x−1)kas xk+terms of smaller degree in x, we get that ν(n;k) is simply the coefficient of qnin q(k+1 2) (1 −q)(1 −q2)· · · (1 −qk)· ∞ ∏ i=1 1 1−qi which is the coefficient of qn−(k+1 2)in 1 (1 −q)(1 −q2)· · · (1 −qk)· ∞ ∏ i=1 1 1−qi·(2) The left factor in (2) is the generating series for the partitions λwith parts ≤k; the right factor is the generating series for all partitions µ(see Section 2.2). Therefore, for any h, the coefficient of qhin (2) is the number of pairs of partitions (λ, µ) such that |λ|+|µ| = h, and λhas all parts ≤k. For h≤k, the condition on the sizes of the parts of λcan be dropped. This is the case in particular for h=n−(k+1 2), since n<(k+2 2)=(k+1 2)+k+1. □ 4. Proof from statistics on partitions We now give another proof of Theorem 1, based on the following result due to Fine. Theorem 6 ([7, Theorem 4 in Chapter 2]).For any r ≥0, ∑ λ⊢n(Q(λ) r)=∑ λ⊢n m1(λ)m2(λ)· · · mr(λ),(3) where Q (λ)is the number of corners of λ, and mi(λ)stands for the multiplicity of i as a part of λ. Proof of Theorem 1 from Theorem 6.Consider nand ksuch that (k+1 2)≤n<(k+2 2). After Lemma 4, the diagram of any partition of nhas at most kcorners. Apply Theorem 6 with r=k. For any λ⊢n, either λhas less than kcorners, and then (Q(λ) k)=0, or λhas exactly kcorners, and then (Q(λ) k)=1. The left-hand side in (3) is thus ν(n;k). The right-hand side is ∑ λ⊢n m1(λ)m2(λ)· · · mk(λ).(4) 165 E. Briand Discrete Applied Mathematics 314 (2022) 162–168 Fig. 3. The diagram of a partition with 4 corners, with its border coordinates (m1,m2,m3,m4;n1,n2,n3,n4).. Note that if a partition λ⊢nhas some part j>k, then at least one of its parts i≤kmust have multiplicity 0 in λ (otherwise n≤(k+2 2)cannot be fulfilled). Such a partition does not contribute to the sum (4). Consider the map (α, β)↦→ α∪β∪ρkfrom the pairs of partitions (α, β) with parts ≤k. If α=(kak· · · 2a21a1) and β=(kbk· · · 2b21b1), the image of (α, β) is the partition (kak+bk+1· · · 2a2+b2+11a1+b1+1). This shows that the number of preimages of a partition λ, under this map, is m1(λ)m2(λ)· · · mk(λ). Indeed, each pair mapped to λis determined by the choice of the multiplicities ai, that must fulfill 0 ≤ai≤mi(λ)−1 for all i, whence there are mi(λ) choices for ai. The sum (4) now interprets as the cardinality of the inverse image of the set of all partitions λ≤n. This inverse image is the set of all pairs of partitions (α, β) with parts ≤ksuch that |α| + |β| + |ρk| = n. This last condition simplifies as |α|+|β| = n−(k+1 2). Finally, since n<(k+2 2), we have that n−(k+1 2)<k+1. Therefore, the condition that the parts of αand βare all at most kcan be dropped, as it is already implied by the condition on their weights. The statement of Theorem 1 is obtained. □ 5. Bijective proof It has been shown in the introduction that Theorem 1 follows from the more general Theorem 2. In this section, a bijective proof of Theorem 2 is provided. We will use the border coordinates for partitions, that we introduce now. Let λbe a partition with kcorners. Let p1,p2,...,pkbe the distinct parts of λ, ordered increasingly; p1<p2<· · · <pk. Let q1<q2<· · · <qkbe the distinct parts of the conjugate partition λ′. For each i, let mi(resp. ni) be the multiplicity of pi(resp. qi) in λ(resp. λ′). We call the pair of sequences (m1,m2,...,mk;n1,n2,...,nk) the border coordinates of λ, since they are the lengths of the vertical and horizontal segments in the border of the diagram of λ(see Fig. 3). The border coordinates niare directly obtained as differences of consecutive parts. Precisely, nk=p1,and for all i>1,nk+1−i=pi−pi−1.(5) Indeed, p1,p2, ..., pkare the first coordinates of the corners listed from left to right, while nk−1,nk−2, ..., n1are the differences between the first coordinates of consecutive corners. The same relation holds between the miand the qi. Lemma 7. Let λbe a partition with k corners and border coordinates (m1,m2,...,mk;n1,n2,...,nk). Let p1<p2<· · · <pkbe the parts of λ, and let q1<q2<· · · <qkbe the parts of λ′. 1. Let γbe a partition whose parts are all among the parts of λ. For each i, let cibe the multiplicity of piin γ. Then the border coordinates of λ∪γare (m1+c1,m2+c2,...,mk+ck;n1,n2,...,nk). 2. Let γbe a partition such that all parts of γ′are among the parts of λ′. For each i, let dibe the multiplicity of qiin γ′. Then the border coordinates of λ+γare (m1,m2,...,mk;n1+d1,n2+d2,...,nk+dk). Proof. We prove part 1. We have λ=(pmk k· · · pm2 2pm1 1) and γ=(pck k· · · pc2 2pc1 1). Therefore (λ∪γ)=(pmk+ck k· · · pm2+c2 2pmk+c1 1). This gives the first half of the border coordinates of λ∪γ. For the second half, observe that, after (5), the nido not depend on the multiplicities of the pi, and thus remain unaffected by the union with γ. Part 2 is straightforwardly deduced from part 1 by means of the identity λ+γ=(λ′∪γ′)′, and noting that conjugation swaps the mi’s and the ni’s in the border coordinates. □ 166 E. Briand Discrete Applied Mathematics 314 (2022) 162–168 Fig. 4. The bijection (α, β)↦→ (ρ3∪β′)+αdescribed in Lemma 8. Its puts in correspondence the pairs of partitions (α, β) with |α|+|β| ≤ 3, with the partitions λwith 3 corners and weight <(5 2), whose diagrams do not contain the diagram of ρ4. This illustrates Theorem 1 for k=3. Rows correspond to the partitions α, and columns to the partitions β. The conjugate partition β′is drawn. The entry in row αand column βis the diagram of the partition (ρ3∪β′)+α. The staircase partition ρ3is left in white, and the new points of the diagram coming from αand β′are in color. Theorem 2 follows straightforwardly from the more precise lemma below. Lemma 8. The map (α, β)↦→ (ρk∪β′)+αestablishes a bijection between the pairs of partitions (α, β)such that ℓ(α)+ℓ(β)≤k, and the partitions λwith k corners whose diagrams do not contain the diagram of ρk+1. The case k=3 of the bijection defined in Lemma 8 is shown in Fig. 4. Proof. Let αand βbe two partitions whose lengths have sum at most k. There exist p≥ℓ(α) and q≥ℓ(β) with p+q=k. Set bi(resp. ai) for the multiplicity of iin β′(resp. α′). Since βhas length at most k, all parts of β′are smaller than or equal to k, and thus all parts of β′are among those of ρk.Lemma 7 applies: the border coordinates of ρk∪β′are (1 +b1,1+b2,...,1+bk;1k). The corners of the diagram of ρkare the pairs (i,k+1−i) for ifrom 1 to k. Since βhas length at most q, i.e. β′has all its parts smaller than or equal to q, performing the union with β′does not affect the columns of the diagram whose indices ifulfill i>q. Therefore, all pairs (i,k+1−i) for i>qare still corners of ρk∪β′. As a consequence, the numbers k+1−ifor i>q, which are the numbers j≤p, are still parts of (ρk∪β′)′. This shows that all parts of α′are among the parts of (ρk∪β′)′, allowing to apply again Lemma 7. The conclusion now is that the border coordinates of (ρk∪β′)+α are (1 +b1,1+b2,...,1+bk;1+a1,1+a2,...,1+ak). This shows clearly that the map Φthat sends each pair of partitions (α, β) whose lengths have sum at most kto (ρk+β′)+α is injective. Indeed, the multiplicities aiand biof α′and β′can be read from the border coordinates of Φ(α, β). Besides, since the union with β′affects only the first qcolumns of the diagram, and the sum with αaffects only the first prows, the point (q+1,p+1), that is not in the diagram of ρk, is still not in the diagram of (ρk∪β′)+α. Since q+1+p+1=k+2, this point (q+1,p+1) lies in the diagram of ρk+1. This shows that the diagram of Φ(α, β) does not contain the diagram of ρk+1. On the other hand, Φ(α, β) has kcorners exactly (since it has 2kborder coordinates). We 167 E. Briand Discrete Applied Mathematics 314 (2022) 162–168 conclude that Φtakes its values in the set Skof all partitions with kcorners whose diagrams do not contain the diagram of ρk+1. Let us now show that Φhas image Skexactly. Let λbe a partition with kcorners, whose diagram does not contain the diagram of ρk+1. There exists (i0,j0), lying in the diagram of ρk+1, but not in the diagram of λ. Since λhas kcorners, its diagram contains the diagram of ρk. Therefore (i0,j0) is not in the diagram of ρk, and belongs to the set difference of the diagram of ρk+1and the diagram of ρk. Thus i0+j0=k+2. Moreover, any point (i,j) of the diagram, and in particular any corner, must fulfill i<i0or j<j0. Let pbe the number of corners (i,j) with i<i0, and let qbe the number of corners (i,j) with j<j0. Then k≤p+q. We have p≤i0−1 since there is at most one corner in each column. Similarly, q≤j0−1, because there is at most one corner in each row. Altogether, we get k≤p+q≤(i0−1) +(j0−1) =k. As a consequence, k=p+qand p=i0−1, q=j0−1. There is one corner in each of the first pcolumns and one corner in each of the first qrows, and no corner belongs at the same time to some of the first pcolumns and to some of the first qrows. We conclude that λhas border coordinates of the form (m1,...,mq,1p;n1,...,np,1q) for some positive numbers miand ni. This coincides with the border coordinates of (ρk∪β′)+αfor β′=(qmq−1· · · 2m2−11m1−1) and α′=(pnp−1· · · 2n2−11n1−1). Clearly, partitions are determined by their border coordinates. Therefore, λis equal to (ρk∪β′)+αfor the partitions α′ and β′defined above (and α=(α′)′). This shows that all λ∈Skare in the image of Φ, which terminates the proof. □ Acknowledgments Thanks to the organizers of the XI Encuentro Andaluz de Matemática Discreta held in Sevilla in February 2020, that allowed the author to hear from Professor Carriegos the conjecture considered in the present note. Thanks to Professor Carriegos for his interest in this work. Thanks to the anonymous reviewers for their valuable comments. References [1] K. Alladi, A fundamental invariant in the theory of partitions, in: Topics in Number Theory (University Park, PA, 1997), in: Math. Appl., vol. 467, Kluwer Acad. Publ., Dordrecht, 1999, pp. 101–113. [2] G.E. Andrews, The Theory of Partitions, in: Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998, Reprint of the 1976 original. [3] G.E. Andrews, Stacked lattice boxes, Ann. Comb. 3 (2–4) (1999) 115–130, http://dx.doi.org/10.1007/BF01608779. [4] M.V. Carriegos, N. De Castro-Garcí a, A.L. Muñoz Castañeda, Partitions, diophantine equations, and control systems, Discrete Appl. Math. 263 (2019) 96–104, http://dx.doi.org/10.1016/j.dam.2018.01.015. [5] M.V. Carriegos, N. De Castro-García, Partitions of elements in a monoid and its applications to systems theory, Linear Algebra Appl. 491 (2016) 161–170, http://dx.doi.org/10.1016/j.laa.2015.05.034. [6] E. Deutsch, Sequence A116608 in The On-Line Encyclopedia of Integer Sequences, 2006, Published electronically at https://oeis.org. [7] N.J. Fine, Basic Hypergeometric Series and Applications, in: Mathematical Surveys and Monographs, vol. 27, American Mathematical Society, Providence, RI, 1988. [8] B. Kim, On the number of partitions of ninto kdifferent parts, J. Number Theory 132 (6) (2012) 1306–1313, http://dx.doi.org/10.1016/j.jnt. 2012.01.003. [9] I.G. Macdonald, Symmetric Functions and Hall Polynomials, second ed., in: Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. [10] P.A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc. (2) 19 (1) (1920) 75–113, http://dx.doi.org/10.1112/plms/s2-19.1.75. [11] I. Pak, Partition bijections, a survey, Ramanujan J. 12 (1) (2006) 5–75, http://dx.doi.org/10.1007/s11139-006-9576-1. [12] R.P. Stanley, Enumerative Combinatorics, vol. 1, second ed., in: Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. 168