Pith. sign in

REVIEW 3 major objections 6 minor 13 references

Generating Trees and Fibonacci Polyominoes

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper derives exact rational generating functions that enumerate p-Fibonacci polyominoes by length, area, and semiperimeter, and by inner points, with bijections to restricted compositions and binary words.

desk verdict Correct generating functions for a real generalization of Fibonacci polyominoes to p>2, but the paper has a few fixable exposition errors, including a wrong example in Theorem 2.4. read the letter →

arxiv 2411.17812 v1 pith:L5Z62FAF submitted 2024-11-26 math.CO

Juan F. Pulido , José L. Ramírez , Andrés R. Vindas-Meléndez This is my paper · ORCID
classification math.CO MSC 05A1505A0511B39
keywords p-Fibonacciwordpolyominobargraphgeneratingfunctionp-generalizedFibonaccinumberssemiperimeterinnerpointsintegercompositions
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

The paper studies p-Fibonacci polyominoes, bargraphs whose column heights form p-Fibonacci words, and establishes exact enumerations by length, area, semiperimeter, and inner points. Its main result is a rational multivariate generating function that packages all three shape statistics, from which closed forms for total area and total semiperimeter follow by differentiation. A second generating function handles inner points, and an identity from Pick's theorem connects the three statistics to the p-generalized Fibonacci numbers. The paper also proves bijections between these polyominoes, restricted compositions, and binary words avoiding $p$ consecutive ones. If the formulas are correct, these otherwise complicated objects become exactly and computationally tractable.

What carries the argument

The engine is a last-column recurrence. In a p-Fibonacci word, a symbol $i<p$ must be preceded by $i+1$, while $p$ may follow any symbol; this makes the class recursive and produces a finite system of equations for the generating functions $F_{p,i}$ and $G_{p,i}$. Solving those systems gives Theorem 2.1 and Theorem 2.3. The same structure appears as the generating tree $\Omega_p$, and reading a word as concatenated descending blocks $p,p-1,\dots,p-k$ yields the bijection to compositions with parts $(p+i)(p-i+1)/2$.

What would settle it

Take $p=3$, enumerate all 3-Fibonacci words of lengths $1$ through $4$, build the corresponding bargraphs, compute area, semiperimeter, and inner points directly, and compare the resulting coefficient lists with the series expansions of $F_3(x;y,z)$ and $G_3(x;q)$ printed in the paper; any mismatch in a coefficient or exponent would falsify the formulas.

Watch

Extended reading notes

Core claim

The central claim is that the class of p-Fibonacci polyominoes, bargraphs whose column heights form a p-Fibonacci word, is exactly enumerated by the rational generating function $F_p(x;y,z)=1+\frac{\sum_{i=1}^p x^{p-i+1}y^{(p+i)(p-i+1)/2}z^{2p-i+1}}{1-xy^p z-\sum_{i=1}^{p-1}x^{p-i+1}y^{(p+i)(p-i+1)/2}z^{2p-2i+1}}$, where $x$ marks columns, $y$ marks area, and $z$ marks semiperimeter. A parallel generating function $G_p(x;q)$ counts the same polyominoes by inner points. From these, the paper obtains closed rational forms for the total area, total semiperimeter, and total inner points over all polyominoes with $n$ columns, and derives the identity $F_{p,n+1}=ip(n)+sp(n)-ap(n)$ from Pick's theorem.

Load-bearing premise

The recurrences for semiperimeter and inner points rely on an unstated rule for how these statistics change when a column is appended to a bargraph; if that increment rule is wrong, the exponents in Theorems 2.1 and 2.3 fail.

Editorial extensions

