Generalizations of Stanley’s Theorem: Combinatorial Proofs and Related Inequalities

Abstract

We give combinatorial proofs for the generalizations of Stanley’s Theorem given in Andrews and Merca (Math Stud 89(1–2): 175–180, 2020). These involve the total number $b_k(n)$ of parts equal to k in all partitions of n. We also introduce several infinite families of linear inequalities involving $b_k(n)$.

1 Introduction

The work of this article started with a search for combinatorial proofs of the results in [4]. Before we discuss these results, we need to introduce some notation and terminology.

Given a non-negative integer n, a partition $\lambda$ of n is a non-increasing sequence of positive integers, $\lambda =(\lambda _1, \lambda _2, \ldots , \lambda _k)$, that add up to n, i.e., $\displaystyle \sum \nolimits _{i=1}^k\lambda _i=n$. Thus, if $\lambda =(\lambda _1, \lambda _2, \ldots , \lambda _k)$ is a partition, we have $\lambda _1\ge \lambda _2\ge \cdots \ge \lambda _k$. The numbers $\lambda _i$ are called the parts of $\lambda$ and n is the size of $\lambda$. The number of parts of the partition is called the length of $\lambda$ and is denoted by $\ell (\lambda )$. The number of times k appears as a part of $\lambda$ is the multiplicity of k in $\lambda$ and is denoted by $m_k(\lambda )$. We denote by ${\mathcal {P}}(n)$ the set of partitions of n and set $p(n)=|{\mathcal {P}}(n)|$.

Let n and k be non-negative integers such that $k>0$. We denote by $b_k(n)$ the number of parts equal to k in all the partitions of n. Thus,

$$\begin{aligned} b_k(n)=\sum _{\lambda \in {\mathcal {P}}(n)} m_k(\lambda ). \end{aligned}$$

We denote by dp(n) the number of parts that appear at least once in a given partition of n, counted without multiplicity, summed over all the partitions of n. We refer to dp(n) as the number of distinct parts in all partitions of n. We have,

$$\begin{aligned} dp(n)=\sum _{\lambda \in {\mathcal {P}}(n)} \sum _{\begin{array}{c} j\ge 1\\ m_j(\lambda )\ge 1 \end{array}} 1. \end{aligned}$$

Stanley’s theorem states that $b_1(n)=dp(n)$ for all positive integers n.

Elder’s generalization of Stanley’s theorem states that for all positive integers n and k,

$$\begin{aligned} b_k(n)=\sum _{\lambda \in {\mathcal {P}}(n)} \sum _{\begin{array}{c} j\ge 1\\ m_j(\lambda )\ge k \end{array}} 1. \end{aligned}$$

For more on Stanley’s and Elder’s theorems and their history, see [4].

Andrews and Merca [4] used generating functions to prove two generalizations of Stanley’s theorem. For non-negative integers k, n and r such that $0 \le r < k$, denote by $d_{r,k}(n)$ the number of distinct parts congruent to $-r \pmod k$ in all partitions of $n-r$.

Theorem 1

(Andrews-Merca 2020). Let k, n and r be non-negative integers such that $0 \le r < k$. Then,

$$\begin{aligned} b_k(n)=d_{r,k}(n). \end{aligned}$$

Theorem 2

(Andrews–Merca 2020). The sum of all parts equal to k in all partitions of n equals the difference between the sum of parts divisible by k, counted without multiplicity, in all the partitions of n and the sum of parts divisible by k, counted without multiplicity, in all the partitions of $n - k$.

In Sect. 2 we prove Theorems 1 and  2 combinatorially. In Sect. 3 we introduce several linear inequalities involving $b_k(n)$. Finally, since the inequalities presented in Sect. 3 are non-negativity results, in Sect. 4 we introduce combinatorial interpretations of the sums involved in these inequalities.

2 Combinatorial Proofs of Theorems 1 and  2

2.1 Combinatorial Proof of Theorem 1

Let n be a non-negative integer. Our goal is to prove that $b_k(n)=d_{r,k}(n)$ for all integers such that $0 \le r < k$. We first show combinatorially that $d_{r,k}(n)=d_{0,k}(n)$ for all $0\le r<k$. Then, we prove the theorem for $r=0$.

Lemma 3

Let k, n and r be non-negative integers such that $0 \le r < k$. Then,

$$\begin{aligned} d_{r,k}(n)=d_{0,k}(n). \end{aligned}$$

Proof

Denote by ${\mathcal {A}}_{r,k}(n)$ the set of overpartitions of $n-r$ with exactly one part overlined and the overlined part is congruent to $-r \pmod k$. Then ${\mathcal {A}}_{0,k}(n)$ denotes the set of overpartitions of n with exactly one part overlined and the overlined part is congruent to $0 \pmod k$. Clearly, $|{\mathcal {A}}_{r,k}(n)|=d_{r,k}(n)$ and $|{\mathcal {A}}_{0,k}(n)|=d_{0,k}(n)$

