Counting pattern-avoiding integer partitions

Jonathan Bloom; Nathan McNew

Counting pattern-avoiding integer partitions

T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Avoiding a fixed pattern makes partition counts grow by a power of n times a power of log n.

desk verdict A complete, well-proven solution of the pattern-avoiding partition counting problem, with genuinely new operator methods and only minor presentational blemishes. read the letter →

arxiv 1908.03953 v2 pith:BDAEAR56 submitted 2019-08-11 math.CO math.NT

Jonathan Bloom , Nathan McNew This is my paper · ORCID

classification math.COmath.NT MSC 05A1705A1505A16

keywords integerpartitionspatternavoidanceFerrersboardsgeneratingfunctionsasymptoticenumerationrookequivalenceWilfmetacyclicp-groups

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper counts how many partitions of an integer $n$ avoid a fixed partition pattern $\mu$, where containment means the Ferrers board of $\mu$ can be obtained by deleting rows and columns. It proves that for every super-strict pattern $\mu$, the generating function for the avoidance counts is rational, and gives an explicit recursive algorithm for computing it. It then derives asymptotic formulas showing that staircase patterns grow like divisor sums times powers of $\log n$, while every other strict pattern grows as $n^{k-1}(\log n)^{\ell}$ with an explicit constant. These asymptotics imply that whenever the two largest parts of $\mu$ are consecutive integers, the generating function is not algebraic. The results rest on the Wilf-equivalence reduction to strict partitions, which lets every pattern be replaced by a strict one without changing counts.

What carries the argument

The main combinatorial device is a pair of operators $E$ and $N$ attached to the southeast border of a super-strict partition $\mu$. Reading the border from bottom-left to top-right, each east step becomes $E$ and each north-east step becomes $N$, yielding a word $\Theta_\mu$; applying these operators to the bivariate generating function $\frac{zt}{1-zt}$ and setting $t=1$ produces $F_\mu(z,1)$, the generating function for avoiding $\mu$. The operator $E$ adds a column to the current rightmost column, while $N$ appends a new strictly shorter column together with an arbitrary number of width-equal columns, and the proof shows that the composition inherits rationality because super-strictness forbids consecutive $N$'s. For asymptotics, the paper uses the rectangular decomposition of a partition into $x_i y_i$ blocks with strictly decreasing heights; patterns with exactly $\mu_1-1$ distinct magnitudes form the dominant set $D(\mu)$, and a map $\Psi_m$ builds partitions avoiding $\mu$ from partitions avoiding a smaller pattern $\hat{\mu}$, giving the recursive constant in Theorem 4.16.

What would settle it

For $\mu = (4,3)$, the theorem predicts $|\mathrm{Av}_n(\mu)| = \frac{n^2 \log n}{4} + O(n^2)$; computing $|\mathrm{Av}_n(4,3)|$ exactly for $n$ up to, say, $10^5$ and checking whether $4 |\mathrm{Av}_n(4,3)| / (n^2 \log n)$ tends to $1$ would settle the asymptotic formula, and a persistent deviation would refute it.

Watch

Extended reading notes

Core claim

For a strict partition $\mu$, the paper establishes a dichotomy in the growth of $|\mathrm{Av}_n(\mu)|$. If $\mu$ is a staircase $(k+1, k, \ldots, 1)$, the count is asymptotic to a divisor-sum expression: for $k \geq 3$, $|\mathrm{Av}_n(\mu)| \sim \sigma_{k-1}(n)(\log n)^k / (k!(k-1)!\zeta(k))$, with separate formulas for $k = 1$ and $k = 2$. If $\mu$ is strict but not a staircase, written as $(k+1, k, k-1, \ldots, k-\ell+1, a_0, a_1, \ldots)$ with $k-\ell > a_0$, then $|\mathrm{Av}_n(\mu)| = \frac{n^{k-1}(\log n)^{\ell}}{\ell!(k-1)! \prod_{j=0}^{k-\ell-1}(k-\ell-a_j-j)}\left(1+O\left(\frac{1}{\log n}\right)\right)$. The paper also proves that $F_\mu(z,1)$ is rational whenever $\mu$ is super-strict, and that the generating function is not algebraic whenever $\mu_1 - \mu_2 = 1$ with $\mu_2 > 0$.