If this is right

  • For each fixed $p$, expanding $F_p(x;y,z)$ and $G_p(x;q)$ yields tables of p-Fibonacci polyominoes by length, area, semiperimeter, and inner points, as the paper displays for $p=2,3,4$.
  • Setting $y=z=1$ in Theorem 2.1 gives $F_p(x;1,1)=1/(1-x-x^2-\cdots-x^p)$, so the number of polyominoes with $n$ columns is exactly the p-generalized Fibonacci number $F_{p,n+1}$.
  • Differentiating at $y=z=1$ produces the closed forms for the total area $A_p(x)$ and total semiperimeter $S_p(x)$; differentiating $G_p$ at $q=1$ produces the total inner points $I_p(x)$.
  • Pick's theorem gives $F_{p,n+1}=ip(n)+sp(n)-ap(n)$, expressing the p-generalized Fibonacci numbers directly through the three geometric statistics.
  • Theorem 2.2 and Theorem 2.4 give bijections between area-$n$ polyominoes and restricted compositions, and between length-$n$ words and binary words with no $p$ consecutive ones.

Reading between the lines

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

  • Because both generating functions are rational, all fixed-order cumulants of area, semiperimeter, and inner points, not just totals, can be obtained by differentiation, and the asymptotic growth of every statistic is controlled by the dominant singularity of $1-x-\cdots-x^p$; the paper does not pursue these consequences.
  • The bijection with binary words suggests a one-bit-per-step encoding of p-Fibonacci polyominoes, which would give a simple uniform random generation algorithm and a linear-time decoder from binary code to polyomino.
  • The last-column recurrence should transfer to other word-defined polyomino families whose production rules give most symbols a unique predecessor, yielding analogous rational generating functions; this generalization is implicit but not developed.
  • The identity $F_{p,n+1}=ip(n)+sp(n)-ap(n)$ invites a bijective proof: if the expression can be interpreted as counting configurations, it would give a direct combinatorial proof of the p-generalized Fibonacci recurrence.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper defines p-Fibonacci words and the bargraph polyominoes obtained by taking the symbols as column heights. The main results are multivariate generating functions for p-Fibonacci polyominoes with respect to length, area, semiperimeter, and number of inner points (Theorems 2.1 and 2.3), closed forms for the total area, semiperimeter, and inner points over all polyominoes with n columns, a generating function for polyominoes of a given area together with a bijection to compositions with parts in a finite set A_p (Theorem 2.2), and a claimed bijection between p-Fibonacci words and binary words avoiding p consecutive 1s (Theorem 2.4). The paper also connects the three statistics via Pick's theorem through the identity F_{p,n+1}=ip(n)+sp(n)-ap(n).

Significance. If the proofs are brought to the same standard as the formulas, the paper gives exact, parameter-free enumerations of a natural class of bargraph polyominoes by several geometric statistics, with rational generating functions that can be checked against small cases and differentiated to obtain total statistics. The composition bijection in Theorem 2.2 is elegant and appears correct. The main weakness is not the validity of the formulas but the presentation of the underlying geometric recurrences and one internally inconsistent bijection proof; both are repairable. As it stands, the manuscript is a useful contribution but needs revision before it can be accepted.

major comments (3)
  1. [§2.1, Cases 1 and 2] The recurrences used in Theorems 2.1 and 2.3 encode a geometric increment rule that is never stated or proved. For a bargraph with last column height j, appending a column of height i to the right changes the semiperimeter by 1 if i ≤ j and by 1+(i−j) if i > j; this is what the z-exponents in Eq. (5) and in the equation for F_{p,p} express. Similarly, the recurrences G_{p,i}=x q^{i−1}G_{p,i+1} and G_{p,p}=x+Σ_{j=1}^p x q^{j−1}G_{p,j} assume, via Pick's theorem, that appending a column of height i changes the number of inner points by i−1 (or j−1 in the p-append case). I checked the rule directly from sper = n + (h_1+h_n)/2 + ½Σ|h_i−h_{i+1}| and from area = inn + sper − 1, and it is correct, so the formulas are not invalidated. Nevertheless, the proof of Theorem 2.1 is incomplete as written because the exponents are asserted without geometric justification, and a reader cannot verify them from the stated decomposition.
  2. [§2.4, Theorem 2.4] The verbal decomposition in §2.1 is incompatible with the recurrences. The text says a polyomino in B^{(p,i)}_n 'starts with a column of p cells, followed by' a polyomino P′ in B^{(p,i+1)}_{n−1}, and similarly for Case 2. But the recurrences F_{p,i}=xy^i z F_{p,i+1} and F_{p,p}=xy^p z^{p+1}+xy^p Σ_j z^{p+1-j}F_{p,j} are rightmost-append recurrences: they remove or add the last column. As written, if P starts with p and is followed by a polyomino ending in i+1, then P ends in i+1, not i, so the case division does not match the definitions of B^{(p,i)}_n. The proof should be rewritten in terms of appending a column to the right of a polyomino whose last column has a specified height, and the geometric increment lemma above should be stated and proved there.
  3. [Conclusion, Figure 8] The proof of Theorem 2.4 is internally inconsistent. The forward map assigns 0 to increases or unchanged digits and 1 to decreases. The reverse construction, however, says to append the 'allowed descending digit' on a 0 and the 'allowed ascending or unchanged digit' on a 1, which is exactly the opposite convention. Under the stated forward map, the example word 33233233 has transitions 3→3, 3→2, 2→3, 3→3, 3→2, 2→3, 3→3, so it maps to 0100100, not to 1011011. Conversely, 1011011 generates 33233233 only if 0 is interpreted as a descent and 1 as an ascent. The sentence 'each word has at most p−1 ascents' should also read 'at most p−1 consecutive descents.' The bijection itself is plausible and can be repaired by fixing the inverse rule and the example, but the proof as written does not establish the theorem.