Adding r to the overlined part of an overpartition in ${\mathcal {A}}_{r,k}(n)$ (and keeping the new part overlined) gives an overpartition in ${\mathcal {A}}_{0,k}(n)$. Subtracting r from the overlined part of an overpartition in ${\mathcal {A}}_{0,k}(n)$ (and keeping the new part overlined) gives an overpartition in ${\mathcal {A}}_{r,k}(n)$. Thus the overpartitions in ${\mathcal {A}}_{r,k}(n)$ are in one-to-one correspondence with the overpartitions in ${\mathcal {A}}_{0,k}(n)$. $\square$

Next, we finish the proof of Theorem 1 by proving the following lemma.

Lemma 4

Let k, n be integers such that $n\ge 0$ and $k>0$. Then,

$$\begin{aligned} b_k(n)=d_{0,k}(n). \end{aligned}$$

Proof

In [5] it is proved combinatorially that

$$\begin{aligned} b_k(n)=\sum _{t \ge 1}p(n-kt). \end{aligned}$$

Since the argument is not difficult, we recall it here for the convenience of the reader.

We denote by ${\mathcal {P}}(n,k,t)$ the set of partitions $\lambda \in {\mathcal {P}}(n)$ such that $m_k(\lambda )\ge t$. Let $p(n,k,t)=|{\mathcal {P}}(n,k,t)|$. Removing t parts equal to k from a partition $\lambda \in {\mathcal {P}}(n,k,t)$ gives a partition of $n-kt$. Conversely, adding t parts equal to k to a partition of $n-kt$ gives a partition of n in ${\mathcal {P}}(n,k,t)$. Thus,

$$\begin{aligned} p(n,k,t)=p(n-kt). \end{aligned}$$

To determine $b_k(n)$ we count, in order, the first appearance of k in all partitions of n, then the second appearance of k in all partitions of n, and so on. The number of the $t^{\text{ th }}$ appearance of k in all partitions of n equals p(n, k, t). Thus,

$$\begin{aligned} b_k(n)=\sum _{t\ge 1}p(n,k,t)=\sum _{t\ge 1}p(n-kt).\end{aligned}$$

(1)

We create a one-to-one correspondence between ${\mathcal {A}}_{0,k}(n)$ and the disjoint union $\displaystyle \bigcup \nolimits _{t\ge 1}{\mathcal {P}}(n-kt)$ as follows. If $\lambda$ in an overpartition in ${\mathcal {A}}_{0,k}(n)$, the overlined part of $\lambda$ is a part equal to kt for some $t\ge 1$. Remove the overlined part to obtain a partition in ${\mathcal {P}}(n-kt)$. Conversely, if $t\ge 1$ and $\mu$ is a partition in ${\mathcal {P}}(n-kt)$, add a part equal to kt to $\mu$ and overline it to obtain an overpartition in ${\mathcal {A}}_{0.k}(n)$. Therefore,

$$\begin{aligned} d_{0,k}(n)=|{\mathcal {A}}_{0,k}(n)|=\sum _{t\ge 1}p(n-kt)=b_k(n). \end{aligned}$$

$\square$

Remark

Lemma 4 leads to the following refinement of Theorem 1. If k, n, t be integers such that $n\ge 0$ and $k,t>0$, then

$$\begin{aligned} b_k(n)=\sum _{r=0}^{(t-1)k}{\tilde{d}}_{r.k}(n), \end{aligned}$$

where ${\tilde{d}}_{r.k}(n)$ is the number of distinct parts congruent to $-rk \pmod {tk}$ in all partitions of n.

To see this, suppose mk is a part counted by $d_{0,k}(n)$. Then m can be written uniquely as $m=qt-r$ with $0\le r\le t-1$. Therefore, $mk\equiv -rk\pmod {tk}$ for a unique $r\in \{0, 1, \ldots , t-1\}$.

2.2 Combinatorial Proof of Theorem 2

To ease the explanation, we refer to the sum of parts divisible by k, counted without multiplicity, in all partitions of n as the sum of distinct parts divisible by k in ${\mathcal {P}}(n)$. Thus, we need to show that $kb_k(n)$ equals the difference between the sum of distinct parts divisible by k in ${\mathcal {P}}(n)$ and the sum of distinct parts divisible by k in ${\mathcal {P}}(n - k)$.

Each partition $\lambda \in {\mathcal {P}}(n)$ with $m_k(\lambda )=1$ contributes k to $kb_k(n)$. The total contribution of these partitions is $k(p(n,k,1)- p(n,k,2))$. Thus,

$$\begin{aligned} kb_k(n)=k(p(n,k,1)- p(n,k,2))+\sum _{\lambda \in {\mathcal {P}}(n,k,2)}k m_k(\lambda ). \end{aligned}$$

