The Minimal Excludant in Integer Partitions

George E. Andrews The Pennsylvania State University University Park, PA 16802 USA

                     gea1@psu.edu

David Newman Far Rockaway, New York USA

                DavidSNewman@gmail.com

Abstract

The minimal excludant, or “mex” function, on a set S of positive integers is the least positive integer not in S. In this paper, the mex function is extended to integer partitions generalized by constricting the universal set from all positive integers to those in certain arithmetic progressions. There are numerous surprising partition identities connected with this restricted mex function. This paper provides an account of some of the most conspicuous cases.

1 Introduction

The minimal excludant function (mex-function) appears extensively in combinatorial game theory (e.g., [7]). For each set S of nonnegative integers we define it as follows:

mex(S) = min(ℤ_{≥0}\S).  (1)

The mex function is perhaps best known in its uses in the game of nim and the Sprague-Grundy theory originating in the 1930’s.

We shall generalize the mex-function to apply to integer partitions. We define mex_{A,a}(π) to be the smallest integer congruent to a modulo A that is not a part of the integer partition π.

We define p_{A,a}(n) to be the number of partitions π of n, where

mex_{A,a}(π) ≡ a (mod 2A),  (2)

and \overline{p}_{A,a}(n) to be the number of partitions π of n, where

mex_{A,a}(π) ≡ A + a (mod 2A).  (3)

If p(n) denotes the number of integer partitions of n, then clearly

p(n) = p_{A,a}(n) + \overline{p}_{A,a}(n).  (4)

For example, consider n = 4, A = 2, and a = 1. There are five partitions of 4, so p(4) = 5, where p(n) is the number of partitions of n. These partitions along with first missing odd part (m.o.) are 4 (m.0. 1), 3 + 1 (m.o. 5), 2 + 2 (m.o. 1), 2 + 1 + 1 (m.o. 3) and 1 + 1 + 1 + 1 (m.o. 3). Thus three partitions have mex_{2,1} congruent to 1 mod 4, and two have mex_{2,1} congruent to 3 mod 4. Thus p_{2,1}(4) = 3 and \overline{p}_{2,1}(4) = 2.

Let us define

F_{A,a}(q) = ∑_{n≥0} p_{A,a}(n)q^{n},  (5)

and

\overline{F}_{A,a}(q) = ∑_{n≥0} \overline{p}_{A,a}(n)q^{n}.  (6)

Then

F_{A,a}(q) + \overline{F}_{A,a}(q) = ∑_{n≥0} p(n)q^{n}  (7)

= ∏_{n=1}^{∞} \frac{1}{1 − q^{n}} := F (q), by [2, p. 3, Th. 1.1].

Thus by (7), every identity for F_{A,a}(q) yields a natural identity for \overline{F}_{A,a}(q) and vice versa.

Our theorems also require p_{e}(n) (resp., p_{o}(n)), the number of partitions of n into an even (resp., odd) numbers of parts. Hence by the methods of [2, Ch. 1], we get

F_{e}(q) := ∑_{n≥0} p_{e}(n)q^{n} = ∑_{n=0}^{∞} \frac{q^{2n}}{(q; q)_{2n}} ,  (8)

and

F_{o}(q) := ∑_{n≥0} p_{o}(n)q^{n} = ∑_{n=0}^{∞} \frac{q^{2n+1}}{(q; q)_{2n+1}} ,  (9)

where

(x; q)_{n} = (1 − x)(1 − xq) ⋯ (1 − xq^{n−1}).  (10)

In order to prove our theorems for p_{1,1}(n) and p_{3,3}(n), we must recall two partition statistics, the rank and the crank.

The rank of a partition is the largest part minus the number of parts. The crank of a partition is the largest part of the partition if there are no ones as parts, and otherwise is the number of parts larger than the number of ones minus the numbers of ones.

Our first theorem (which is actually a lemma for treating p_{1,1}(n)) is originally due to Uncu [10]. Our proof differs from his and is included for completeness. Also see Somos [9].

