A Restricted Growth Word Approach to Partitions with Odd/Even Size Blocks

Richard Ehrenborg, Dustin Hedmark, and Cyrus Hettle Department of Mathematics University of Kentucky Lexington, KY 40506-0027 USA

                   richard.ehrenborg@uky.edu
                    dustin.hedmark@uky.edu
                        cyrus.h@uky.edu

Abstract We use restricted growth words and multivariate generating functionology to obtain the ordinary generating function for the number of partitions of an n-set into k blocks of odd (respectively, even) cardinality.

1 Introduction

The Stirling numbers of the second kind S(n, k) enumerate the partitions of the set [n] = {1, 2, …, n} into k blocks. They satisfy the ordinary generating function identity

∑_{n≥k} S(n, k) · t^{n−k} = \frac{1}{(1 − t) · (1 − 2t) ⋯ (1 − kt)}.  (1)

Recall that the complete symmetric function h_{m}(x_{1}, x_{2}, …, x_{k}) satisfies the generating function identity

∑_{m≥0} h_{m}(x_{1}, x_{2}, …, x_{k}) · t^{m} = \frac{1}{(1 − x_{1}t) · (1 − x_{2}t) ⋯ (1 − x_{k}t)}.

The expression S(n, k) = h_{n−k}(1, 2, …, k) for the Stirling numbers of the second kind follows directly. For a reference on Stirling numbers, see [12, Section 1.9].

Let T_{n,k} and U_{n,k} denote the number of set partitions of the set [n] into k blocks where each block has odd (respectively, even) cardinality. These numbers have been well-studied in the literature. The classical approach is via their exponential generating functions sinh(t)^{k}/k! and (cosh(t) − 1)^{k}/k! or via a more bijective route; see [5, 10] and [1], respectively. We study the ordinary generating functions of these numbers using restricted growth words and multivariate generating functions.

In this paper we use the natural bijection between partitions and restricted growth words. Our first step is to generalize (1) to a multivariate generating function. Next, by picking up the terms where all the powers are even/odd, we obtain expressions for the ordinary generating function of partitions with each block size being odd (respectively, even). By viewing these expressions as sums over walks on the integers, we give explicit product expressions for them. Here we use homogeneous bivariate generating functions, making the proofs of the essential identities straightforward. We end with a few open questions.

2 Restricted growth words

A restricted growth word, which we abbreviate as RG-word, is a word u = u_{1}u_{2} ⋯ u_{n} with the entries in the positive integers such that u_{j} ≤ max(0, u_{1}, u_{2}, …, u_{j−1}) + 1 for all 1 ≤ j ≤ n. Let RG(n, k) denote the set of all RG-words of length n with largest entry k. The set RG(n, k) is in bijection with the set partitions of the set {1, 2, …, n} into k blocks. Namely, given an RG-word u_{1}u_{2} ⋯ u_{n}, construct a partition by letting elements i and j be in the same block if u_{i} = u_{j}. Hence the cardinality of RG(n, k) is given by the Stirling number of the second kind S(n, k). The notion of RG-words was introduced by Milne; see [7, 8, 9]. More recently, they appear in the papers [2, 3].

For an RG-word u = u_{1}u_{2} ⋯ u_{n} in RG(n, k), let x_{u} be the monomial x_{1}^{c_{1}} ⋯ x_{k}^{c_{k}}, where for all i, c_{i} is one less than the number of times the letter i appears in u. Note that the monomial x_{u} has total degree n − k. We begin by generalizing equation (1) to a multivariate version.

Theorem 1. For a non-negative integer k the sum of the monomial of an RG-word over all RG-words with largest entry k is given by

∑_{n≥k} ∑_{u∈RG(n,k)} x_{u} = \frac{1}{(1 − x_{1}) · (1 − x_{1} − x_{2}) ⋯ (1 − x_{1} − x_{2} − ⋯ − x_{k})}.