As in the proof of Lemma 4, there is a bijection between ${\mathcal {P}}(n,k,1)$ and ${\mathcal {P}}(n-k)$. It follows from the definition of this bijection (remove/add a part equal to k) that the difference between the sum of distinct parts divisible by k in ${\mathcal {P}}(n,k,1)$ and the sum of distinct parts divisible by k in ${\mathcal {P}}(n - k)$ equals k times the number of partitions $\lambda \in {\mathcal {P}}(n)$ with $m_k(\lambda )=1$, i.e., $k(p(n,k,1)- p(n,k,2))$. It remains to show that

$$\begin{aligned} \sum _{\lambda \in {\mathcal {P}}(n,k,2)} k m_k(\lambda ) \end{aligned}$$

equals the sum of distinct parts divisible by k in all partitions $\lambda$ in ${\mathcal {P}}(n)$ with $m_k(\lambda )=0$. Let ${\mathcal {A}}'_{0,k}(n)$ be the set of overpartitions in ${\mathcal {A}}_{0,k}(n)$ with no part equal to k. Then, the sum of overlined parts in all overpartitions in ${\mathcal {A}}'_{0,k}(n)$ equals the sum of distinct parts divisible by k in all partitions $\lambda$ in ${\mathcal {P}}(n)$ with $m_k(\lambda )=0$.

There is a one-to one correspondence $\phi : {\mathcal {A}}'_{0,k}(n) \rightarrow {\mathcal {P}}(n,k,2)$ defined as follows. Given an overpartition $\lambda \in {\mathcal {A}}'_{0,k}(n)$, let $\phi (\lambda )$ be the partition obtained from $\lambda$ by replacing the overlined part, kt, with t parts equal to k. The inverse, takes all parts equal to k in $\mu \in {\mathcal {P}}(n,k,2)$, merges them, and overlines the obtained part. Moreover, for each overpartition $\lambda \in {\mathcal {A}}'_{0,k}(n)$, the overlined part is equal to $km_k(\phi (\lambda ))$. Summing the overlined parts of all $\lambda \in {\mathcal {A}}'_{0,k}(n)$ completes the proof.

Remark

We note that the proof of Theorem 2 also follows from the fact that $kb_k(n)=k\sum _{t\ge 1} p(n-kt)$ and the sum of distinct parts divisible by k in ${\mathcal {P}}(n)$ equals $k\sum _{t\ge 1} tp(n-kt)$.

2.3 A Simple Proof of a Further Result of [4]

In [4], the authors use logarithmic differentiation of the two variable generating function for partitions to show that

$$\begin{aligned} \sum _{j=-\infty }^\infty (-1)^j S(n-j(3j-1)/2)=d(n), \end{aligned}$$

where S(n) denotes the total number of parts in all partitions of n and d(n) denotes the number of divisors of n. We offer an alternative proof.

Recall, from the proof of Lemma 4 that

$$\begin{aligned} b_k(n)=\sum _{t\ge 1} p(n-kt). \end{aligned}$$

Clearly

$$\begin{aligned} S(n)=\sum _{k\ge 1}b_k(n). \end{aligned}$$

Therefore,

$$\begin{aligned} \sum _{j=-\infty }^\infty (-1)^j S(n-j(3j-1)/2)&= \sum _{j=-\infty }^\infty (-1)^j \sum _{k\ge 1}\sum _{t\ge 1} p(n-kt- j(3j-1)/2) \\&=\sum _{k\ge 1}\sum _{t\ge 1}\sum _{j=-\infty }^\infty (-1)^j p(n-kt-j(3j-1)/2).\end{aligned}$$

From Euler’s Pentagonal Number Theorem, it follows that

$$\begin{aligned} \sum _{j=-\infty }^\infty (-1)^jp(n-j(3j-1)/2)={\left\{ \begin{array}{ll} 0 &{} \text{ if } n>0\\ 1 &{} \text{ if } n=0. \end{array}\right. } \end{aligned}$$

Thus,

$$\begin{aligned} \sum _{k\ge 1}\sum _{t\ge 1}\sum _{j=-\infty }^\infty (-1)^j p(n-kt-j(3j-1)/2)=\sum _{\begin{array}{c} k,t\ge 1\\ kt=n \end{array}}1=d(n). \end{aligned}$$

3 Linear Inequalities Involving $b_k(n)$

In this section, and throughout this paper, we use the following customary q-series notation:

$$\begin{aligned} (a;q)_n =&{\left\{ \begin{array}{ll} 1, &{} \text {for n=0,}\\ (1-a)(1-aq)\cdots (1-aq^{n-1}), &{}\text {for n>0;} \end{array}\right. }\\ (a;q)_\infty =&\lim _{n\rightarrow \infty } (a;q)_n. \end{aligned}$$

Because the infinite product $(a;q)_\infty$ diverges when $a\ne 0$ and $|q|\geqslant 1$, whenever $(a;q)_\infty$ appears in a formula, we shall assume $|q| <1$.

We denote by $p_{e-o}(n)$ the difference between the number of partitions of n into an even number of parts and the number of partitions of n into an odd number of parts. We have the following infinite families of inequalities.

Theorem 5

Let k, m and n be three positive integers. Then

$$\begin{aligned} (-1)^m \left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt) \right) \geqslant 0, \end{aligned}$$