minor comments (6)
  1. [§2.3.1] The displayed set W^{(3)}_4 contains the word 3323 twice; there are only seven 3-Fibonacci words of length 4, as shown correctly in Figure 2.
  2. [§2.4 closing paragraph] The subsection title contains a typo: 'Fibonaci' should be 'Fibonacci.'
  3. [Figure 8] The sentence 'the subset of p-generalized Fibonacci words of length n or equivalently the p-generalized Fibonacci polyominoes with area n' conflates length (number of columns) with area; a word of length n corresponds to a polyomino with n columns, not area n.
  4. [Theorem 2.2 proof] The examples in Figure 8 do not appear to follow the bijections stated in Theorem 2.4: for instance, the word 32321 would correspond to the binary word 1011 under the mapping of Theorem 2.4, not to 110. The figure should be redrawn or its conventions explained.
  5. [Section 2, Eq. (3)] In the example in the proof of Theorem 2.2, the word 32321 is split into blocks 32 and 321, which is correct, but the sentence introducing the blocks should make clear that the decomposition is deterministic and reads the word from left to right, starting a new block at each occurrence of p that is not part of the current descending run.
  6. [Abstract] The identity F_{p,n+1}=ip(n)+sp(n)-ap(n) is presented as 'interesting,' but it follows immediately from Pick's theorem after summing over the F_{p,n+1} polyominoes; this derivation should be stated explicitly in one sentence.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main generating functions are derived from the p-Fibonacci word definition, and the only load-bearing external inputs (Baril–Do characterization and Pick’s theorem) are not self-citations.

full rationale

The derivation chain is self-contained. Theorem 2.1’s recurrences follow directly from the definition of p-Fibonacci words: a word ending in i (1 ≤ i ≤ p−1) is obtained by appending the column height i to a word ending in i+1, while a word ending in p is either the single column of height p or is obtained by appending p to any p-Fibonacci word. The z-exponents in the recurrences are the true semiperimeter increments for bargraphs (1 when appending a column no taller than the previous one, and p+1−j when appending p after height j), and the y-exponents are the added areas; the rational function in Theorem 2.1 is then obtained by solving the resulting linear system algebraically. Theorem 2.3 uses the same rightmost-append structure for inner points, with the q-exponents i−1 and j−1 being the genuine increments in interior lattice points, as can be verified by Pick’s theorem. The identity F_{p,n+1} = ip(n) + sp(n) − ap(n) is an application of Pick’s theorem to each polyomino and is not used as an input to the enumeration. The only cited inputs that are load-bearing are Baril and Do’s characterization of p-generalized Fibonacci words and Pick’s theorem; both are external, and the self-citations in the bibliography appear only as contextual examples of prior polyomino work, not as justification of any theorem. No parameter is fitted to data and no prediction is forced by construction: the tables and OEIS checks are consequences of the derived generating functions, and the bijections in Theorems 2.2 and 2.4 are proved from the word and composition definitions. The geometric increment rules underlying the recurrences are not stated as a separate lemma, which is an exposition gap rather than a circular step, since the increments follow directly from bargraph geometry and are confirmed by the displayed p = 2, 3, 4 series.

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