Proof. Every RG-word u has a unique factorization u = 1 · w_{1} · 2 · w_{2} ⋯ k · w_{k}, where w_{i} is a word with entries 1 through i. For any word w, let x(w) be the monomial where the power of x_{i} is the number of times i appears in w. Note that x_{u} is given by the product x(w_{1}) · x(w_{2}) ⋯ x(w_{k}). The result now follows by the sum

∑_{w_{i}} x(w_{i}) = \frac{1}{1 − x_{1} − x_{2} − ⋯ − x_{i}} ,

where w_{i} ranges over all words with entries 1 through i.

Note that by setting x_{i} = q^{i−1} · t we obtain a q-analogue of equation (1) which is due to Gould [6]; see also [2, Thm. 4.1].

Let RG^{odd}(n, k) denote the set of RG-words u in which each letter occurs an odd number of times and let RG^{even}(n, k) denote the set of RG-words u in where each letter occurs an even number of times. By the bijection between RG-words and partitions we have that |RG^{odd}(n, k)| = T_{n,k} and |RG^{even}(n, k)| = U_{n,k}.

Theorem 2. The multivariate generating functions for RG^{odd}(n, k) and RG^{even}(n, k) are given by

∑_{n≥k} ∑_{u∈RG^{odd}(n,k)} x_{u} = \frac{1}{2^{k}} · ∑_{c⃗} F (c_{1}x_{1}, c_{2}x_{2}, …, c_{k}x_{k}),  (2)

∑_{n≥k} ∑_{u∈RG^{even}(n,k)} x_{u} = \frac{1}{2^{k}} · ∑_{c⃗} c_{1} · c_{2} ⋯ c_{k} · F (c_{1}x_{1}, c_{2}x_{2}, …, c_{k}x_{k}),  (3)

where the sums are over all vectors c⃗ = (c_{1}, c_{2}, …, c_{k}) ∈ {−1, 1}^{k} and F (x_{1}, x_{2}, …, x_{k}) is the generating function in Theorem 1.

Proof. This result follows from the fact that the RG-words in RG^{odd}(n, k) have monomials with all even powers, and the words in RG^{even}(n, k) have monomials with all odd powers. All monomials containing odd powers are eliminated in the first sum and all monomials containing even powers are eliminated in the second sum.

3 Generating functions

Let W_{k}(a) be the set of all walks of length k starting at a taking steps either −1 or 1. That is, W_{k}(a) = {(a_{0}, a_{1}, …, a_{k}) ∈ ℤ^{k+1} : a_{0} = a, a_{i} − a_{i−1} ∈ {−1, 1}}. Define the rational generating functions G_{k}(s, t) and G_{k}^{±}(s, t) over the set of walks starting at 0 of length k by the sums

G_{k}(s, t) = \frac{1}{2^{k}} · ∑_{a⃗∈W_{k}(0)} \frac{1}{(s − a_{0}t) · (s − a_{1}t) ⋯ (s − a_{k}t)},

G_{k}^{±}(s, t) = \frac{1}{2^{k}} · ∑_{a⃗∈W_{k}(0)} \frac{(−1)^{(k−a_{k})/2}}{(s − a_{0}t) · (s − a_{1}t) ⋯ (s − a_{k}t)}.

Proposition 3. The generating functions G_{k}(s, t) and G_{k}^{±}(s, t) satisfy the recursions

G_{k+1}(s, t) = \frac{G_{k}(s − t, t) + G_{k}(s + t, t)}{2s},
G_{k+1}^{±}(s, t) = \frac{G_{k}^{±}(s − t, t) − G_{k}^{±}(s + t, t)}{2s},

with the initial condition G_{0}(s, t) = G_{0}^{±}(s, t) = 1/s.

Proof. Observe that the substitution s ⟼ s − j · t translates the sequence (a_{0}, a_{1}, …, a_{k}) j steps up, that is,

G_{k}(s − j · t, t) = \frac{1}{2^{k}} · ∑_{a⃗∈W_{k}(j)} \frac{1}{(s − a_{0}t) · (s − a_{1}t) ⋯ (s − a_{k}t)} .