with strict inequality if and only if $n \geqslant k+(m+1)^2$.

Proof

It is well-known that the generating function for $p_{e-o}(n)$ is given by

$$\begin{aligned} \sum _{n=0}^\infty p_{e-o}(n) q^n = \frac{1}{(-q;q)_\infty }= (q;q^2)_\infty . \end{aligned}$$

From [4], we have

$$\begin{aligned} \sum _{n=0}^\infty b_k(n) q^n= \frac{q^k}{(1-q^k)(q;q)_\infty }. \end{aligned}$$

Considering the Cauchy multiplication of two power series and the generating functions for $b_k(n)$ and $p_{e-o}(n)$, we obtain:

$$\begin{aligned}&\sum _{n=0}^\infty \left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt) \right) q^n\\&\quad = \left( \sum _{n=0}^\infty b_k(n) q^n \right) \left( 1+2\sum _{n=1}^m (-1)^n q^{n^2} \right) - \left( \sum _{n=1}^\infty q^{kn} \right) \left( \sum _{n=0}^\infty p_{e-o}(n) q^n \right) \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{n=1}^m (-1)^n q^{n^2} \right) - \frac{q^k}{1-q^k} \frac{1}{(-q;q)_\infty }\\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{n=1}^m (-1)^n q^{n^2} - \frac{(q;q)_\infty }{(-q;q)_\infty } \right) . \end{aligned}$$

To obtain our inequality, we consider the Gauss hypergeometric series

$$\begin{aligned} {_{2}}\phi _{1}\bigg (\begin{matrix}a, b\\ c\end{matrix}\,;q,z\bigg ) = \sum _{n=0}^{\infty } \frac{(a;q)_n(b;q)_n}{(q;q)_n(c;q)_n} z^n \end{aligned}$$

and the second Heine transformation formula for ${_{2}}\phi _{1}$ [6, (III.2)], namely

$$\begin{aligned} {_{2}}\phi _{1}\bigg (\begin{matrix}a, b\\ c\end{matrix}\,;q,z\bigg ) = \frac{(c/b;q)_\infty (bz;q)_\infty }{(c;q)_\infty (z;q)_\infty } {_{2}}\phi _{1}\bigg (\begin{matrix}abz/c, b\\ bz\end{matrix}\,;q,c/b\bigg ). \end{aligned}$$

(2)

In addition, using the classical theta identity of Gauss [1, p.23]

$$\begin{aligned} \frac{(q;q)_\infty }{(-q;q)_\infty } = 1+2\sum _{n=1}^\infty (-1)^n q^{n^2}, \end{aligned}$$

we can write

$$\begin{aligned}&\frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{j=1}^m (-1)^j q^{j^2} - \frac{(q;q)_\infty }{(-q;q)_\infty } \right) \\&\quad = -\frac{2q^k}{(1-q^k)(q;q)_\infty } \sum _{j=m+1}^\infty (-1)^j q^{j^2} \\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}}{(1-q^k)(q;q)_\infty } \sum _{j=0}^{\infty } (-1)^j q^{j^2+2j(m+1)}\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}}{(1-q^k)(q;q)_\infty } \lim _{\tau \rightarrow 0} \sum _{j=0}^\infty \frac{(q^{2m+3}/\tau ;q^2)_j}{(\tau ;q^2)_j}\tau ^j\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}}{(1-q^k)(q;q)_\infty } \lim _{\tau \rightarrow 0} {_{2}}\phi _{1}\bigg (\begin{matrix}q^{2}, q^{2m+3}/\tau \\ \tau \end{matrix}\,;q^{2},\tau \bigg )\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}}{(1-q^k)(q;q)_\infty }\times \\&\qquad \times \lim _{\tau \rightarrow 0} \frac{(\tau ^2/q^{2m+3};q^2)_\infty (q^{2m+3};q^2)_\infty }{(\tau ;q^2)^2_\infty } {_{2}}\phi _{1}\\&\qquad \times \bigg (\begin{matrix}q^{2m+5}/\tau , q^{2m+3}/\tau \\ q^{2m+3}\end{matrix}\,;q^{2},\tau ^2/q^{2m+3}\bigg )\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}(q^{2m+3};q^2)_\infty }{(1-q^k)(q;q)_\infty }\times \\&\qquad \times \lim _{\tau \rightarrow 0} \sum _{j=0}^\infty \frac{(q^{2m+5}/\tau ;q^2)_j(q^{2m+3}/\tau ;q^2)_j}{(q^2;q^2)_j(q^{2m+3};q^2)_j}\left( \frac{\tau ^2}{q^{2m+3}}\right) ^j\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}(q^{2m+3};q^2)_\infty }{(1-q^k)(q;q)_\infty } \lim _{\tau \rightarrow 0} \sum _{j=0}^\infty \frac{(-1)^j q^{j(j+1)}(q^{2m+3}/\tau ;q^2)_j}{(q^2;q^2)_j(q^{2m+3};q^2)_j}\tau ^j\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}(q^{2m+3};q^2)_\infty }{(1-q^k)(q;q)_\infty } \sum _{j=0}^\infty \frac{q^{j(2j+2m+3)}}{(q^2;q^2)_j(q^{2m+3};q^2)_j}\\&\quad = (-1)^m \frac{2q^{k+(m+1)^2}}{(1-q^k)(q^2;q^2)_\infty } \sum _{j=0}^\infty \frac{q^{j(2j+2m+3)}}{(q^2;q^2)_j(q;q^2)_{m+j+1}}. \end{aligned}$$