Load-bearing premise

Every statement for arbitrary partitions rests on the published theorem that each partition is Wilf-equivalent to a unique strict partition, so avoiding any pattern $\tau$ has exactly the same counts as avoiding its strict representative.

Editorial extensions

If this is right

For every super-strict partition $\mu$, the sequence $|\mathrm{Av}_n(\mu)|$ has a rational generating function and therefore satisfies a linear recurrence with constant coefficients.
For every fixed $K$, partitions in which any two part sizes differ by at most $K$ have a rational generating function.
For a strict non-staircase $\mu$, the growth order of $|\mathrm{Av}_n(\mu)|$ is determined by two parameters: $n^{k-1}$ times $(\log n)^{\ell}$, where $\ell$ counts how many consecutive part sizes directly below the largest are present in $\mu$.
If the two largest parts of $\mu$ are consecutive positive integers, the avoidance generating function cannot be algebraic, so no finite polynomial or rational closed form exists for that count.
Staircase patterns form a genuine exceptional family, with counts controlled by averaged divisor functions rather than by the power-of-$n$ formula.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The constant in Theorem 4.16 is built from the Foata-Schützenberger numbers $i + \mu_i$ appearing in rook-equivalence classification; this hints that the full asymptotic could be expressed as a Wilf-invariant quantity determined solely by the strict representative of $\mu$.
If Conjecture 1.2 is true, the boundary between algebraic and non-algebraic avoidance generating functions is exactly the super-strict condition; a testable next step is to search the algorithm's outputs for any non-super-strict pattern whose generating function is algebraic.
The coincidence that $F_{(5,2)}(z,1)$ equals the generating function for metacyclic $p$-groups suggests there may be a bijection between partitions avoiding $(5,2)$ and such groups, though the paper does not supply one.
The constructive $E/N$ algorithm could be run for arbitrary super-strict patterns to generate many new integer sequences, making it possible to test the conjecture computationally and to detect further coincidences with existing sequences.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Worth reading: this is the complete solution of the counting problem for pattern-avoiding integer partitions, and the operator calculus is genuinely new. Prior work only covered the two extremes—partitions into at most k parts and staircase avoidance—and this paper fills the whole spectrum with uniform asymptotics. The three headline results are all proven: rationality of the generating function for super-strict patterns, the full asymptotic formula for every strict pattern, and the non-algebraicity corollary for patterns whose first two parts differ by 1. The constructive algorithm and the table of small cases are practical payoffs, not afterthoughts.

The E/N operator method is the real novelty, and the proof of Theorem 3.18 is careful: the nice/very nice lemmas are simple but effective, and the induction in Theorem 3.7 is clean. On the asymptotic side, the paper does not hand-wave. The error terms are explicit, the k=2 log log n wrinkle is handled honestly, and the use of Ingham, Estermann, and Halberstam is transparent and appropriate. I also appreciate that the reduction to strict partitions is outsourced explicitly to Bloom–Saracino Theorem 1.1; that is a published tool, not a circular dependency.

Soft spots are minor. The non-algebraicity proof via Fatou's theorem is sound, though the multiple-roots-of-unity case deserves the two sentences it gets; they are sufficient. There are small notational hiccups in Lemma 4.15, especially the index shift between µ(i) and µ(i+1) in Case 2, but the counting argument remains legible and the conclusion follows. The metacyclic p-group coincidence is a curiosity, and the paper is honest that no bijective explanation is known. None of these rise to the level of a substantive flaw.

I agree with the reader's high confidence. This paper will likely be the standard reference for pattern-avoiding partitions. I would send it to a serious referee for a good combinatorics journal; I expect minor revision at most.

Referee Report

0 major / 6 minor

Summary. The paper studies pattern-avoiding integer partitions, where a partition α contains a pattern µ if the Ferrers board of µ can be obtained from α by deleting rows and columns. Using the Bloom–Saracino theorem that every partition is Wilf-equivalent to a unique strict partition, the authors reduce to strict patterns. They introduce two operators E and N on bivariate generating functions and prove (Theorem 3.18) that the avoidance generating function is rational whenever µ is super-strict, with a constructive algorithm for computing it. For asymptotics, they prove Theorem 4.8 for staircase patterns and Theorems 4.14 and 4.16 for general strict non-staircase patterns, giving explicit polynomial–logarithmic asymptotics whose constants are products of divisor sums and zeta values. Corollary 4.17 then uses Fatou's theorem to show that the generating function is not algebraic when µ1 − µ2 = 1 and µ2 > 0. The paper closes with a table of small cases, a conjecture on non-algebraicity for all non-super-strict µ, and a remark connecting the generating function for (5,2) to metacyclic p-groups.