By taking the average of G_{k}(s − t, t) and G_{k}(s + t, t), we obtain the average over all walks beginning at ±1. Divide by s, since each term of G_{k+1}(s, t) contains a factor of 1/s, and use that the set W_{k+1}(0) is given by the Cartesian product {(0)} × (W_{k}(1) ∪ W_{k}(−1)). The first recursion follows. The same proof applies to G_{k}^{±}(s, t) by considering the difference G_{k}^{±}(s − t, t) − G_{k}^{±}(s + t, t).

Proposition 4. The generating functions G_{k}(s, t) and G_{k}^{±}(s, t) are given by the products

G_{k}(s, t) = ∏_{\begin{matrix}i=−k \\ i≡k (mod 2) \end{matrix}}^{k}(s − i · t)^{−1},  (4)

G_{k}^{±}(s, t) = (2k − 1)!! · t^{k} · ∏_{i=−k}^{k}(s − i · t)^{−1}.  (5)

Proof. Let g_{k}(s, t) be the right-hand side of equation (4). We would like to prove that G_{k}(s, t) and g_{k}(s, t) are equal. Observe first that G_{0}(s, t) = 1/s = g_{0}(s, t). Next observe that

\frac{1}{(s − (k + 1)t)} + \frac{1}{(s + (k + 1)t)} = \frac{2s}{(s − (k + 1)t)(s + (k + 1)t)}.

Multiply both sides by g_{k−1}(s, t), yielding g_{k}(s − t, t) + g_{k}(s + t, t) = 2 · s · g_{k+1}(s, t). This shows that g_{k}(s, t) satisfies the same recurrence relations as G_{k}(s, t).

Let g_{k}^{±}(s, t) be the right-hand side of equation (5). We have that G_{0}^{±}(s, t) = 1/s = g_{0}^{±}(s, t). Now consider the difference

\frac{1}{(s − (k + 1)t)(s − kt)}−\frac{1}{(s + (k + 1)t)(s + kt)} = \frac{2s · (2k + 1)t}{(s − (k + 1)t)(s − kt)(s + kt)(s + (k + 1)t)}.

Multiply both sides by (2k − 1)!! · t^{k} · ∏_{i=−k+1}^{k−1}(s − i · t)^{−1}. This yields the recursion

g_{k}^{±}(s − t, t) − g_{k}^{±}(s + t, t) = 2 · s · g_{k+1}^{±}(s, t).

Combining these results yields the following generating functions.

Theorem 5. For a non-negative integer k the ordinary generating function for the number of RG-words where each entry occurs an odd or even number of times is G_{k}(1, t) or G_{k}^{±}(1, t), respectively, that is,

∑_{n≥k} T_{n,k} · t^{n−k} = ∏_{\begin{matrix}i=−k \\ i≡k (mod 2) \end{matrix}}^{k}(1 − i · t)^{−1},

∑_{n≥k} U_{n,k} · t^{n−k} = (2k − 1)!! · t^{k} · ∏_{i=−k}^{k}(1 − i · t)^{−1} .

Proof. In Theorem 2, set x_{1} = ⋯ = x_{k} = t. Note that the monomial x_{u} becomes t^{n−k} and the left-hand side of (2) and (3) becomes the generating function for the cardinality of RG^{odd}(n, k), (respectively, RG^{even}(n, k)). Next, under this substitution the term on the right-hand side corresponding to the {−1, 1}-vector c⃗ becomes the term corresponding to the walk a⃗ satisfying a_{i} − a_{i−1} = c_{i} in the function G_{k}(1, t) (respectively, G_{k}^{±}(1, t)). In the signed case we use that the sign c_{1} ⋯ c_{k} is given by (−1)^{(k−a_{k})/2}. Finally, the result follows by Proposition 4.

When k is even the generating function for T_{n,k} is given by

∑_{n≥k} T_{n,k} · t^{n−k} = \frac{1}{(1 − 2^{2} · t^{2}) · (1 − 4^{2} · t^{2}) ⋯ (1 − k^{2} · t^{2})}.

Similarly, for k odd we have

