pith. sign in

arxiv: 1907.09409 · v1 · pith:QQKAQKLYnew · submitted 2019-07-12 · 🧮 math.CO

The perimeter generating function for nondirected diagonally convex polyominoes

Svjetlan Fereti\'c This is my paper

Pith reviewed 2026-05-24 22:09 UTC · model grok-4.3

classification 🧮 math.CO
keywords polyominoesdiagonally convex polyominoesgenerating functionsperimeter enumerationalgebraic functionsconvex polyominoesfunctional equations
0
0 comments X

The pith

The perimeter generating function for nondirected diagonally convex polyominoes is an algebraic function of degree eight.

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

The paper establishes an explicit algebraic generating function that enumerates nondirected diagonally convex polyominoes according to perimeter. General polyomino enumeration has no known closed form, but the author shows that this restricted class admits one through a diagonal layering construction. A modification avoids generating invalid shapes that are not connected polyominoes. The resulting function satisfies a single algebraic equation of degree eight whose solution is expressed by nine polynomials, each of degree 58 or higher in the perimeter variable. This supplies a concrete, computable way to obtain the counts for any fixed perimeter.

Core claim

The main result is the perimeter generating function D(d,x) for diagonally convex polyominoes. The function is algebraic and satisfies an equation of degree eight. Its explicit formula, involving nine polynomials in d and x each of degree 58 or more in x, occupies about eight pages and is provided in an attached Maple worksheet.

What carries the argument

Layered diagonal construction of the polyominoes, modified by a trick that excludes non-polyomino configurations, which produces a functional equation solved to an algebraic degree-eight expression.

If this is right

  • The number of diagonally convex polyominoes with any given perimeter is the coefficient of the corresponding term in the explicit eight-page formula.
  • Asymptotic growth rates for the number of such polyominoes follow from singularity analysis of the algebraic equation.
  • The same construction yields generating functions for related statistics such as area once the perimeter variable is specialized.
  • Directed diagonally convex polyominoes appear as a special case whose simpler generating function can be recovered by setting a parameter to zero.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result supplies the missing generating function that separates the directed case from the general nondirected case.
  • Similar layered methods may produce algebraic equations for other non-directed convex polyomino families.
  • The high degree and polynomial sizes indicate that symbolic computation is now essential for obtaining closed forms in polyomino enumeration.

Load-bearing premise

The layered construction together with the trick to exclude non-polyominoes yields a correct functional equation whose algebraic solution of degree eight contains no computational errors.

What would settle it

Extract the first several coefficients of D(d,x) for small perimeters and compare them against an exhaustive computer enumeration of all diagonally convex polyominoes with those perimeters.

Figures

Figures reproduced from arXiv: 1907.09409 by Svjetlan Fereti\'c.