Significance. If the results hold, the paper gives a clean structural dichotomy: rational generating functions for super-strict patterns and non-algebraicity for patterns whose first two parts differ by 1, with fully explicit parameter-free asymptotic formulas in between. The operator calculus is original and constructive, and the asymptotic theorems are sharp enough to imply non-algebraicity. The proofs are detailed and carefully articulated, with dependencies on published results (Ingham, Estermann, Bloom–Saracino) clearly cited; there are no fitted parameters and no circularity in the derivations. I verified the central chain of reasoning: the rationality theorem follows from the nice/very nice lemmas, and the asymptotic theorems follow by induction with explicit error terms. The table of small cases contains several entries that contradict the theorems, but these appear to be local presentation errors rather than flaws in the central arguments.

minor comments (6)

[Table 1] The rows for (4,3,1), (4,3,2), and (4,3,2,1) contradict the theorems in the text. Applying Theorem 4.16 to (4,3,1) with k=3, ℓ=1, a0=1 gives |Av_n| = n^2 log n / 2 + O(n^2), not n^3 log n / 2. Applying it to (4,3,2) with k=3, ℓ=2, a0=0 gives n^2 log^2 n / 4 + O(n^2 log n), not n^3 log^2 n / 4. Applying Theorem 4.8 to the staircase (4,3,2,1) with k=3 gives σ2(n) log^3 n / (12ζ(3)), not σ2(n) log^3 n / (6ζ(3)). Please correct the table, or reconcile the theorems if the table was computed independently.
[§4.2.1, Lemma 4.13 proof] In the sentence 'there can be at most k partitions α ∈ ⋃_{m=1}^n D_{n−m}(µ) with Ψ_{n−|α|}(α) = β', the set should be D_{n−m}(ˆµ), since α is an element of D(ˆµ). The same typo appears in the proof of Lemma 4.15, Case 2, where 'α ∈ D(µ)' should read 'α ∈ D(ˆµ)'.
[§3, Lemma 3.10] The lemma is stated for an arbitrary partition µ, but its proof invokes Lemma 3.21(iii), which requires µ to be strict. Please restrict the statement to strict µ, or at least note that this is the only case used in the paper.
[§4.2.2, Lemma 4.15, Case 3] The displayed rectangular decomposition of β omits the thin rectangle y_{k−ℓ}, even though the surrounding text immediately uses r ∈ {y_{a0+1}, ..., y_{k−ℓ}}. Please include the missing term for clarity.
[§4.3, Corollary 4.17] In the comparison after equation (33), the text writes the dominant term as ≍_m n^{k−1} log n, but the cited theorems give log^ℓ n with ℓ > 0; for ℓ > 1 this should be log^ℓ n. This does not affect the argument, but the notation should be corrected.
[Throughout] There are minor typos and notation issues: 'Riordon' should be 'Riordan' in Section 2, and in Theorem 4.16 the expression O(n^{k−1} log^{ℓ−1} n) for ℓ = 0 should be understood as O(n^{k−1}/log n). Please consider a brief note on this convention.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the paper's reduction to strict partitions uses a prior published Wilf-equivalence theorem as a tool, and the generating-function and asymptotic derivations are self-contained inductions over externally cited estimates.

full rationale

