#A56 INTEGERS 24 (2024) CASTING LIGHT ON INTEGER PARTITIONS Aubrey Blecher The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, South Africa aubrey.blecher@wits.ac.za Arnold Knopfmacher The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, South Africa arnold.knopfmacher@wits.ac.za Michael Mays Department of Mathematics, West Virginia University, Morgantown, West Virginia mmays@mail.wvu.edu Received: 1/23/23, Revised: 3/20/24, Accepted: 5/16/24, Published: 6/19/24 Abstract Integer partitions of n are viewed as bargraphs (i.e., Young diagrams rotated anti- clockwise by 90 degrees) in which the ith part of the partition xi is given by the ith column of the bargraph with xi cells. The sun is at infinity in the northwest of our two dimensional model and each cell may or may not be lit depending on whether it stands in the shadow cast by another cell to its left. The partition being ordered either as weakly increasing or weakly decreasing yields different generating functions and we consider both cases. We study the number of lit cells in partitions of n in their bargraph representation. In the weakly increasing case the generating function is straightforward, but in the weakly decreasing case we define triangular q-binomial coefficients which are analogous to standard q-binomial coefficients and we obtain a formula for these. We also study lit nodes in rotated Ferrers diagrams. 1. Introduction A partition of a positive integer n is a way of writing n as a sum of positive integers, n = ∑ xi. Two sums that differ only in the order of their parts xi are considered to be the same partition, so the parts are usually ordered as weakly increasing or weakly decreasing. Partitions with weakly decreasing parts have natural geometric DOI: 10.5281/zenodo.12167489 INTEGERS: 24 (2024) 2 representations as arrays of circles or squares. A Ferrers diagram represents a par- tition as rows of circles, with xi circles in row i. A Young diagram uses touching square cells in the same arrangement. Books by Andrews and Eriksson ([1] and [2]) are good sources for general information about partitions. Representations of n as a sum in which the order of summands matters are called compositions. As has become common practice in many recent papers, an integer composition of n with k parts is modeled by a bargraph with k columns in which the ith part, xi, is represented by column i of the bargraph of height xi. We adopt this convention here also for integer partitions to write weakly decreasing partitions as Young diagrams rotated anticlockwise by 90 degrees. See Figure 1 for the geometry of our represen- tations. Since we are studying partitions represented as both weakly increasing and weakly decreasing bargraphs, we also reverse the rotated representation in Figure 1 to get the bottom right representation as a weakly increasing bargraph. Figure 1: 5+4+4+2+2+2+1+1 as a Young diagram and as decreasing and increas- ing bargraphs. The geometric description of a partition as a bargraph opens the door to studying geometric properties of the bargraph. For example, in [5] the relevant statistic is the number of corners of the bargraph of a composition, and in [4] the focus is on how many cells would be bounded by higher values to the left or right to “hold water.” In this paper we are interested in cells that would be illuminated by a source of light. We position the sun at infinity in the northwest and consider the problem of how many of the cells in the bargraph representation of the partition are lit by the sun (and hence also how many are in the shade). The idea of such lit cells has been studied before (see [3]) in the paradigm of words over a fixed alphabet k and also in [6] where the paradigm is compositions of n. However, specific to the case INTEGERS: 24 (2024) 3 of weakly increasing partitions, if we change the bargraph model by replacing the aforementioned square cells by small circular nodes in the center of each such cell, as illustrated in Figure 2, we get a different pattern of lit elements. Hence we find that the generating function for the number of lit nodes is different from that of lit cells. We will derive results for lit elements in the weakly increasing case in Section 3 and results for the weakly decreasing case in Sections 4, 5, and 6. Figure 2: Three lit cells, five lit nodes. 2. Background and Tools An important analytic tool in our analysis is the bivariate generating function for partitions in which v tracks the number of parts. It is given by the following expression: P (q, v) = ∞∏ i=1 1 1− vqi . (1) The total number of parts across all partitions of n is given by the following expres- sion: ∂P (q, v) ∂v ∣∣∣ v=1 = P (q) ∞∑ i=1 qi 1− qi , (2) where P (q) = P (q, 1). From the conjugate of the Ferrers diagram for a partition, the total number of parts across all partitions is equal to the sum of the largest parts. The number of distinct parts tracked by u is given by the following: P2(q, u) = ∞∏ i=1 ( 1 + uqi 1− qi ) . (3) Thus the total number of distinct parts across all partitions of n is given by the following expression: ∂P2(q, u) ∂u ∣∣∣ u=1 = P (q) q 1− q . (4) INTEGERS: 24 (2024) 4 The product representation and the partial derivative embody an important dis- tinction for two independent combinatorial problems of interest. We can consider individual partitions of n, or we can consider the set of all partitions of n and in- vestigate properties of the aggregate, such as the total number of parts among all partitions of n. Our results are in the tradition of analysis of partition statistics ex- emplified by [9], [10], [16], and [17], and the more basic topic of classifying partitions by the nature of their parts as in [8], [11], and [13]. 3. Weakly Increasing Partitions Here we consider weakly increasing partititions lit by light at infinity in the north- west, represented either with a square cell Young diagram bargraph or a circular node Ferrers diagram. We illustrate this using the partition {1,1,3,3,3,5,6,7,7,7,7} where the ith coor- dinate represents the ith column of the partition. Note for example, that in Figure 3 the bottom cell in column three of the square cell picture is not lit whereas it is in the node picture. Figure 3: Several unlit cells are lit nodes. First we deal with the square cell case. Proposition 1. The generating function for the number of lit cells among all weakly increasing partitions of n is given by the following formula: 2P (q) ∞∑ i=1 qi 1− qi − P (q)q 1− q = P (q) ∞∑ i=1 qi ( 1 + qi ) 1− qi . (5) Proof. In the square cell diagrams, the number of lit cells equals the largest part plus the number of parts minus the number of distinct parts. This is because the number of cells which are lit on their western boundary equals the size of the largest part; those that are lit on the northern boundary equals the number of parts and INTEGERS: 24 (2024) 5 those that are double counted (i.e., lit from both directions) equals the number of distinct parts. For lit cells in skew partitions we subtract one for each column that exceeds the previous column by two or more. We will make use of the fact that the multiplicity of all repeated parts plus the number of non-repeated parts is equal to the total number of parts. We use the expressions for the number of distinct parts in Equation (1) and the total number of distinct parts in Equation (2) to see the generating function for the number of lit cells is given in 2P (q) ∞∑ i=1 qi 1− qi − P (q)q 1− q = P (q) ∞∑ i=1 qi ( 1 + qi ) 1− qi , (6) as claimed. The series expansion for this function is q+4q2+8q3+17q4+28q5+51q6+78q7+127q8+189q9+287q10+411q11+O ( q12 ) . We verify the bolded term in the equation above in Figure 4, which shows a total of 17 lit cells among all the partitions of 4. This is sequence A366069 in [14]. Figure 4: 17 lit cells in partitions of 4. Now we consider lit nodes in the Ferrers diagram representation of a weakly increasing partition. Proposition 2. The generating function for the number of lit nodes in weakly increasing partitions of n is given by the following: 1 + P (q) ( ∞∑ i=1 2qi 1− qi − 1 ) . (7) Proof. In the node diagrams, the number of lit nodes equals the largest part plus the number of parts minus one. In addition to the lit square cell positions there is an extra lit node for each distinct part size excluding the largest part. For skew INTEGERS: 24 (2024) 6 partitions the number of lit nodes is the size of largest part. We again make use of the fact that the multiplicity of all repeated parts plus the number of non-repeated parts is equal to the total number of parts. With these changes, the generating function simplifies to 1 + P (q) ( ∞∑ i=1 2qi 1− qi − 1 ) , (8) as claimed. The series expansion for this function is q+4q2+9q3+19q4+33q5+59q6+93q7+150q8+226q9+342q10+494q11+721q12+O ( q13 ) . We verify the bolded term in the equation above in Figure 5, which shows 19 lit nodes among all the partitions of 4. The sequence of coefficients is A179862 in [14]. Figure 5: 19 lit nodes in the 5 partitions of 4. 4. Triangular q-Binomial Coefficients In this section we are interested in weakly decreasing partitions. We can constrain such partitions by the total number of parts or by the maximum size of parts. In general, see [2], a standard q-binomial coefficient ( N+m m ) q is the partition generating function( N + m m ) q = ∑ n≥0 p(n : ≤ m parts, each ≤ N)qn, where p(n : ≤ m parts, each ≤ N) counts partitions of n into at most m parts, each ≤ N . For example,( 7 3 ) q = ( 4 + 3 3 ) q = 1+q+2q2+3q3+4q4+4q5+5q6+4q7+4q8+3q9+2q10+q11+q12, INTEGERS: 24 (2024) 7 where the term in bold represents the 4 partitions of 7, namely {43, 421, 331, 322}, with a maximum of 3 parts and a maximum part size of 4. Note that partitions counted by ( N+m m ) q have bargraphs that fit inside a “bound- ing rectangle” of width m and height N . We modify this generating function slightly and define a triangular q-binomial coefficient t[r, s]q = t[r, s] to be the generating function for all weakly decreasing partitions with exactly s parts that are contained in a modified figure in which the upper boundary is a decreasing staircase with column heights r, r − 1, ..., r − s + 1. We use q to track the size of partitions that fit inside the modified figure, which we will call a bounding trapezoid. This trapezoid can be thought of as a rectangle surmounted by a triangle. For example, t[4, 3] = q3 + q4 + 2q5 + 3q6 + 3q7 + 3q8 + q9, where the term in bold represents the 3 partitions {411, 321, 222} of 6 that fit inside the bounding trapezoid with columns of heights 4, 3, 2. We set up a recursion for t[r, s]q = t[r, s]. We obtain the following result. Proposition 3. The generating function t[r, s] satisfies the recursion t[r, s] = qs s∑ i=0 t[r − 1, i]. (9) The initial conditions for the recursion are: t[1, 1] = q; t[2, 1] = q(1 + q); t[r, 0] = 1 if r ≥ 0; t[r, s] = 0 if s > r ≥ 0. (10) Proof. Since t[r, s] is the generating function for partitions with exactly s parts, the bottom row of the bargraph modeling such partitions must be completely filled. To construct the recursion we remove the bottom row with generating function qs from the model, and above it we have one of the bounding trapezoids with maximum part size r − 1 and i parts. This leads to Equation (9) above. Next, we obtain an alternative formula for t[r, s] which displays more clearly its relationship to standard q-binomial coefficients. Many of the partitions counted by t[r, s] are also counted in the q-binomial qs ( r+s−1 s ) q , which counts all partitions with exactly s parts (like t[r, s]) and maxi- mum part size r. To find an equation relating the two, we remove from qs ( r+s−1 s ) q all partitions not counted in t[r, s]. To do this systematically and uniquely, we use the index i to specify the leftmost column where a partition is counted in the q- binomial but not in the triangular q-binomial. For example when r = 8, s = 5 and INTEGERS: 24 (2024) 8 i = 4, we illustrate this situation in Figure 6 below. The blue part represents the modified triangle in which the partitions are counted by t[r, s]. The yellow cell is the first column in which a partition counted by the q-binomial generating function is not also counted by t[r, s]. Figure 6: Counting by q-binomials. This ith part must be at least r− i+2, because a part of lesser height would still have the first i parts counted in the triangular q-binomial generating function. To the left of this column, all partitions whose first i−1 columns are weakly decreasing partitions with these i− 1 parts having respective heights lying between maximum values r, r− 1, r− 2, . . . , r− (i− 1) and minimum value for each of these columns of r−(i−1). Since the top of all these columns lie above a rectangle of height r−i and width i−1, the generating function for the first i parts of these partitions counted by t[r, s] is t[i−1, i−1]q(r−i+1)(i−1). The ith part has generating function qr−i+2. The removal of this particular ith part from the q-binomial generating function means that this together with all allowed parts in the rectangle to the right of the ith part must also be removed from those counted in the q-binomial generating function. The generating function for these is itself a q-binomial generating function where the bottom row of width s− i (and generating function qs−i) of this rectangle must be filled (since there must be s parts in the overall rectangle). Above this bottom row is a rectangle representing the generating function for partitions with at most s−i parts and maximum part size r−i+1. So, to summarize, the generating function for the allowed rectangle to the right of the ith column is qs−i ( r−i+1+s−i s−i ) q . Putting all this together, we obtain the following: t[r, s] = qs ( r + s− 1 s ) q − s∑ i=2 t[i−1, i−1]q(r−i+1)(i−1)qr−i+2qs−i ( r − i + 1 + s− i s− i ) q . (11) Simplifying this equation, we obtain the following result. INTEGERS: 24 (2024) 9 Proposition 4. The triangular q-binomial coefficients t[r, s] are also given by the following formula: t[r, s] = qs ( r + s− 1 s ) q − qs+1 s∑ i=2 t[i− 1, i− 1]qi(r−i) ( r − 2i + 1 + s s− i ) q , (12) where t[r, s] satisfies the initial conditions given in Equation (10). Definition 1. We also define Tq(r) := ∑r s=0 t[r, s] which is the generating function for all decreasing partitions contained in the triangle r, r − 1, ..., 1. For example, Tq(4) = 1 + q + 2q2 + 3q3 + 5q4 + 5q5 + 7q6 + 7q7 + 6q8 + 4q9 + q10, where the term in bold represents the 7 partitions of 6 which fit in the triangle 4321, namely {42, 411, 33, 321, 3111, 222, 2211}. 5. Weakly Decreasing Partitions We fix the positive integer value k and set out initially to find all partitions with ≤ s parts that have a maximum number of k lit cells. There is no difference between lit cells and lit nodes for weakly decreasing partitions. Following the creative idea of Prodinger in [12], the problem of identifying lit elements can be simplified as follows: we consider the bijection specified below which maps each weakly decreasing partition of n with j parts to the super-diagonal (or skew, in Prodinger’s terms) composition of n + ( j−1 2 ) . This bijection is defined by mapping each original ith part xi to the new ith part xi + i− 1 (and its reverse for the inverse). The image objects for this bijection are super-diagonal compositions (i.e., compositions in which the ith part ≥ i) which are so called 1-compositions (i.e., compositions in which successive parts are not allowed to increase by more than 1). The simplifying modification is that we now consider the image composition to be lit by light coming from the sun on the western horizon, and the number of such lit cells in the image composition is the same as the number of lit cells in the original partition (when lit by the northwest sun). Moreover, this number is simply given by the largest part that occurs in the image composition. This is all very nicely explained by Prodinger in the introduction to [12], and we recommend this paper to the reader. Other papers dealing with skew or super-diagonal bargraphs are found in [7] and [15]. The number of lit cells in an integer partition with i ≤ s parts is identical to the size of the largest part of this integer partition after the staircase partition 0, 1, 2, . . . , i − 1 has been added to it. In other words the latter object needs to be entirely contained in the k × s bounding rectangle which is used to define the INTEGERS: 24 (2024) 10 Figure 7: 5+4+4+2+2 and its skew diagram, inside bounding shapes. q-binomial coefficient that counts all partitions with maximum part size k and maximum number of parts s. This is equivalent to the original partition being entirely contained in the k × i bounding rectangle after subtracting the staircase partition from it. The generating function for such partitions is given by t[k, s]q. We see in Figure 7 a partition lit by northwest light and its skew diagram built by adding the staircase, with the same number of cells lit by west light. Now we let lit[k, s] be the generating function for partitions with at most s + 1 parts and which have less than or equal to k cells lit. The first i parts of such partitions are modeled as a modified rectangle (see t[r, s]) in Section 4) in which the i columns are bounded above by k, (k−1), · · · , (k− i+1) and therefore have a generating function t[k, i]qi(k−s). This is followed immediately by any (bottom justified) partition with a maximum number of parts s + 1− i and a maximum part size of k − s. The generating function for the latter is given by( k−s+s+1−i s+1−i ) q . Altogether, by summing over the range of possible values for i, we have proved the following result. Proposition 5. The generating function lit[k, s] for all partitions with at most s+1 parts and a maximum of k lit cells is given by the following expression: lit[k, s] := s∑ i=0 t[s, i]qi(k−s) ( k + 1− i k − s ) q . (13) For example, we calculate from Equation (13) that lit[4, 2] = 1 + q + 2q2 + 3q3 + 4q4 + 4q5 + 5q6 + 4q7 + 3q8 + q9. The term in bold counts partitions of 7 with at most 3 parts, and at most 4 lit cells. The four such partitions are shown in Figure 8. INTEGERS: 24 (2024) 11 Figure 8: Partitions of 7 with at most 3 parts, and at most 4 lit cells. Next, lit[k, s]− lit[k− 1, s] is the generating function for partitions with at most s + 1 columns that have exactly k lit cells. Therefore k(lit[k, s]− lit[k − 1, s])− k(lit[k, s− 1]− lit[k − 1, s− 1]) is the generating function for partitions with exactly s+1 columns that have exactly k lit cells. Definition 2. Define L(q) to be the generating function for the total number of lit cells in weakly decreasing partitions of n, tracked by q. Therefore, L(q) : = ∞∑ k=1 k−1∑ s=0 k(lit[k, s]− lit[k − 1, s])− k(lit[k, s− 1]− lit[k − 1, s− 1]) = ∞∑ k=1 k−1∑ s=0 k(lit[k, s]− lit[k, s− 1])− k(lit[k − 1, s]− lit[k − 1, s− 1]). (14) We simplify the above by using lit[k, s]− lit[k, s− 1] = t[k, s + 1]. This is obtained by using the fact that the left side of the above equation is the generating function for partitions with exactly s + 1 parts and a maximum of k lit cells (see Proposition 5) and this is also the meaning of the right side of the above equation. Thus L(q) = ∞∑ k=1 k−1∑ s=0 (kt[k, s + 1]− kt[k − 1, s + 1]) = ∞∑ k=1 k∑ s=1 (kt[k, s]− kt[k − 1, s]). INTEGERS: 24 (2024) 12 To simplify further let us temporarily take the k sum up to some finite integer M and also recall Definition 1 of Tq(k). We define LM (q) as LM (q) : = M∑ k=1 k∑ s=1 (kt[k, s]− kt[k − 1, s]) = M∑ k=1 k∑ s=1 kt[k, s]− M−1∑ k=0 k∑ s=1 (k + 1)t[k, s] = M∑ r=1 Mt[M, r]− M−1∑ k=1 k∑ r=1 t[k, r] = M(Tq(M)− 1)− M−1∑ k=1 (Tq(k)− 1) = M−1∑ k=0 (Tq(M)− Tq(k)). (15) We now use the fact that, at least in the sense of formal power series, the limit as M → ∞ of Tq(M) is P (q), the generating function for all partitions of n from Section 2, and limM→∞ LM (q) = L(q). So we have now proved the following result. Theorem 1. The generating function for the total number of lit cells in weakly decreasing partitions of n, tracked by q satisfies L(q) = ∞∑ k=0 (P (q)− Tq(k)). (16) The series expansion of L(q) begins q+4q2 +8q3 +17q4 +27q5 +49q6 +74q7 +118q8 +174q9 +263q10 +371q11 +540q12. The term in bold means that the partitions of 4, namely {4, 31, 22, 211, 1111}, have 17 lit cells, which is indeed the case, as shown in Figure 9. Figure 9: 17 lit cells in weakly decreasing partitions of 4. This sequence of coefficients is A366157 in [14]. INTEGERS: 24 (2024) 13 6. Weakly Decreasing Partitions with Only the First Column Lit Let us consider the problem in which only the first column of height r + 1 of a partition of n is lit. If the first column is the only lit column and s represents the number of parts in such partitions, then 0 ≤ s ≤ r + 1. By stripping off the first column, we see that the generating function for such partitions is given by the following: qr+1 r∑ s=0 t[r, s] = qr+1Tq(r). Next, we set up a bivariate generating function T (u, q) which counts all weakly decreasing partitions in which only the first column of size tracked by u is lit and in which as usual q tracks the size of the partition. We obtain the following expression: T (u, q) = ∑ r≥1 ur+1qr+1Tq(r). By differentiating the above equation, we obtain our last result. Proposition 6. The generating function for the total number of lit cells in parti- tions of n with only the first column lit is given by the following expression: ∂T (u, q) ∂u ∣∣∣ u=1 = ∑ r≥1 (r + 1)qr+1Tq(r). The series expansion begins 2q2+5q3+7q4+15q5+22q6+35q7+54q8+86q9+115q10+175q11+248q12+351q13. This sequence of coefficients is A366175 in [14]. The bold term above is illustrated by the partitions {4, 31} of 4 which have a total of 7 lit cells. We see these cells lit in the first two partitions in Figure 9. Acknowledgement. We thank the referee for a thoughtful report with many clarifying suggestions. References [1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, MA, 1976; reissued: Cambridge University Press, Cambridge, 1988. [2] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, Cambridge, 2004. [3] M. Archibald, A. Blecher, C. Brennan, A. Knopfmacher, and T. Mansour, Shedding light on words Appl. Anal. Discrete Math. 11 (2017), 216–231. INTEGERS: 24 (2024) 14 [4] A. Blecher, C. Brennan, and A. Knopfmacher, The water capacity of integer compositions, Online J. Anal. Comb. 13 (2018), #06. [5] A. Blecher, C. Brennan, A. Knopfmacher, and T. Mansour, Counting corners in partitions, Ramanujan J. 39 (2016), 201–224. [6] A. Blecher, A. Knopfmacher, and M. Mays, Casting light on compositions, submitted. [7] E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs, J. Statist. Plann. Inference 140 (6) (2010), 1550–1562. [8] P. Erdös and J. Lehner, The distribution of the number of summands in the partition of a positive integer, Duke Math. J. 8 (1941), 335–345. [9] P. Grabner and A. Knopfmacher, Analysis of some new partition statistics, Ramanujan J. 12 (2006), 439–453. [10] P. Grabner, A. Knopfmacher and S. Wagner, A general asymptotic scheme for moments of partition statistics, Combin. Probab. Comput. 23 (2014), 1057–1086. [11] M. Hirschhorn, The number of different parts in the partitions of n, Fibonacci Quart. 52 (2014), 10–15. [12] H. Prodinger, Visibility problems related to skip lists, Australas. J. Combin. 72 (3) (2018), 509-515. [13] D. Ralaivaosaona, On the distribution of multiplicities of integer partitions, Ann. Comb. 16 (2012), 871–889. [14] The On-line Encyclopedia of Integer Sequences, The OEIS Foundation Inc., (https://oeis.org/). [15] E. J. Janse Van Rensburg, Adsorbing bargraph paths in a q-wedge, J. Phys. A 38 (2005), 8505–8525. [16] S. Wagner, On the distribution of the longest run in number partitions, Ramanujan J. 20 (2009), 189–206. [17] S. Wagner, Limit distributions of smallest gap and largest repeated part in integer partitions, Ramanujan J. 25 (2011), 229–246.