Now we see that the coefficients of $q^n$ in the series

$$\begin{aligned} (-1)^m \frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{j=1}^m (-1)^j q^{j^2} - \frac{(q;q)_\infty }{(-q;q)_\infty } \right) \end{aligned}$$

are all non-negative. Moreover, for $n\geqslant k+(m+1)^2$ the coefficients of $q^n$ are all positive. This concludes the proof. $\square$

The limiting case $m\rightarrow \infty$ of Theorem 5 reads as follows.

Corollary 6

Let k and n be two positive integers. Then

$$\begin{aligned} b_k(n) + 2\sum _{j=1}^\infty (-1)^j b_k(n-j^2) = \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt). \end{aligned}$$

In addition, we remark that

$$\begin{aligned} \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt) \equiv b_k(n) \pmod 2. \end{aligned}$$

Usually, the number of partitions of n into distinct parts is denoted by Q(n). For what follows, we denote by $Q_{odd}(n)$ the number of partitions of n into distinct odd parts. It is well-known that the generating functions for Q(n) and $Q_{odd}(n)$ are given by

$$\begin{aligned} \sum _{n=0}^\infty Q(n) q^n = (-q;q)_\infty \end{aligned}$$

and

$$\begin{aligned} \sum _{n=0}^\infty Q_{odd}(n) q^n = (-q;q^2)_\infty . \end{aligned}$$

We have the following infinite families of linear inequalities.

Theorem 7

Let k, m and n be three positive integers. Then

$$\begin{aligned} (-1)^m \left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-2j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } Q_{odd}(n-kt)\right) \geqslant 0, \end{aligned}$$

with strict inequality if and only if $n \geqslant k+2(m+1)^2$.

Proof

The proof of this theorem is quite similar to the proof of Theorem 5, i.e.,

$$\begin{aligned}&\sum _{n=0}^\infty \left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-2j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } Q_{odd}(n-kt) \right) q^n\\&\quad = \left( \sum _{n=0}^\infty b_k(n) q^n \right) \left( 1+2\sum _{n=1}^m (-1)^n q^{2n^2} \right) - \left( \sum _{n=1}^\infty q^{kn} \right) \left( \sum _{n=0}^\infty Q_{odd}(n) q^n \right) \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{n=1}^m (-1)^n q^{2n^2} \right) - \frac{q^k}{1-q^k} (-q;q^2)_\infty \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \left( 1+2\sum _{n=1}^m (-1)^n q^{2n^2} - \frac{(q^2;q^2)_\infty }{(-q^2;q^2)_\infty } \right) \\&\quad = -\frac{2q^k}{(1-q^k)(q;q)_\infty } \sum _{n=m+1}^\infty (-1)^n q^{2n^2}\\&\quad = (-1)^m \frac{2q^{k+2(m+1)^2}}{(1-q^k)(q;q)_\infty } \sum _{n=0}^\infty (-1)^{n} {(q^{2})}^{n^2+2n(m+1)}\\&\quad = (-1)^m \frac{2q^{k+2(m+1)^2}(q^{4m+6};q^4)_\infty }{(1-q^k)(q;q)_\infty } \sum _{n=0}^\infty \frac{q^{2n(2n+2m+3)}}{(q^4;q^4)_n(q^{4m+6};q^4)_n}\\&\quad = (-1)^m \frac{2q^{k+2(m+1)^2}(q^{2};q^4)_\infty }{(1-q^k)(q;q)_\infty } \sum _{n=0}^\infty \frac{q^{2n(2n+2m+3)}}{(q^4;q^4)_n(q^2;q^4)_{m+n+1}}. \end{aligned}$$

$\square$

The limiting case $m\rightarrow \infty$ of Theorem 7 reads as follows.

Corollary 8

Let k and n be two positive integers. Then

$$\begin{aligned} b_k(n) + 2\sum _{j=1}^\infty (-1)^j b_k(n-2j^2) = \sum _{t=1}^{\lfloor n/k \rfloor } Q_{odd}(n-kt). \end{aligned}$$

Next, we give an infinite family of linear inequalities involving $b_k(n)$ and Q(n).

Theorem 9

Let k, m and n be three positive integers. Then

$$\begin{aligned} (-1)^{m-1} \left( \sum _{j=0}^{2m-1} (-1)^{j(j+1)/2} b_k\big (n-j(j+1)/2\big ) - \sum _{t=1}^{\lfloor n/k \rfloor } Q\left( \frac{n-kt}{2}\right) \right) \geqslant 0, \end{aligned}$$