Figure 1
Figure 1. Figure 1: Top left: A polyomino. Top right: A column-convex polyomino [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A diagonally convex polyomino that is not a self-avoiding polyg [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Four diagonally convex polyominoes. The top left one has tw [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A polyomino with two noses produces another polyomino with [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A polyomino with one nose produces a polyomino with two nose [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A polyomino with zero noses produces a polyomino with two no [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A DCP with two noses and two diagonals. X∞ k=1 d 2x 4k+4z k+1 = d 2x 8 z 2 1 − x 4z . Next we consider Procedure 1. What part of A(z) does come from DCPs with two noses produced from DCPs with two noses? Extending the old last diagonal, we get 4r + 4s extra edges, and the last diagonal grows by r + s cells. Then we add a new diagonal. Thus the perimeter increases by yet four edges, and the last diagonal gr… view at source ↗
Figure 8
Figure 8. Figure 8: The formula for ∆. In the case d = 1, the Taylor series expansion of D(d, x) is D(1, x) = x 4 + 2x 6 + 7x 8 + 28x 10 + 122x 12 + 556x 14 + 2618x 16 + 12634x 18 + 62128x 20 + 310212x 22 + 1568495x 24 + 8014742x 26 + 41323641x 28 + 214719610x 30 + 1123244757x 32 + 5910863420x 34 + 31268459118x 36 + 166185855552x 38 + 886961294034x 40 + . . . (10) 7 Comparison to the perimeter generating function for column-c… view at source ↗
Figure 9
Figure 9. Figure 9: The transformation of a diagonally convex polyomino into a c [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 2
Figure 2. Figure 2: References [1] M. Bousquet-M´elou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 1–25. [2] M. Bousquet-M´elou, Rapport Scientifique pour obtenir l’habilitation `a diriger des recherches, Report No. 1154-96, LaBRI, Universit´e Bordeaux I, 1996. [3] R. Brak, A. J. Guttmann, I. G. Enting, Exact solution of the row-convex polygon perimeter generating func… view at source ↗
read the original abstract

A polyomino is a finite, edge-connected set of cells in the plane. At the present time, an enumeration of all polyominoes is nowhere in sight. On the other hand, there are several subsets of polyominoes for which generating functions are known. For example, there exists extensive knowledge about column-convex polyominoes, a model introduced by Temperley in 1956. While studying column-convex polyominoes, researchers also gave a look at diagonally convex polyominoes (DCPs), but noticed an awkward feature: when the last diagonal of a DCP is deleted, the remaining object is not always a polyomino. So researchers focused their attention on directed DCPs. (A directed DCP is such a DCP that remains a polyomino when, for any $i$, its last $i$ diagonals are deleted.) Directed DCPs gradually became well understood, whereas general DCPs have remained unexplored up to now. In this paper, we finally face general DCPs. Modulo a little trick, which saves us from dealing with non-polyominoes, we use the layered approach (described in chapter 3 of the book ``Polygons, Polyominoes and Polycubes", edited by Anthony Guttmann). The computations are of remarkable bulk. Our main result is the perimeter generating function for DCPs; we denote it $D(d,x)$. The function $D(d,x)$ is algebraic and satisfies an equation of degree eight. The formula for $D(d,x)$ is about eight pages long. That formula involves nine polynomials in $d$ and $x$, and each of those polynomials is of degree $58$ or more in $x$. The interested reader can view the formula for $D(d,x)$ in the Maple worksheet attached to this paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript derives the perimeter generating function D(d,x) for nondirected diagonally convex polyominoes. Modulo an unspecified 'little trick' to exclude non-polyominoes, the layered construction from the cited book is applied to obtain a functional equation; algebraic elimination then yields an algebraic function of degree eight whose explicit form (involving nine polynomials each of degree at least 58 in x) occupies roughly eight pages and is supplied in an attached Maple worksheet.

Significance. If correct, the result supplies the first explicit perimeter generating function for the previously unexplored class of general (nondirected) DCPs, extending the well-understood directed case. The algebraic character of the solution and the successful adaptation of the layered method constitute a concrete advance in polyomino enumeration; the provision of the Maple worksheet is a positive step toward reproducibility.

major comments (2)
  1. [Abstract] Abstract and method description: the 'little trick' that prevents the layered construction from generating non-polyominoes is alluded to but never specified. Because the correctness of the initial functional equation (and therefore of the subsequent degree-8 minimal polynomial) rests entirely on this modification, its omission renders the central derivation unverifiable from the text alone.
  2. [Main result] Main result and worksheet: the claim that D(d,x) satisfies an irreducible equation of exact degree eight is supported only by the final eight-page expression and the external worksheet. No intermediate functional equation, elimination steps, or error analysis is supplied, despite the polynomials reaching degree 58 or higher; any undetected error in setup or elimination would propagate undetected into the claimed formula.
minor comments (2)
  1. The manuscript states that the formula 'is about eight pages long' yet supplies it only via an external attachment; a brief summary of the structure of the nine polynomials (e.g., leading terms or factorizations) would improve readability without lengthening the text.
  2. Notation for the variables d and x (perimeter and area, respectively) is introduced without an explicit sentence reminding the reader of their meaning after the abstract; a single clarifying sentence in the introduction would prevent minor confusion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and for highlighting issues of verifiability. We agree that both the 'little trick' and the intermediate derivation steps require explicit treatment in the main text and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and method description: the 'little trick' that prevents the layered construction from generating non-polyominoes is alluded to but never specified. Because the correctness of the initial functional equation (and therefore of the subsequent degree-8 minimal polynomial) rests entirely on this modification, its omission renders the central derivation unverifiable from the text alone.

    Authors: We agree that the 'little trick' is central to the correctness of the functional equation and must be described explicitly. In the revised manuscript we will add a dedicated paragraph (or subsection) that fully specifies the modification to the layered construction of Chapter 3 of the cited book, including the precise rule that excludes non-polyominoes while enumerating all nondirected diagonally convex polyominoes. This will make the initial functional equation directly verifiable from the text. revision: yes

  2. Referee: [Main result] Main result and worksheet: the claim that D(d,x) satisfies an irreducible equation of exact degree eight is supported only by the final eight-page expression and the external worksheet. No intermediate functional equation, elimination steps, or error analysis is supplied, despite the polynomials reaching degree 58 or higher; any undetected error in setup or elimination would propagate undetected into the claimed formula.

    Authors: The algebraic elimination is computationally intensive, which motivated the provision of the complete Maple worksheet. Nevertheless, we accept that the main text should contain at least the functional equation obtained after applying the trick and a concise outline of the subsequent elimination strategy. We will insert these elements in the revised version. The final minimal polynomial, the nine high-degree polynomials, and the irreducibility verification will continue to be supplied via the worksheet, but the added intermediate material will allow readers to trace the logical steps without relying solely on external files. revision: yes

Circularity Check

0 steps flagged

No circularity: external layered method applied to new class

full rationale

The paper explicitly invokes the layered approach from chapter 3 of the external edited volume 'Polygons, Polyominoes and Polycubes' (Guttmann) and applies a modification ('little trick') to handle nondirected DCPs. No load-bearing step reduces by definition, by fitted input renamed as prediction, or by a self-citation chain whose cited result itself depends on the target. The resulting degree-8 algebraic equation and its explicit (lengthy) solution are presented as outputs of that independent construction; the derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the applicability of the layered approach to the new class and the correctness of the algebraic manipulations; no free parameters, new entities, or ad-hoc axioms beyond standard generating-function techniques are introduced.

axioms (1)
  • domain assumption The layered approach described in chapter 3 of the book Polygons, Polyominoes and Polycubes can be adapted to nondirected diagonally convex polyominoes via a small trick that preserves the polyomino property.
    The paper invokes this method to set up the functional equation for D(d,x).

pith-pipeline@v0.9.0 · 5871 in / 1336 out tokens · 141676 ms · 2026-05-24T22:09:13.033166+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Bousquet-M´ elou, A method for the enumeration of various c lasses of column-convex polygons, Discrete Math

    M. Bousquet-M´ elou, A method for the enumeration of various c lasses of column-convex polygons, Discrete Math. 154 (1996), 1–25

    work page 1996

  2. [2]

    Bousquet-M´ elou, Rapport Scientifique pour obtenir l’habilitat ion ` a diriger des recherches, Report No

    M. Bousquet-M´ elou, Rapport Scientifique pour obtenir l’habilitat ion ` a diriger des recherches, Report No. 1154-96, LaBRI, Universit´ e Bordeaux I, 1996

    work page 1996

  3. [3]

    R. Brak, A. J. Guttmann, I. G. Enting, Exact solution of the row -convex polygon perimeter generating function, J. Phys. A: Math. Gen. 23 (1990) , 2319–2326

    work page 1990

  4. [4]

    M. P. Delest, Generating functions for column-convex polyomino es, J. Combin. Theory Ser. A 48 (1988), 12–31

    work page 1988

  5. [5]

    Delest, J.-M

    M.-P. Delest, J.-M. F´ edou, Exact formulas for fully diagonal com pact animals, Report No. 89-06, LaBRI, Universit´ e Bordeaux I, 1989

    work page 1989

  6. [6]

    Fereti´ c, The column-convex polyominoes perimeter genera ting function for every- body, Croat

    S. Fereti´ c, The column-convex polyominoes perimeter genera ting function for every- body, Croat. Chem. Acta 69 (1996), 741–756

    work page 1996

  7. [7]

    Fereti´ c, A perimeter enumeration of column-convex polyom inoes, Discrete Math

    S. Fereti´ c, A perimeter enumeration of column-convex polyom inoes, Discrete Math. Theor. Comput. Sci. 9 (2007), 57–83

    work page 2007

  8. [8]

    Fereti´ c, D

    S. Fereti´ c, D. Svrtan, On the number of column-convex polyominoes with given perime- ter and number of columns, in: A. Barlotti, M. Delest, R. Pinzani (Ed s.), Proc. Fifth FPSAC Conference, Firenze, 1993, pp. 201–214

    work page 1993

  9. [9]

    Fereti´ c, D

    S. Fereti´ c, D. Svrtan, Combinatorics of diagonally convex dire cted polyominoes, Dis- crete Math. 157 (1996), 147–168

    work page 1996

  10. [10]

    A. J. Guttmann (Ed.), Polygons, Polyominoes and Polycubes , Lecture Notes in Physics, Vol. 775, Springer-Verlag, Berlin, 2009

    work page 2009

  11. [11]

    K. Y. Lin, Perimeter generating function for row-convex polyg ons on the rectangular lattice, J. Phys. A: Math. Gen. 23 (1990), 4703–4705. Nondirected diagonally convex polyominoes 17

    work page 1990

  12. [12]

    H. N. V. Temperley, Combinatorial problems suggested by the s tatistical mechanics of domains and of rubber-like molecules, Phys. Rev. 103 (1956), 1–16

    work page 1956