Theorem 1. The generating function for partitions with non-negative crank is

\frac{1}{(q; q)_{∞}} ∑_{n≥0}(−1)^{n}q^{\binom{n+1}{2}}.  (11)

This leads directly to the following three results:

Theorem 2. p_{1,1}(n) equals the number of partitions of n with non-negative crank.

Theorem 3. p_{3,3}(n) equals the number of partitions of n with rank ≥ −1.

Theorem 4. p_{2,1}(n) = p_{e}(n).

Our last two theorems are the real surprises in this study. The theory of partitions is replete with uncanny partition identities, of which the first Rogers-Ramanujan identity is the most famous example:

Theorem 5 (Rogers-Ramanujan). [2, Ch. 7] The number of partitions of n in which the difference between parts is at least 2 equals the number of partitions of n in which all parts are congruent to 1 or 4 modulo 5.

It turns out that p_{4,2}(n) and p_{6,3}(n) appear in identities of this nature.

Theorem 6. p_{4,2}(n) − p_{o}(n) equals the number of partitions of n into parts congruent to ±4, ±6, ±8, ±10 (mod 32).

Theorem 7. p_{6,3}(n) − p_{o}(n) equals the number of partitions of n into parts congruent to ±2, ±4, ±5, ±6, ±7, ±8 (mod 24).

Table 1 gives the first few values of these sequences.

\begin{matrix}n & p_{11}(n) & p_{33}(n) & p_{21}(n) & p_{42}(n) & p_{63}(n) \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 2 & 1 & 2 & 1 & 1 & 2 \\ 3 & 2 & 2 & 1 & 2 & 2 \\ 4 & 3 & 4 & 3 & 3 & 4 \\ 5 & 4 & 5 & 3 & 4 & 5 \\ 6 & 6 & 8 & 6 & 6 & 8 \\ 7 & 8 & 10 & 7 & 8 & 10 \\ 8 & 12 & 15 & 12 & 12 & 15 \\ 9 & 16 & 20 & 14 & 16 & 19 \\ 10 & 23 & 28 & 22 & 22 & 27 \\ 11 & 30 & 36 & 27 & 29 & 34 \\ 12 & 42 & 50 & 40 & 40 & 48 \\ 13 & 54 & 64 & 49 & 52 & 60 \\ 14 & 73 & 86 & 69 & 69 & 81 \\ 15 & 94 & 110 & 86 & 90 & 102 \\ 16 & 124 & 145 & 118 & 118 & 135 \\ 17 & 158 & 184 & 146 & 151 & 169 \\ 18 & 206 & 238 & 195 & 195 & 220 \\ 19 & 260 & 300 & 242 & 248 & 224 \\ 20 & 334 & 384 & 317 & 317 & 352 \\ 21 & 419 & 481 & 392 & 400 & 437 \\ 22 & 531 & 608 & 505 & 505 & 554 \\ 23 & 662 & 756 & 623 & 632 & 684 \\ 24 & 832 & 948 & 793 & 793 & 860 \\ 25 & 1029 & 1172 & 973 & 985 & 1057 \end{matrix}

Table 1: First few values of p_{1,1}, p_{33}(n), p_{21}(n), p_{42}(n), and p_{63}(n)

We note that p_{1,1}(n) is sequence \underline{A064428} in the On-Line Encyclopedia of Integer Sequeces (OEIS), p_{3,3}(n) is \underline{A260894}, p_{2,1}(n) is \underline{A027187}, and p_{4,2}(n) is \underline{A046682}. We also note that none of the references to these sequences in the OEIS refer to our results.

We note that the proof of Theorem 3 relies on the study of Garden of Eden partitions given by Hopkins and Sellers [8], while Theorem 6 and 7 rely on identities given by Blecksmith, Brillhart and Gerst [5].

2 Uncu’s theorem

If M(m, n) denotes the number of partitions of n with crank m, then [4]