with strict inequality if and only if $n \geqslant k+m(2m+1)$.

Proof

Considering the following classical theta identities of Gauss [1, p.23]

$$\begin{aligned} \sum _{n=0}^\infty (-q)^{n(n+1)/2} = \frac{(q^2;q^2)_\infty }{(-q;q^2)_\infty }, \end{aligned}$$

we can write

$$\begin{aligned}&\sum _{n=0}^\infty \left( \sum _{j=0}^{2m-1} (-1)^{j(j+1)/2} b_k\big (n-j(j+1)/2\big ) - \sum _{t=1}^{\lfloor n/k \rfloor } Q\left( \frac{n-kt}{2} \right) \right) q^n \\&\quad = \left( \sum _{n=0}^\infty b_k(n) q^n \right) \left( \sum _{n=0}^{2m-1} (-q)^{n(n+1)/2} \right) - \left( \sum _{n=1}^\infty q^{kn} \right) \left( \sum _{n=0}^\infty Q(n) q^{2n} \right) \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \sum _{n=0}^{2m-1} (-q)^{n(n+1)/2} - \frac{q^k (-q^2;q^2)_\infty }{1-q^k} \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \left( \sum _{n=0}^{2m-1} (-q)^{n(n+1)/2} - \frac{(q^2;q^2)_\infty }{(-q;q^2)_\infty } \right) \\&\quad = (-1)^{m-1} \frac{q^k (-q^2;q^2)_\infty }{1-q^k} \frac{(-q;q^2)_m}{(q^2;q^2)_{m-1}} \sum _{n=0}^{\infty } \frac{q^{m(2n+2m+1)}(-q^{2n+2m+3};q^2)_{\infty }}{(q^{2n+2m+2};q^2)_{\infty }}, \end{aligned}$$

where we have invoked [3, Theorem 9]: for $m\geqslant 1$,

$$\begin{aligned}&\frac{(-q;q^2)_\infty }{(q^2;q^2)_\infty } \sum _{n=0}^{2m-1}(-q)^{n(n+1)/2} \\&\qquad = 1 - (-1)^m \frac{(-q;q^2)_m}{(q^2;q^2)_{m-1}} \sum _{n=0}^{\infty } \frac{q^{m(2n+2m+1)}(-q^{2n+2m+3};q^2)_{\infty }}{(q^{2n+2m+2};q^2)_{\infty }}. \end{aligned}$$

This concludes the proof. $\square$

The limiting case $m\rightarrow \infty$ of Theorem 9 reads as follows.

Corollary 10

Let k and n be two positive integers. Then

$$\begin{aligned} \sum _{j=0}^\infty (-1)^{j(j+1)/2} b_k\big (n-j(j+1)/2\big ) = \sum _{t=1}^{\lfloor n/k \rfloor } Q\left( \frac{n-kt}{2}\right) . \end{aligned}$$

Andrews and Garvan [2] introduced the crank of a partition as equal to the largest part of the partition if there are no ones as parts and otherwise equal to the number of parts larger than the number of ones minus the number of ones. We denote by C(n) the number of partition of n with non-negative crank. We have the following infinite family of inequalities.

Theorem 11

Let k, m and n be three positive integers. Then

$$\begin{aligned} (-1)^{m-1} \left( \sum _{j=0}^{m-1} (-1)^{j} b_k\big (n-j(j+1)/2\big ) - \sum _{t=1}^{\lfloor n/k \rfloor } C(n-kt)\right) \geqslant 0, \end{aligned}$$

with strict inequality if and only if $n \geqslant k+2(m+1)^2$.

Proof

Recently, Uncu [8] proved that the generating function for partitions with non-negative crank is given by

$$\begin{aligned} \sum _{n=0}^\infty C(n) q^n = \frac{1}{(q;q)_\infty } \sum _{n=0}^\infty (-1)^n q^{n(n+1)/2}. \end{aligned}$$

Thus we can write