No free parameters are fitted, and no new physical or auxiliary entities are postulated. The p-Fibonacci polyomino class is the object of study rather than a hidden assumption. The axioms are the known word characterization, Pick's theorem, and an implicit geometric increment rule for the statistics.

assumptions (3)
  • domain assumption The production system Omega_p encodes p-generalized Fibonacci numbers, and p-Fibonacci words are characterized by the transition rule in Equation (2).
    Imported from Baril and Do (2006) as the foundation of the paper's definitional framework. If this characterization were wrong, the entire enumeration would fail.
  • standard math Pick's theorem applies to p-Fibonacci polyominoes as simple lattice polygons, yielding area = inn + sper - 1.
    Used in Section 2 to derive Equation (3). The paper states the theorem and applies it.
  • domain assumption Semiperimeter and inner point increments under column appending follow the rules used implicitly in the recurrences: adding a column of height i after height j increases semiperimeter by 1 if i <= j and by 1 + (i-j) if i > j, and increases inner points by i-1 in the descent case.
    This geometric increment rule is used in the z-exponents and q-exponents of the recurrences in Theorems 2.1 and 2.3 and is not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generating Trees and Fibonacci Polyominoes." pith.science (2026). https://pith.science/paper/L5Z62FAF

@misc{pith2026241117812,
  author       = {Pith},
  title        = {Pith review of: Generating Trees and Fibonacci Polyominoes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L5Z62FAF}},
  note         = {Machine review of arXiv:2411.17812}
}
abstract

We study a new class of polyominoes, called $p$-Fibonacci polyominoes, defined using $p$-Fibonacci words. We enumerate these polyominoes by applying generating functions to capture geometric parameters such as area, semi-perimeter, and the number of inner points. Additionally, we establish bijections between Fibonacci polyominoes, binary Fibonacci words, and integer compositions with certain restrictions.

Figures

Figures reproduced from arXiv: 2411.17812 by the authors.