∑_{n=0}^{∞} ∑_{m=−∞}^{∞} M(m, n)z^{m}q^{n} = \frac{(q; q)_{∞}}{(zq; q)_{∞}(z^{−1}q; q)_{∞}} .  (12)

Now by [2, p. 19, Eq. (2.2.5)] we have

\frac{(q; q)_{∞}}{(zq; q)_{∞}(z^{−1}q; q)_{∞}} = (q; q)_{∞} ∑_{m=0}^{∞} \frac{z^{m}q^{m}}{(q; q)_{m}} ∑_{n=0}^{∞} \frac{z^{−n}q^{n}}{(q; q)_{n}} .  (13)

Thus the generating function for partitions with non-negative crank consists of those terms on the right-hand side of (13), where the exponent on z is non-negative. Hence the required generating function is

(q; q)_{∞} ∑_{n=0}^{∞} ∑_{m=n}^{∞} \frac{q^{m+n}}{(q; q)_{m}(q; q)_{n}} = (q; q)_{∞} ∑_{n=0}^{∞} ∑_{m=0}^{∞} \frac{q^{m+2n}}{(q; q)_{m+n}(q; q)_{n}}

= (q; q)_{∞} ∑_{m=0}^{∞} \frac{q^{m}}{(q; q)_{m}} ∑_{n=0}^{∞} \frac{q^{2n}}{(q; q)_{n}(q^{m+1}; q)_{n}}

= (q; q)_{∞} ∑_{m=0}^{∞} \frac{q^{m}}{(q; q)_{m}(q^{2}; q)_{∞}(q^{m+1}; q)_{∞}}

× ∑_{n=0}^{∞} \frac{(−1)^{n}q^{\binom{n+1}{2}+mn}(q^{2}; q)_{n}}{(q; q)_{n}}

(by [2, p. 19, Cor. 2.3, a = b = 0, c = q^{m+1}, t = q^{2}])

= \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{\binom{n+1}{2}}(1 − q^{n+1}) ∑_{m=0}^{∞} q^{m(n+1)}

= \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{\binom{n+1}{2}}.

3 Background lemmas

Lemma 8.

F_{2k,k}(q) = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{kn^{2}}.  (14)

Proof.

\frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{kn^{2}} = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{4kn^{2}}(1 − q^{4kn+k})

= \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{k+3k+5k+···+k(4n−1)}(1 − q^{k(4n+1)})

= ∑_{n=0}^{∞} \frac{q^{k+3k+5k+···+k(4n−1)}}{∏_{\begin{matrix}m=1 \\ m≠k(4n+1) \end{matrix}}^{∞}(1 − q^{m})} ,

and thus this last expression is clearly the generating function for p_{2k,k}(n). Lemma 9.

F_{k,k}(q) = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{k\binom{n+1}{2}}.  (15)

Proof.

\frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{k\binom{n+1}{2}} = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{k\binom{2n+1}{2}}(1 − q^{k(2n+1)})

= \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{k+2k+···+2nk}(1 − q^{k(2n+1)})

= ∑_{n=0}^{∞} \frac{q^{k+2k+···+2nk}}{∏_{\begin{matrix}m=1 \\ m≠k(2n+1) \end{matrix}}^{∞}(1 − q^{m})},

and this last expression is clearly the generating function for p_{k,k}(n).

4 Proof of Theorem 2

Proof.

∑_{n=0}^{∞} p_{1,1}(n)q^{n} = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{\binom{n+1}{2}} (by Lemma 9 with k = 1)

and by Theorem 1, this is the generating function for partitions with non-negative crank.

5 Proof of Theorem 3

Proof. In [8], Hopkins and Sellers prove that Garden of Eden partitions are equinumerous with partitions whose rank is ≤ −2. They then quote the work of Dyson [6] to reveal that this generating function is

\frac{1}{(q; q)_{∞}} ∑_{n=1}^{∞}(−1)^{n−1}q^{3\binom{n+1}{2}}.

Hence