$$\begin{aligned}&\sum _{n=0}^\infty \left( \sum _{j=0}^{m-1} (-1)^{j} b_k\big (n-j(j+1)/2\big ) - \sum _{t=1}^{\lfloor n/k \rfloor } C(n-kt)\right) q^n \\&\quad = \left( \sum _{n=0}^\infty b_k(n) q^n \right) \left( \sum _{n=0}^{m-1} (-1)^n q^{n(n+1)/2} \right) - \left( \sum _{n=1}^\infty q^{kn} \right) \left( \sum _{n=0}^\infty C(n) q^{n} \right) \\&\quad = \frac{q^k}{(1-q^k)(q;q)_\infty } \sum _{n=0}^{m-1} (-1)^{n} q^{n(n+1)/2} - \frac{q^k}{1-q^k} \sum _{n=0}^\infty C(n) q^{n} \\&\quad = \frac{q^k}{1-q^k} \left( \frac{1}{(q;q)_\infty } \sum _{n=0}^{m-1} (-1)^{n} q^{n(n+1)/2} - \sum _{n=0}^\infty C(n) q^{n} \right) \\&\quad = - \frac{q^k}{(1-q^k)(q;q)_\infty } \sum _{n=m}^\infty (-1)^{n} q^{n(n+1)/2}\\&\quad = (-1)^{m-1} \frac{q^{k+m(m+1)/2}}{(1-q^k)(q;q)_\infty } \sum _{n=0}^\infty (-1)^n q^{n(2m+1)/2+n^2/2}\\&\quad = (-1)^{m-1} \frac{q^{k+m(m+1)/2}}{(1-q^k)(q;q)_\infty } \lim _{z\rightarrow 0} \sum _{n=0}^\infty \frac{z^n(q^{m+1}/z;q)_n}{(z;q)_n}\\&\quad = (-1)^{m-1} \frac{q^{k+m(m+1)/2}}{(1-q^k)(q;q)_\infty } \\&\qquad \times \lim _{z\rightarrow 0} \frac{(z^2/q^{m+1};q)_\infty (q^{m+1};q)_\infty }{(z;q)^2_\infty }\\&\qquad \sum _{n=0}^\infty \frac{(q^{m+2}/z;q)_n(q^{m+1}/z;q)_n}{(q;q)_n(q^{m+1};q)_n}\left( \frac{z^2}{q^{m+1}} \right) ^n\\&\qquad \qquad ({\hbox {By Heine's transformation }(2)})\\&\quad = (-1)^{m-1} \frac{q^{k+m(m+1)/2} (q^{m+1};q)_\infty }{(1-q^k)(q;q)_\infty } \sum _{n=0}^\infty \frac{q^{n(n+m+1)}}{(q;q)_n(q^{m+1};q)_n}\\&\quad = (-1)^{m-1} \frac{q^{k+m(m+1)/2}}{1-q^k} \sum _{n=0}^\infty \frac{q^{n(n+m+1)}}{(q;q)_n(q;q)_{n+m}}. \end{aligned}$$

This concludes the proof. $\square$

The limiting case $m\rightarrow \infty$ of Theorem 11 reads as follows.

Corollary 12

Let k and n be two positive integers. Then

$$\begin{aligned} \sum _{j=0}^\infty (-1)^{j} b_k\big (n-j(j+1)/2\big ) = \sum _{t=1}^{\lfloor n/k \rfloor } C\left( n-kt\right) . \end{aligned}$$

4 Combinatorial Interpretations of the Linear Inequalities

This section makes use of the results of Sect. 3 of [7]. First we introduce some notation following [7].

Definition 1

Given a partition $\lambda$, the m-Durfee rectangle of $\lambda$ is the largest rectangle whose width minus height equals m that fits in the Ferrers diagram of $\lambda$.

Definition 2

Let $\lambda =(\lambda _1, \lambda _2, \ldots , \lambda _{\ell (\lambda )})$ be a partition. Each part $\lambda _i$ of $\lambda$ can be written uniquely as $\lambda _i=2\mu _i+s_i$, where $s_i\in \{1,2\}$. The 2-modular Ferrers diagram of the partition $\lambda$ is a Ferrers digram whose i-th row consists of $\mu _i$ boxes labeled 2 and one box labeled $s_i$.

Let ${\mathcal {M}}_{o,m}(n)$ be the set of partitions of n into odd parts such that parts $2t+1$, $0\le t\le m$, occur (at least once) and parts below the $(m+2)$-Durfee rectangle in the 2-modular Ferrers diagram are strictly less than the width of the rectangle. Denote by $M_{o,m}(n)$ the cardinality of ${\mathcal {M}}_{o,m}(n)$. In [7], the authors prove that

$$\begin{aligned} \sum _{n=0}^\infty M_{o,m}(n)q^n= q^{(m+1)^2}\sum _{j=0}^\infty \frac{q^{j(2j+2m+3)}}{(q^2;q^2)_j(q;q^2)_{m+j+1}}. \end{aligned}$$

From the proof of Theorem 5, we have

$$\begin{aligned}&(-1)^m \sum _{n=0}^\infty \left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt) \right) q^n\\&\quad = 2 \frac{q^{k}}{(1-q^k)(q^2;q^2)_\infty } q^{(m+1)^2}\sum _{j=0}^\infty \frac{q^{j(2j+2m+3)}}{(q^2;q^2)_j(q;q^2)_{m+j+1}} \end{aligned}$$

Let ${\mathcal {N}}_{m,k}(n)$ be the set of pairs of partitions $(\mu ,\lambda )$ with $|\mu |+|\lambda |=n$ and such that $\mu$ is a partition in which k appears at least once and all parts not equal to k (if any) are even and $\lambda \in {\mathcal {M}}_{o,m}(n-|\mu |)$. Let $N_{m.k}(n)=|{\mathcal {N}}_{m,k}(n)|$. We then have the following combinatorial version of Theorem 5.

Theorem 13

Let k, m, and n be positive integers. Then,

$$\begin{aligned} (-1)^m\left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } p_{e-o}(n-kt)\right) =2N_{m,k}(n). \end{aligned}$$