Figure 1
Figure 1. Generating tree induced by Ω3. A production system Ω induces a sequence of positive integers (an)n≥0, where an is the number of nodes at level n in the generating tree. For our example, the first few values of the sequence an are 1, 2, 4, 7, 13, ... . In general, this sequence corresponds to the 3- generalized Fibonacci numbers, also known as the tribonacci numbers (sequence A000073 in the OEIS [13]). The systematic… view at source ↗
Figure 2
Figure 2. Initial levels of the planar tree associated to the words of W(3) . Recently, the combinatorial study of different families of words has been explored through their interpretation as polyominoes. A polyomino is a finite collection of unit squares connected along their edges. The connection between these objects is important because, although polyominoes are simple to describe, their combinatorics can be quite challe… view at source ↗
Figure 3
Figure 3. The 3-Fibonacci polyominoes of length 4. The main purpose of this paper is to enumerate the p-Fibonacci polyominoes based on their length (number of columns) and geometric parameters, including area, semi￾perimeter, and the number of inner points. We make use of generating functions to describe our results. We also introduce a novel method to calculate the generalized p-Fibonacci numbers using the three aforemention… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The area, perimeter, and inner points of a polyomino. We can interpret our polyominoes (bargraphs) as polygons. The area, perimeter, and number of lattice points of a polygon are connected by Pick’s theorem [12]. Let T be a simple polygon (non-self-intersecting) with i…
Figure 5
Figure 5. Figure 5: Decomposition of a p-Fibonacci polyomino. The coefficient x n y i z j in the generating function Fp(x; y , z) corresponds to the number of p-Fibonacci polyominoes P with n columns such that area(P) = i and sper(P) = j. In Theorem 2.1, we provide a rational expression f…
Figure 6
Figure 6. Figure 6: Weights for 4-Fibonacci polyominoes with 3 columns. From Theorem 2.1, we can derive several results, including those related to the total area and semi-perimeter of p-Fibonacci polyominoes with a fixed number of columns. 2.2.1. Total area of Fibonacci polyominoes. Let …
Figure 7
Figure 7. Figure 7: Weights for 4-Fibonacci polyominoes with 3 columns. 2.3.1. Total number of inner points of Fibonaci polyominoes. Let Ip(x) denote the generating function for the sequence ip(n), which represents the total number of inner points of the p-Fibonacci polyominoes with n col…
Figure 8
Figure 8. Figure 8: Family of Bijections. Acknowledgements The first two authors were partially supported by Universidad Nacional de Colombia, Project No. 57340. References 1. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: a methodology for the enumeration of combinatorial ob…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Barcucci, A

    E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, J. Differ. Equations Appl. 5 (1999), no. 4-5, 435–490

    work page 1999

  2. [2]

    Baril and P.-T

    J.-L. Baril and P.-T. Do, ECO-generation for p-generalized Fibonacci and Lucas permutations , Pure Math. Appl. (PU.M.A.) 17 (2006), no. 1-2, 19–37. 14 J. F. PULIDO, J. L. RAM ´IREZ, AND A R. VINDAS-MEL ´ENDEZ

    work page 2006

  3. [3]

    The Combinatorics of Motzkin Polyominoes

    J.-L. Baril, S. Kirgizov, J.L. Ram ´ ırez, and D. Villamizar, The combinatorics of Motzkin polyominoes , 2024, preprint (arXiv:2401.06228)

    work page Pith review arXiv 2024

  4. [4]

    Bernini, Restricted binary strings and generalized Fibonacci numbe rs, In: International Workshop on Cellular Automata and Discrete Complex Systems, Springer (2017 ), 32–43

    A. Bernini, Restricted binary strings and generalized Fibonacci numbe rs, In: International Workshop on Cellular Automata and Discrete Complex Systems, Springer (2017 ), 32–43

    work page 2017

  5. [5]

    Blecher, C

    A. Blecher, C. Brennan, and A. Knopfmacher, Combinatorial parameters in bargraphs , Quaest. Math. 39 (2016), no. 5, 619–635

    work page 2016

  6. [6]

    Blecher, C

    A. Blecher, C. Brennan, A. Knopfmacher, and M. Shattuck, Capacity of permutations , Ann. Math. Inform. 50 (2019), 39–56

    work page 2019

  7. [7]

    Callan, T

    D. Callan, T. Mansour, and J.L. Ram ´ ırez, Statistics on bargraphs of Catalan words , J. Autom. Lang. Comb. 26 (2021), no. 3-4, 177–196

    work page 2021

  8. [8]

    A. J. Guttmann (ed.), Polygons, Polyominoes and Polycubes , Lecture Notes in Physics, vol. 775, Springer, 2009

    work page 2009

Show all 13 references
  1. [9]

    Heubach and T

    S. Heubach and T. Mansour, Combinatorics of Compositions and Words , CRC Press, 2009

    2009

  2. [10]

    Kirgizov and J.L

    S. Kirgizov and J.L. Ram ´ ırez, Polyominoes and graphs built from Fibonacci words , Fibonacci Quart. 60 (2022), no. 5, 196–211

    2022

  3. [11]

    Mansour and A

    T. Mansour and A. Sh. Shabani, Enumerations on bargraphs , Discrete Math. Lett. 2 (2019), 65–94

    2019

  4. [12]

    Pick, Geometrisches zur Zahlentheorie , Sitzenber 19 (1899), 311–319

    G. Pick, Geometrisches zur Zahlentheorie , Sitzenber 19 (1899), 311–319

  5. [13]

    Sloane, The On-Line Encyclopedia of Integer Sequences , 2024, published electronically at http://oeis.org

    N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences , 2024, published electronically at http://oeis.org. Departamento de Matem ´aticas, Universidad Nacional de Colombia, Bogot ´a, Colombia Email address : jupulidom@unal.edu.co Departamento de Matem ´aticas, Universida...

    2024

Pith tools

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