F_{3,3}(q) = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{3\binom{n+1}{2}} = \frac{1}{(q; q)_{∞}} (1 − ∑_{n=1}^{∞}(−1)^{n−1}q^{3\binom{n+1}{2}})

and this generates all partitions excluding those with rank ≤ −2, i.e., partitions with rank ≥ −1.

6 Proof of Theorem 4

Proof.

F_{2,1}(q) = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{n^{2}}

= \frac{1}{2(q; q)_{∞}} ( ∑_{n=−∞}^{∞}(−1)^{n}q^{n^{2}} + 1)

= \frac{1}{2(q; q)_{∞}} (\frac{(q; q)_{∞}}{(−q; q)_{∞}} + 1)

= \frac{1}{2} (\frac{1}{(−q; q)_{∞}} + \frac{1}{(q; q)_{∞}} )

= \frac{1}{2} (∑_{n=0}^{∞} \frac{(−1)^{n}q^{n}}{(q; q)_{n}} + ∑_{n=0}^{∞} \frac{q^{n}}{(q; q)_{n}} )

= ∑_{n=0}^{∞} \frac{q^{2n}}{(q; q)_{2n}}

= ∑_{n≥0} p_{e}(n)q^{n}.

7 Proof of Theorem 6

Proof. In the work of Blecksmith, Brillhart and Gerst [5, Theorem 1 (a)], we find

∏_{\begin{matrix}n=1 \\ n≢±4,±6,±8,±10 (mod 32) \end{matrix}}^{∞}(1 − q^{n}) = 1 + ∑_{n=1}^{∞}(−1)^{n} (q^{n^{2}} + q^{2n^{2}}) .  (16)

Let us now divide both sides of (16) by (q; q)_{∞}, and we find

∏_{\begin{matrix}n=1 \\ n≡±4,±6,±8,±10 (mod 32) \end{matrix}}^{∞} \frac{1}{1 − q^{n}} = F_{2,1}(q) + F_{4,2}(q) − \frac{1}{(q; q)_{∞}}  (17)
= F_{4,2}(q) − \overline{F_{2,1}}(q)  (by (7))
= F_{4,2}(q) − ∑_{n=0}^{∞} p_{o}(n)q^{n},  (by Theorem 4 and (7))

and this is equivalent to Theorem 6.

8 Proof of Theorem 7

Proof. Again, we turn to the paper of Blecksmith, Brillhart and Gerst, where we find [5, Theorem 3 (a)]

∏_{\begin{matrix}n=1 \\ n≢±2,±4,±5,±6,±7,±8 (mod 24) \end{matrix}}^{∞}(1 − q^{n}) = 1 + ∑_{n=1}^{∞}(−1)^{n} (q^{n^{2}} + q^{3n^{2}}) .  (18)

We now divide by (q; q)_{∞} to obtain

∏_{\begin{matrix}n=1 \\ n≡±2,±4,±6,±7,±8 (mod 24) \end{matrix}} \frac{1}{1 − q^{n}} = F_{2,1}(q) + F_{6,3}(q) − \frac{1}{(q; q)_{∞}}  (19)
= F_{6,3}(q) − \overline{F_{2,1}}(q)  (by (7))
= F_{6,3}(q) − ∑_{n=0}^{∞} p_{o}(n)q^{n},  (by Theorem 4 and (7))

and this is equivalent to Theorem 7.

9 Conclusion

We would suggest that this is the tip of the iceberg in the study of mex_{A,a}(π). It is our hope that there are many interesting results awaiting further inquiry.

Among the more obvious questions are these:

I. Are there bijective proofs of any of these theorems? II. Is there a theorem for p_{2,2}(n) comparable to Theorem 2 and 3?

To study p_{2,2}(n), we would need to know more about

F_{2,2}(q) = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{n^{2}+n}.

Utilizing the weak form of Bailey’s lemma [1, eqs. (3.27) and (3.33) with a = q, α_{r} = (−1)^{n}] we see that