To obtain a combinatorial version of Theorem 7, let ${\mathcal {M}}_{e,o,m}(n)$ be the set of partitions $\lambda$ of n into even parts such that the partition whose parts are half the parts of $\lambda$ is in ${\mathcal {M}}_{o,m}\left( \frac{n}{2}\right)$. Let $M_{e,o,m}(n)=|{\mathcal {M}}_{e,o,m}(n)|$. Then,

$$\begin{aligned} \sum _{n=0}^\infty M_{e,o,m}(n)q^n=q^{2(m+1)^2}\sum _{n=0}^\infty \frac{q^{2n(2n+2m+3)}}{(q^4;q^4)_n(q^2;q^4)_{m+n+1}}. \end{aligned}$$

Let ${\mathcal {T}}_{m,k}(n)$ be the set of pairs of partitions $(\mu ,\lambda )$ with $|\mu |+|\lambda |=n$ and such that $\mu$ is a partition in which k appears at least once and all parts not equal to k (if any) are $\not \equiv 2\pmod 4$ and $\lambda \in {\mathcal {M}}_{e,o,m}(n-|\mu |)$. Let $T_{m.k}(n)=|{\mathcal {T}}_{m,k}(n)|$. We then have the following combinatorial version of Theorem 7.

Theorem 14

Let k, m, and n be positive integers. Then,

$$\begin{aligned} (-1)^m\left( b_k(n) + 2\sum _{j=1}^m (-1)^j b_k(n-2j^2) - \sum _{t=1}^{\lfloor n/k \rfloor } Q_{odd}(n-kt)\right) =2T_{m,k}(n). \end{aligned}$$

From the proof of Theorem 9, it is clear that a combinatorial version would be very cumbersome and we omit it here.

To obtain a combinatorial version of Theorem 11, let ${\mathcal {M}}_m(n)$ be the set of partitions of n such that parts $1\le t\le m$ occur (at least once) and parts below the $(m+1)$-Durfee rectangle of $\lambda$ are strictly less than the width of the rectangle. Let $M_{m}(n)=|{\mathcal {M}}_{m}(n)|$. As in [7], we have

$$\begin{aligned} \sum _{n=0}^\infty M_{m}(n)q^n= q^{m(m+1)/2}\sum _{n=0}^\infty \frac{q^{n(n+m+1)}}{(q;q)_n(q;q)_{n+m}}. \end{aligned}$$

Let ${\mathcal {U}}_{m,k}(n)$ be the set of pairs of partitions $(\mu ,\lambda )$ with $|\mu |+|\lambda |=n$ and such that $\mu$ is a nonempty rectangular partition with all parts equal to k and $\lambda \in {\mathcal {M}}_{m}(n-|\mu |)$. Let $U_{m,k}(n)=|{\mathcal {U}}_{m,k}(n)|$. We then have the following combinatorial version of Theorem 11.

Theorem 15

Let k, m, and n be positive integers. Then,

$$\begin{aligned} (-1)^{m-1} \left( \sum _{j=0}^{m-1} (-1)^{j} b_k\big (n-j(j+1)/2\big ) - \sum _{t=1}^{\lfloor n/k \rfloor } C(n-kt)\right) =U_{m,k}(n), \end{aligned}$$

5 Concluding Remarks

We presented combinatorial proofs of the generalizations of Stanley’s theorem given in [4] as well as linear inequalities involving $b_k(n)$ and their combinatorial meaning. It would be very nice to find combinatorial proofs of the corollaries in Sect. 3. Since $b_k(n)=\sum _{t\ge 1}p(n-kt)$ is explained combinatorially, it suffices to prove combinatorially the identities in terms of numbers of partitions.

Let k and n be two positive integers. Proving combinatorially that

$$\begin{aligned} \sum _{j=-\infty }^\infty (-1)^j p(n-j^2) =p_{e-o}(n) \end{aligned}$$

would give a combinatorial proof of Corollary 6. Proving combinatorially that

$$\begin{aligned} \sum _{j=-\infty }^\infty (-1)^j p(n-2j^2) = Q_{odd}(n) \end{aligned}$$

would give a combinatorial proof of Corollary 8. Proving combinatorially that

$$\begin{aligned} \sum _{j=0}^\infty (-1)^{j(j+1)/2} p\big (n-j(j+1)/2\big ) = Q\left( \frac{n}{2}\right) \end{aligned}$$

would give a combinatorial proof of Corollary 10. Finally, proving combinatorially that

$$\begin{aligned} \sum _{j=0}^\infty (-1)^{j} p\big (n-j(j+1)/2\big ) = C\left( n\right) \end{aligned}$$

would give a combinatorial proof of Corollary 12.

The above identities have fairly straight forward proofs in terms of generating functions. However, their combinatorial proofs remain elusive.