The central claims—rational generating functions for super-strict patterns (Theorem 3.18), the staircase asymptotics (Theorem 4.8), and the general strict-partition asymptotics (Theorem 4.16)—are proved by induction over the pattern's Ferrers geometry and by summing divisor-function estimates from Ingham, Estermann, Hardy–Wright, and Stanley. No parameter is fitted to data; all constants in the leading terms are divisor sums or zeta values inherited from the cited external estimates. The only load-bearing self-citation is Theorem 1.1, the Bloom–Saracino result that every partition is Wilf-equivalent to a unique strict partition, which is used to justify restricting attention to strict μ; that is a previously published, externally checkable theorem used as a reduction tool, not a restatement of the present results, so it does not make the derivation circular. Likewise, the observation that F_(5,2) equals Liedahl's metacyclic p-group generating function (Remark 3.20) is an explicit concurrence with an external enumeration, not an input to the proof. The asymptotic formulas in Theorems 4.8, 4.14, and 4.16 are derived from independent counting bijections (Lemmas 4.5, 4.13, 4.15) and from the external estimates for ν_k(n); the error terms are bounded by larger expressions, not by the target formulas. I therefore find no step in which a prediction reduces by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted; all constants are known arithmetic quantities. The axioms are standard background theorems or cited prior results. No new entities are posited.

assumptions (6)

domain assumption Theorem 1.1 (Bloom-Saracino): every partition τ is Wilf-equivalent to a unique strict partition µ, so |Av_n(τ)|=|Av_n(µ)| for all n.
Invoked in the introduction to reduce the whole problem to strict partitions; the paper cites [2,3] and does not reprove it.
domain assumption Ingham/Estermann/Andrews estimates for ν_k(n), the number of representations of n as a sum of k products (Eqs. 15-18).
Used in Theorem 4.8 to handle staircase patterns; these are external analytic results.
standard math Divisor-sum average estimates (9)-(13), including Huxley's θ=131/416, from Hardy-Wright and Huxley.
Used throughout Section 4 to sum asymptotics and to control error terms.
standard math Fatou's theorem: an algebraic power series with integer coefficients and radius 1 is rational, and rational ones have poles at roots of unity.
Used in Corollary 4.17 to infer non-algebraicity from non-rationality.
domain assumption Nathanson/Sylvester asymptotic for partitions into at most k parts: |Av_n((k+1))| = n^(k-1)/(k!(k-1)!)+O(n^(k-2)).
Base case for the induction in Theorem 4.14.
standard math Halberstam's bound ∑_m σ_a(n-m)σ_b(m) ≪ σ_{a+b+1}(n) for a,b>0.
Used in Theorem 4.8 to bound representations with repeated heights.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Counting pattern-avoiding integer partitions." pith.science (2026). https://pith.science/paper/BDAEAR56

@misc{pith2026190803953,
  author       = {Pith},
  title        = {Pith review of: Counting pattern-avoiding integer partitions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BDAEAR56}},
  note         = {Machine review of arXiv:1908.03953}
}

abstract

A partition $\alpha$ is said to contain another partition (or pattern) $\mu$ if the Ferrers board for $\mu$ is attainable from $\alpha$ under removal of rows and columns. We say $\alpha$ avoids $\mu$ if it does not contain $\mu$. In this paper we count the number of partitions of $n$ avoiding a fixed pattern $\mu$, in terms of generating functions and their asymptotic growth rates. We find that the generating function for this count is rational whenever $\mu$ is (rook equivalent to) a partition in which any two part sizes differ by at least two. In doing so, we find a surprising connection to metacyclic $p$-groups. We further obtain asymptotics for the number of partitions of $n$ avoiding a pattern $\mu$. Using these asymptotics we conclude that the generating function for $\mu$ is not algebraic whenever $\mu$ is rook equivalent to a partition with distinct parts whose first two parts are positive and differ by 1.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Andrews, Stacked lattice boxes , Ann

G. Andrews, Stacked lattice boxes , Ann. Comb. 3 (1999), no. 2-4, 115–130. MR1772341

work page 1999
[2]

Bloom and D

J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions , European J. Combin. 71 (2018), 246–267. MR3802248

work page 2018
[3]

, On criteria for rook equivalence of Ferrers boards , European J. Combin. 76 (2019), 199–207. MR3886523

work page 2019
[4]

Estermann, On the representations of a number as the sum of two products , J

T. Estermann, On the representations of a number as the sum of two products , J. London Math. Soc. 5 (1930), no. 2, 131–137. MR1574218

work page 1930
[5]

London Math

, On the representations of a number as the sum of three or more p roducts, Proc. London Math. Soc. (2) 34 (1932), no. 3, 190–195. MR1576145

work page 1932
[6]

Fatou, S´ eries trigonom´ etriques et s´ eries de Taylor, Acta Math