F_{2,2}(q) = ∑_{n≥0} \frac{q^{n^{2}+n}B_{n}(q)}{(q; q)_{2n+1}},

where

B_{n}(q) = ∑_{r=0}^{n}(−1)^{r}\left[{2n + 1 \atop n − r}\right]

with the q-binomial coefficient given by

\left[{m \atop n}\right] = \frac{(q; q)_{m}}{(q; q)_{n}(q; q)_{m−n}} .

It appears that B_{n}(q)

(1) has nonnegative coefficients;

(2) is unimodal; and

(3) enumerates some subset of the partitions into at most n parts each ≤ n + 1. We are unable to prove any of these assertions.

III. Are there comparable theorems for other F_{A,a}(q)?

We would note that in terms of classical theta functions

F_{2k,k}(q) = \frac{1}{2(q; q)_{∞}} (θ_{4}(0, q^{k}) − 1).

Thus one can insert F_{2k,k}(q) into classical modular equations such as [10, p. 289, penultimate equation]

ψ(q^{2})θ_{4}(0, q^{5}) + qψ(q^{10})θ_{4}(0, q) = (−q; q)_{∞}(−q^{5}; −q^{5})_{∞};  (20)

where [2, p. 23, Eq. (2.2.13)]

ψ(q) = ∑_{n=0}^{∞} q^{n(n+1)/2} = \frac{(q^{2}; q^{2})_{∞}}{(q; q^{2})_{∞}} .

However, such complex identities do not appear to yield appealing partition identities comparable to any of Theorems 1 to 7.

IV. Are there other partition-theoretic objects that are related to instances of p_{A,a}(n)?

With regard to IV., we note that in [3, Sec. 5] it is proved that p_{1,1}(n) is also the number of concatenated spiral self-avoiding walks with an odd number of turns.

References

[1] George E. Andrews, q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra, Vol. 66 of CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1986.

[2] George E. Andrews, The Theory of Partitions, Cambridge Mathematical Library, Cambridge University Press, 1998.

[3] George E. Andrews, Concave compositions, Electron. J. Combin. 18 (2) (2011), Paper 6.

[4] George E. Andrews and F. G. Garvan, Dyson’s crank of a partition, Bull. Amer. Math. Soc. 18 (1988), 167–171.

[5] Richard Blecksmith, John Brillhart, and Irving Gerst, Parity results for certain partition functions and identities similar to theta function identities, Math. Comp. 48 (1987), 29– 38.

[6] F. J. Dyson, Some guesses in the theory of partitions, Eureka 8 (1944), 10–15.

[7] Aviezri S. Fraenkel and Udi Peled, Harnessing the unwieldy MEX function. In Games Of No Chance 4, Vol. 63 of Math. Sci. Res. Inst. Publ., pp. 77–94. Cambridge Univ. Press, 2015.

[8] Brian Hopkins and James A. Sellers, Exact enumeration of Garden of Eden partitions. In B. Landman, M. Nathanson, J. Nešetřil, R. Nowakowski and C. Pomerance, eds., Combinatorial Number Theory, pp. 299–303. De Gruyter, Berlin, 2007.

[9] M. Somos, contribution to sequence \underline{A064428}, in N. J. A. Sloane et al., On-Line Encyclopedia of Integer Sequences. Posted January 15 2018.

[10] Ali Kemal Uncu, Weighted Rogers-Ramanujan partitions and Dyson crank, Ramanujan J. 46 (2018), 579–591.

2010 Mathematics Subject Classification: Primary 11P81; Secondary 11A63, 05A19. Keywords: minimal excludant, mex function, theta function, partition.

(Concerned with sequences \underline{A027187}, \underline{A046682}, \underline{A064428}, and \underline{A260894}.) Received February 24 2019; revised versions received July 24 2019; October 26 2019; October 30 2019; February 16 2020. Published in Journal of Integer Sequences, February 17 2020. Return to Journal of Integer Sequences home page.