∑_{n≥k} T_{n,k} · t^{n−k} = \frac{1}{(1 − 1^{2} · t^{2}) · (1 − 3^{2} · t^{2}) ⋯ (1 − k^{2} · t^{2})}.

The generating function for U_{n,k} is given by

∑_{n≥k} U_{n,k} · t^{n−k} = \frac{(2k − 1)!! · t^{k}}{(1 − 1^{2} · t^{2}) · (1 − 2^{2} · t^{2}) ⋯ (1 − k^{2} · t^{2})}.

We now obtain the following expressions in terms of the complete symmetric function.

Corollary 6. The number of RG-words with odd (respectively, even) number of each entry is given by

T_{n,k} = \begin{cases}h_{\frac{n−k}{2}} (2^{2}, 4^{2}, …, k^{2}), & k even; \\ h_{\frac{n−k}{2}} (1^{2}, 3^{2}, …, k^{2}), & k odd, \end{cases}
U_{n,k} = (2k − 1)!! · h_{\frac{n}{2} −k}(1^{2}, 2^{2}, …, k^{2}).

Using the recurrence h_{m}(x_{1}, …, x_{k}) = x_{k} ·h_{m−1}(x_{1}, …, x_{k})+h_{m}(x_{1}, …, x_{k−1}), this corollary yields the classical recurrences for T_{n,k} and U_{n,k}.

4 Concluding remarks

Is there a bijective proof of Corollary 6? Is there a multivariate refinement of Theorem 5? For instance, is there a q-analogue of this theorem?

For more on the poset and topological structure of partitions with all blocks odd/even, see [4, 11, 13].

5 Acknowledgments

The authors thank Gábor Hetyei for his help with finding and reading reference [10]. The authors also thank Andrew Klapper, Margaret Readdy, and the referee for their comments on an earlier draft. This work was supported by a grant from the Simons Foundation (#429370, Richard Ehrenborg).

References

[1] W. Bruno, G.-C. Rota, and D. C. Torney, Probability set functions, Ann. Comb. 3 (1999), 13–25.

[2] Y. Cai, R. Ehrenborg, and M. Readdy, q-Stirling identities revisited, preprint 2016.

[3] Y. Cai and M. Readdy, q-Stirling numbers: a new view, Adv. in Appl. Math. 86 (2017), 50–80.

[4] A. R. Calderbank, P. Hanlon, and R. W. Robinson, Partitions into even and odd block size and some unusual characters of the symmetric groups, Proc. London Math. Soc.

(3) 53 (1986), 288–320.

[5] L. Carlitz, Set partitions, Fibonacci Quart. 14 (1976), 327–342.

[6] H. W. Gould, The q-Stirling numbers of the first and second kinds, Duke Math. J. 28 (1961), 281–289.

[7] S. Milne, Restricted growth functions and incidence relations of the lattice of partitions of an n-set, Adv. Math. 26 (1977), 290–305.

[8] S. Milne, A q-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc. 245 (1978), 89–118.

[9] S. Milne, Restricted growth functions, rank row matchings of partition lattices, and q-Stirling numbers, Adv. in Math 43 (1982), 173–196.

[10] A. Rényi, Új módszerek és eredmények a kombinatorikus analízisben, I., Magyar Tudományos Akadémia III. Osztály Közleményei 16 (1966), 77–105. Available at

    http://real-j.mtak.hu/499/1/MATFIZ_16.pdf.

[11] R. P. Stanley, Exponential structures, Studies Appl. Math 59 (1978), 73–82.

[12] R. P. Stanley, Enumerative Combinatorics, Vol. 1, second edition. Cambridge University Press, 2012.

[13] M. L. Wachs, A basis for the homology of the d-divisible partition lattice, Adv. Math. 117 (1996), 294–318.

2010 Mathematics Subject Classification: Primary 05A18; Secondary 05A15. Keywords: set partition, restricted growth word, multivariate generating function.

(Concerned with sequences \underline{A136630} and \underline{A156289}.)

Received December 9 2016; revised version received April 29 2017. Published in Journal of Integer Sequences, April 30 2017.

Return to Journal of Integer Sequences home page.