P. Fatou, S´ eries trigonom´ etriques et s´ eries de Taylor, Acta Math. 30 (1906), no. 1, 335–400. MR1555035

work page 1906
[7]

Foata and M

D. Foata and M. P. Sch¨ utzenberger, On the rook polynomials of Ferrers relations , Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ ured, 1969), 1970 , pp. 413–436. MR0360288 27

work page 1969
[8]

Goldman, J

J. Goldman, J. Joichi, and D. White, Rook theory. I. Rook equivalence of Ferrers boards , Proc. Amer. Math. Soc. 52 (1975), 485–492. MR429578

work page 1975

Show all 19 references

[9]

Halberstam, An asymptotic formula in the theory of numbers , Trans

H. Halberstam, An asymptotic formula in the theory of numbers , Trans. Amer. Math. Soc. 84 (1957), 338–351. MR0084519

1957
[10]

G. H. Hardy and E. M. Wright, An introduction to the theory of numbers , Sixth, Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silve rman, With a foreword by Andrew Wiles. MR2445243

2008
[11]

M. N. Huxley, Exponential sums and lattice points. III , Proc. London Math. Soc. (3) 87 (2003), no. 3, 591–609. MR2005876

2003
[12]

A. E. Ingham, Some asymptotic formulae in the theory of numbers , J. London Math. Soc. 2 (1927), no. 3, 202–208. MR1574426

1927
[13]

S. M. Johnson, On the representations of an integer as the sum of products of integers, Trans. Amer. Math. Soc. 76 (1954), 177–189. MR0060532

1954
[14]

Kaplansky and J

I. Kaplansky and J. Riordan, The problem of the rooks and its applications , Duke Math. J. 13 (1946), 259–268. MR16082

1946
[15]

Liedahl, Enumeration of metacyclic p-groups, J

S. Liedahl, Enumeration of metacyclic p-groups, J. Algebra 186 (1996), no. 2, 436–446. MR1423270

1996
[16]

P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc. (2) 19 (1920), no. 1, 75–113. MR1576612

1920
[17]

Nathanson, Partitions with parts in a ﬁnite set , Proc

M. Nathanson, Partitions with parts in a ﬁnite set , Proc. Amer. Math. Soc. 128 (2000), no. 5, 1269–

2000
[18]

J. L. Ram ´ ırez Alfons ´ ın,The Diophantine Frobenius problem , Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005. M R2260521

2005
[19]

Stanley, Enumerative combinatorics

R. Stanley, Enumerative combinatorics. Volume 1 , Second, Cambridge Studies in Advanced Mathemat- ics, vol. 49, Cambridge University Press, Cambridge, 2012. MR2868 112 28

2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Andrews, Stacked lattice boxes , Ann

G. Andrews, Stacked lattice boxes , Ann. Comb. 3 (1999), no. 2-4, 115–130. MR1772341

work page 1999

[2] [2]

Bloom and D

J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions , European J. Combin. 71 (2018), 246–267. MR3802248

work page 2018

[3] [3]

, On criteria for rook equivalence of Ferrers boards , European J. Combin. 76 (2019), 199–207. MR3886523

work page 2019

[4] [4]

Estermann, On the representations of a number as the sum of two products , J

T. Estermann, On the representations of a number as the sum of two products , J. London Math. Soc. 5 (1930), no. 2, 131–137. MR1574218

work page 1930

[5] [5]

London Math

, On the representations of a number as the sum of three or more p roducts, Proc. London Math. Soc. (2) 34 (1932), no. 3, 190–195. MR1576145

work page 1932

[6] [6]

Fatou, S´ eries trigonom´ etriques et s´ eries de Taylor, Acta Math

P. Fatou, S´ eries trigonom´ etriques et s´ eries de Taylor, Acta Math. 30 (1906), no. 1, 335–400. MR1555035

work page 1906

[7] [7]

Foata and M

D. Foata and M. P. Sch¨ utzenberger, On the rook polynomials of Ferrers relations , Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ ured, 1969), 1970 , pp. 413–436. MR0360288 27

work page 1969

[8] [8]

Goldman, J

J. Goldman, J. Joichi, and D. White, Rook theory. I. Rook equivalence of Ferrers boards , Proc. Amer. Math. Soc. 52 (1975), 485–492. MR429578

work page 1975