Combinatorial Extensions on Andrews and El Bachraoui’s Almost-Distinct Partitions

Brian Hopkins · 2025

Read Combinatorial Extensions on Andrews and El Bachraoui’s Almost-Distinct Partitions by Brian Hopkins (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17459.txt.

Introduction

Brian Hopkins gives counting proofs for a family of partition identities tied to recent work by Andrews and El Bachraoui, published in 2025. The partitions in question repeat only the smallest part a set number of times. All other parts must be distinct, or different from each other.

Andrews and El Bachraoui had found two surprising identities and asked for direct counting proofs. Hopkins supplies such proofs for an infinite family that includes those cases. He also treats the mirror setting, where only the largest part may be repeated. The work yields infinite families of inequalities for counts of partitions with distinct parts. It is aimed at readers in combinatorics who value proof by direct matching of sets.

Catalog record

CREATORBrian Hopkins
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-17459

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Combinatorial Extensions on Andrews and El Bachraoui’s Almost-Distinct Partitions Brian Hopkins Abstract . Andrews and El Bachraoui recently studied integer partitions where the smallest part is repeated a specified number of times and any other parts are distinct. Their results included two “surprising identities” for which they requested combinatorial proofs. We provide combinatorial proofs for an infinite family of related identities and also consider the analogous partitions where only the largest part can be repeated. The results give rise to infinite families of inequalities for the number of partitions with distinct parts. 1. Background Given an integer n>0 , we say \lambda=(\lambda_{1},\dots,\lambda_{t}) is a partition of n if each \lambda_{i} is a positive integer, \sum\lambda_{i}=n , and \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{t} . Write P(n) for the set of partitions of n . Requiring that the inequalities on the parts are strict, i.e., \lambda_{1}>\lambda_{2}>\cdots>\lambda_{t} , gives Q(n)\subset P(n) , the set of distinct part or strict partitions of n . Throughout, we use lowercase letters for set sizes, e.g., q(n)=|Q(n)| . In 2008, George Andrews initiated a rich subfield in integer partition theory focusing on the smallest parts of partitions [ 1 ] . In this vein, Andrews and Mohamed El Bachraoui recently considered partitions whose smallest part is repeated a specified number of times and any other parts are distinct [ 2 ] . Definition 1 . Given an integer k\geq 1 , let S_{k}(n)\subset P(n) be the partitions of n where the smallest part occurs exactly k times and any other parts are distinct. For example, S_{2}(8)=\{(6,1,1),(4,4),(4,2,2))\} . Note that the k=1 case means that all parts appear exactly once, so that S_{1}(n)=Q(n) . (Andrews and El Bachraoui use the notation \text{Spt}k_{d}(n) .) The primary motivation for the current work concerns the following results from their section “applications to partitions” [ 2 , §3] . Proposition 1 (Corollaries 5 and 6, Andrews and El Bachraoui) . For any integer n\geq 2 , (1) s_{2}(n)=2q(n-1)-q(n). For any integer n\geq 4 , (2) s_{3}(n)=2q(n-3)-2q(n-1)+q(n) and (3) 2q(n-1)-2q(n-3)\leq q(n)\leq 2q(n-1). Notice that the two inequalities of ( 3 ) follow from the quantities s_{3}(n) and s_{2}(n) being nonnegative in ( 2 ) and ( 1 ), respectively. Proposition 1 includes results for which Andrews and El Bachraoui requested combinatorial proofs. In the next section, we supply combinatorial proofs for ( 1 ) and a new result, Theorem 2 , from which identities analogous to ( 2 ) follow for every k , not just k=3 . The family of identities in Theorem 2 below also gives a sequence of inequalities expanding ( 3 ). In Section 3, we consider partitions where only the largest part can be repeated which will lead to another sequence of inequalities for q(n) . 2. Results for all s_{k}(n) We begin with a combinatorial proof of [ 2 , Cor. 5(a)] as requested by Andrews and El Bachraoui to complement their analytic approach. Combinatorial proof of ( 1 ). Let A(n)\subset S_{2}(n)\cup Q(n) be the partitions in the union with last part 1 and let B(n) be the complementary subset of S_{2}(n)\cup Q(n) with last part greater than one. We establish bijections A(n)\cong Q(n-1),\;B(n)\cong Q(n-1) from which the claim follows. For the first bijection, given (\lambda_{1},\ldots,\lambda_{t-1},1)\in A(n) , remove the final part 1. Whether the partition comes from S_{2}(n) (with \lambda_{t-1}=1 also) or from Q(n) (with \lambda_{t-1}>1 ), the image (\lambda_{1},\ldots,\lambda_{t-1})\in Q(n-1) . For the reverse direction, given (\mu_{1},\ldots,\mu_{s})\in Q(n-1) , append a part 1, making the image in A(n) (more specifically, the image is in S_{2}(n) if \mu_{s}=1 , otherwise the image is in Q(n) ). For the second bijection, given (\lambda_{1},\ldots,\lambda_{t-1},\lambda_{t})\in B(n) , replace the last part by \lambda_{t}-1 (which is positive). Whether the partition comes from S_{2}(n) (with \lambda_{t-1}=\lambda_{t} ) or from Q(n) (with \lambda_{t-1}>\lambda_{t} ), the image (\lambda_{1},\ldots,\lambda_{t-1},\lambda_{t}-1)\in Q(n-1) . For the reverse direction, given (\mu_{1},\ldots,\mu_{s-1},\mu_{s})\in Q(n-1) , increase the last part by one, making the image in B(n) (the image is in S_{2}(n) if \mu_{s-1}=\mu_{s}+1 , otherwise the image is in Q(n) ). Since A(n)\cap B(n)=\varnothing and A(n)\cup B(n)=S_{2}(n)\cup Q(n) , the bijections establish s_{2}(n)+q(n)=2q(n-1) , equivalent to ( 1 ). ∎ This proof also establishes that A(n) and B(n) are equinumerous subsets of S_{2}(n)\cup Q(n) , the partitions of n with smallest part occurring once or twice and any other parts distinct [ 3 , A087135] . See Table 1 for an example of the bijection. Table 1. The n=9 example of the bijections in our proof of ( 1 ). Short horizontal bars separate partitions in S_{2}(9) and Q(9) within A(9) and B(9) . A(9) Q(8) B(9) Q(8) (7,1,1) (7,1) (5,2,2) (5,2,1) (5,2,1,1) (5,2,1) (9) (8) (4,3,1,1) (4,3,1) (7,2) (7,1) (8,1) (8) (6,3) (6,2) (6,2,1) (6,2) (5,4) (5,3) (5,3,1) (5,3) (4,3,2) (4,3,1) Rather than give a combinatorial proof of ( 2 ), an identity involving s_{3}(n) , we establish the following general result. Theorem 2 . Given integers k\geq 2 and n\geq k , s_{k}(n)=-s_{k-1}(n)+s_{k-1}(n-k+1)+q(n-k+1). Proof. Let C(n)\subset S_{k}(n)\cup S_{k-1}(n) be the partitions in the union with last part 1 and let D(n) be the complementary subset of S_{k}(n)\cup S_{k-1}(n) with last part greater than one. We establish bijections C(n)\cong Q(n-k+1),\;D(n)\cong S_{k-1}(n-k+1) from which the claim follows. For the first bijection, given (\lambda_{1},\ldots,\lambda_{t-k},1,\ldots,1)\in C(n) (with k-1 parts 1 specified), remove the final k-1 parts 1. Whether the partition comes from S_{k}(n) (with \lambda_{t-k}=1 also) or from S_{k-1}(n) (with \lambda_{t-k}>1 ), the image (\lambda_{1},\ldots,\lambda_{t-k})\in Q(n-k+1) . For the reverse direction, given (\mu_{1},\ldots,\mu_{s})\in Q(n-k+1) , append k-1 parts 1, making the image (\mu_{1},\ldots,\mu_{s},1,\ldots,1)\in C(n) (more specifically, the image is in S_{k}(n) if \mu_{s}=1 , otherwise the image is in S_{k-1}(n) ). For the second bijection, given (\lambda_{1},\ldots,\lambda_{t-k},i,\ldots,i)\in D(n) (with k-1 smallest parts i>1 specified), decrease the final k-1 parts by one (note that i-1 is positive). Whether the partitions comes from S_{k}(n) (with \lambda_{t-k}=i also) or from S_{k-1}(n) (with \lambda_{t-k}>i ), the image (\lambda_{1},\ldots,\lambda_{t-k},i-1,\ldots,i-1)\in S_{k-1}(n-k+1) . For the reverse direction, given (\mu_{1},\ldots,\mu_{s-k},j,\ldots,j)\in S_{k-1}(n-k+1) (with exactly k-1 parts j ), increase the final k-1 parts by one, making the image (\mu_{1},\ldots,\mu_{s-k},j+1,\ldots,j+1)\in D(n) (more specifically, the image is in S_{k}(n) if \mu_{s-k}=j+1 , otherwise the image is in S_{k-1}(n) ). Since C(n)\cap D(n)=\varnothing and C(n)\cup D(n)=S_{k}(n)\cup S_{k-1}(n) , the bijections establish s_{k}(n)+s_{k-1}(n)=q(n-k+1)+s_{k-1}(n-k-1) , equivalent to the claim. ∎ See Table 2 for an example of the bijection. Table 2. The n=10 , k=3 example of the bijections used in the proof of Theorem 2 . Short horizontal bars separate partitions in S_{3}(10) and S_{2}(10) within C(10) and D(10) . C(10) Q(8) D(10) S_{2}(8) (7,1,1,1) (7,1) (4,2,2,2) (4,2,1,1) (5,2,1,1,1) (5,2,1) (6,2,2) (6,1,1) (4,3,1,1,1) (4,3,1) (4,3,3) (4,2,2) (8,1,1) (8) (6,2,1,1) (6,2) (5,3,1,1) (5,3) The k=2 case of Theorem 2 reduces to ( 1 ). Substituting that into the k=3 case for n\geq 4 gives \displaystyle s_{3}(n) \displaystyle=-s_{2}(n)+s_{2}(n-2)+q(n-2) \displaystyle=-(2q(n-1)-q(n))+(2q(n-3)-q(n-2))+q(n-2) \displaystyle=2q(n-3)-2q(n-1)+q(n) which is ( 2 ), i.e., we have an alternative proof of [ 2 , Cor. 5(b)] using our combinatorial proof of Theorem 2 . Continuing, the next two s_{k}(n) expressions written in terms of the q(n) sequence are (4) \displaystyle s_{4}(n) \displaystyle=2q(n-6)-2q(n-4)+2q(n-1)-q(n), \displaystyle s_{5}(n) \displaystyle=2q(n-10)-2q(n-8)+2q(n-6)-2q(n-5) \displaystyle\qquad{}+2q(n-4)-2q(n-1)+q(n). In the same way that the expressions for s_{2}(n) and s_{3}(n) give the two inequalities of ( 3 ), Theorem 2 gives an

Read the complete text