pith. sign in

arxiv: 1907.07334 · v1 · pith:JGD2QUVInew · submitted 2019-07-17 · 🧮 math.CO · math-ph· math.MP· q-bio.QM

Motzkin path on RNA abstract shapes

Sang Kwan Choi This is my paper

Pith reviewed 2026-05-24 20:37 UTC · model grok-4.3

classification 🧮 math.CO math-phmath.MPq-bio.QM
keywords RNA secondary structuresabstract shapesMotzkin pathsNarayana numbersgenerating functionscombinatorial correspondenceasymptotic distributionscomponent classification
0
0 comments X

The pith

2-Motzkin paths and Narayana numbers generate the count of abstract RNA secondary structures and establish a direct correspondence to 1-Motzkin paths.

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

The paper models a chosen abstraction of RNA secondary structures using combinatorial paths to derive an explicit generating function. It obtains this function through Narayana numbers together with 2-Motzkin paths, which simultaneously produces an algebraic identity linking those numbers to Motzkin polynomials. The same path interpretation supplies a bijection that identifies RNA shapes with ordinary 1-Motzkin paths. The authors then partition the shapes according to the number of their components and extract the asymptotic growth rates of each class. A reader cares because the construction turns an informal biological abstraction into an enumerative object whose size and distribution can be read off from well-studied sequences.

Core claim

The generating function that counts the abstract structures is obtained by means of Narayana numbers and 2-Motzkin paths; this supplies an identity relating Narayana numbers to Motzkin polynomials. A combinatorial reading of the 2-Motzkin paths yields a correspondence between 1-Motzkin paths and the RNA shapes themselves. The shapes are further classified by the number of their components, and the asymptotic distribution of each class is computed from the generating function.

What carries the argument

2-Motzkin paths equipped with a combinatorial interpretation that maps them onto 1-Motzkin paths, used together with Narayana numbers to produce the generating function for the abstract shapes.

If this is right

  • The number of abstract structures of any given length is given by a closed combination of Narayana numbers and the coefficients of 2-Motzkin path generating functions.
  • Every RNA shape corresponds to a unique 1-Motzkin path, allowing any enumeration or statistic on 1-Motzkin paths to be transferred to the shapes.
  • The distribution of shapes according to the number of components admits an explicit asymptotic formula derived from singularity analysis of the generating function.
  • Further, coarser or finer abstractions of the shapes can be obtained by imposing additional restrictions on the same 2-Motzkin path model.

Where Pith is reading between the lines

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

  • The same path model could be used to enumerate or sample RNA shapes under different probability measures induced by the Motzkin path weights.
  • The algebraic identity between Narayana numbers and Motzkin polynomials may admit a direct bijective proof independent of the RNA interpretation.
  • Because the correspondence is length-preserving, it supplies a way to translate questions about the expected number of components in random RNA shapes into questions about random Motzkin paths.
  • The asymptotic formulas could be checked against tabulated RNA databases once the abstraction map is made fully explicit.

Load-bearing premise

The chosen abstraction of RNA secondary structures preserves exactly the combinatorial features required for the Motzkin-path bijections and the generating-function derivations to remain faithful.

What would settle it

Explicit enumeration of the abstract shapes for small sequence lengths and direct comparison of those counts with the coefficients produced by the claimed generating function; any mismatch for lengths greater than 10 would falsify the counting claim.

Figures

Figures reproduced from arXiv: 1907.07334 by Sang Kwan Choi.

Figure 1
Figure 1. Figure 1: Representations of secondary structures. The RNA structure on the left hand side [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Structure elements of secondary structures. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of island diagrams. This island diagram is the abstract structure of [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Motzkin path of UHUHDDH. On the other hand, 2-Motzkin paths allow two kinds of horizontal steps, which often distinguish one from another by a color, let us say, R and B denoting a red and a blue step, respectively. We provide a bijection map between 2-Motzkin paths and strings of matching brackets.2 Suppose we have a 2-Motzkin path of size n given by a string q1 q2 · · · qn over the set {U, D, R, B}. The … view at source ↗
Figure 5
Figure 5. Figure 5: Normalized distribution M(r0; n)/Mn of Motzkin paths as a function of r0. The dots are given for n = 100. The line is the asymptotic distribution as n → ∞. 3.2 π-shapes compatible with secondary structures In the previous subsection, we considered Motzkin paths of size n, or equivalently, π-shapes of length 2n+ 2. On the other hand, instead of π-shapes with their own length fixed, one may regard π-shapes t… view at source ↗
Figure 6
Figure 6. Figure 6: Normalized distribution π4(r0; ν)/π4(ν) as a function of r0. The dots are given for ν = 200. The line is the asymptotic distribution at the limit of ν → ∞. 4 Conclusion In this paper, we established the combinatorial interpretation of 2-Motzkin paths to describe the island diagrams. The generating function of island diagrams was calculated using both 2-Motzkin paths and Narayana numbers, from which we foun… view at source ↗
Figure 7
Figure 7. Figure 7: Dyck paths of C3. From the left side, the first two are of C(3, 1), the next two are of C(3, 2) and the last one is of C(3, 3). For given Dyck paths of C(u; p), one adds n−2u horizontal steps to obtain Motzkin paths of length n. There are 2u + 1 places into which one possibly inserts horizontal steps, and of which p + 1 places are at x-axis. We first put r0 horizontal steps into the p + 1 places and then p… view at source ↗
Figure 8
Figure 8. Figure 8: The shaded region is ∆1 domain (left). When there are two dominant singularities at z = ±1, the generating function is required to be analytic in the domain on the right. B.1 Proof of Theorem 3.1 We need to find the asymptotics of Mn, M(r0; n) and P r0 r0M(r0; n). Among the three, the asymptotic of Mn is already well-known: Mn ∼ 3 n+ 3 2 /(2√ π n3/2 ). We will not derive it here, nevertheless, one may easi… view at source ↗
read the original abstract

We consider a certain abstract of RNA secondary structures, which is closely related to RNA shapes. The generating function counting the number of the abstract structures is obtained by means of Narayana numbers and 2-Motzkin paths, through which we provide an identity related to Narayana numbers and Motzkin polynomials. Furthermore, we show that a combinatorial interpretation on 2-Motzkin paths leads to the correspondence between 1-Motkzin paths and RNA shapes, which facilitates probing further classifications or abstractions of the shapes. In this paper, we classify the shapes with respect to the number of components and calculate their asymptotic distributions.

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

0 major / 1 minor

Summary. The manuscript considers an abstraction of RNA secondary structures closely related to RNA shapes. The generating function for the number of these abstract structures is derived using Narayana numbers and 2-Motzkin paths, yielding an identity involving Narayana numbers and Motzkin polynomials. A combinatorial interpretation on 2-Motzkin paths is used to establish a correspondence between 1-Motzkin paths and RNA shapes. The shapes are classified according to the number of components, and their asymptotic distributions are computed.

Significance. Should the bijections and generating-function derivations be correct, the paper offers new combinatorial tools for studying RNA abstract shapes through Motzkin paths. The provision of parameter-free identities and explicit correspondences is a notable strength, as is the classification by number of components with asymptotics. This may aid in further classifications or abstractions of RNA shapes.

minor comments (1)
  1. [Abstract] Abstract: the term '1-Motkzin paths' is a typographical error and should read '1-Motzkin paths'.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its combinatorial contributions, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation uses external classical objects

full rationale

The paper introduces an abstraction of RNA shapes and derives its enumeration via generating functions expressed in terms of Narayana numbers and Motzkin paths. These are standard, externally defined combinatorial objects whose definitions and properties predate the paper and are not redefined or fitted within it. The claimed identity and bijection are parameter-free enumerative statements obtained by algebraic manipulation and combinatorial interpretation; no step reduces a prediction to a fitted input, invokes a self-citation as a uniqueness theorem, or renames a result by construction. The abstraction is chosen precisely to make the bijections work, but this is an explicit modeling choice rather than a hidden definitional loop.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard generating-function algebra and known properties of Narayana numbers and Motzkin paths; no free parameters, ad-hoc axioms, or new postulated entities are introduced in the abstract.

axioms (1)
  • standard math Standard algebraic properties of ordinary generating functions and the known closed forms or recurrences for Narayana numbers and Motzkin polynomials hold.
    Invoked to obtain the counting generating function and the stated identity.

pith-pipeline@v0.9.0 · 5627 in / 1275 out tokens · 19637 ms · 2026-05-24T20:37:05.350943+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Fast algorithm for predicting the secondary structure of single-stranded RNA.,

    R. Nussinov and A. B. Jacobson, “Fast algorithm for predicting the secondary structure of single-stranded RNA.,” Proceedings of the National Academy of Sciences of the United States of America, vol. 77, no. 11, pp. 6309–13, 1980

    work page 1980

  2. [2]

    Optimal computer folding of large RNA sequences using ther- modynamics and auxiliary information,

    M. Zuker and P. Stiegler, “Optimal computer folding of large RNA sequences using ther- modynamics and auxiliary information,” Nucleic Acids Research, vol. 9, no. 1, pp. 133– 148, 1981

    work page 1981

  3. [3]

    Rna secondary structures and their prediction,

    M. Zuker and D. Sankoff, “Rna secondary structures and their prediction,” Bulletin of Mathematical Biology, vol. 46, no. 4, pp. 591 – 621, 1984

    work page 1984

  4. [4]

    Rna structures and folding: from conventional to new issues in structure predictions,

    P. Schuster, P. F. Stadler, and A. Renner, “Rna structures and folding: from conventional to new issues in structure predictions,” Current Opinion in Structural Biology , vol. 7, no. 2, pp. 229 – 235, 1997

    work page 1997

  5. [5]

    On some new sequences generalizing the catalan and motzkin numbers,

    P. Stein and M. Waterman, “On some new sequences generalizing the catalan and motzkin numbers,” Discrete Mathematics, vol. 26, no. 3, pp. 261 – 272, 1979

    work page 1979

  6. [6]

    Combinatorics of RNA secondary struc- tures,

    I. L. Hofacker, P. Schuster, and P. F. Stadler, “Combinatorics of RNA secondary struc- tures,” Discrete Applied Mathematics, vol. 88, no. 1-3, pp. 207–237, 1998. 17

    work page 1998

  7. [7]

    Linear trees and rna secondary structure,

    W. R. Schmitt and M. S. Waterman, “Linear trees and rna secondary structure,” Discrete Applied Mathematics, vol. 51, no. 3, pp. 317 – 323, 1994

    work page 1994

  8. [8]

    RNA Secondary Structures Having a Compat- ible Sequence of Certain Nucleotide Ratios,

    C. L. Barrett, T. J. Li, and C. M. Reidys, “RNA Secondary Structures Having a Compat- ible Sequence of Certain Nucleotide Ratios,” Journal of Computational Biology , vol. 23, pp. 857–873, 2016

    work page 2016

  9. [9]

    RNA substructure as a random matrix ensemble,

    S. K. Choi, C. Rim, and H. Um, “RNA substructure as a random matrix ensemble,” 2016

    work page 2016

  10. [10]

    Secondary structure of single-stranded nucleic acids,

    M. S. Waterman, “Secondary structure of single-stranded nucleic acids,” Adv. math. suppl. studies, vol. 1, pp. 167–212, 1978

    work page 1978

  11. [11]

    Abstract shapes of rna,

    R. Giegerich, B. Voss, and M. Rehmsmeier, “Abstract shapes of rna,” Nucleic Acids Research, vol. 32, no. 16, pp. 4843–4851, 2004

    work page 2004

  12. [12]

    RNA folding and large n matrix theory,

    H. Orland and A. Zee, “RNA folding and large n matrix theory,” Nucl. Phys., vol. B620, pp. 456–476, 2002

    work page 2002

  13. [13]

    Topology and prediction of RNA pseudoknots,

    C. M. Reidys, F. W. D. Huang, J. E. Andersen, R. C. Penner, P. F. Stadler, and M. E. Nebel, “Topology and prediction of RNA pseudoknots,”Bioinformatics, vol. 27, pp. 1076– 1085, apr 2011

    work page 2011

  14. [14]

    Shape based indexing for faster search of rna family databases,

    S. Janssen, J. Reeder, and R. Giegerich, “Shape based indexing for faster search of rna family databases,” BMC Bioinformatics, vol. 9, p. 131, Feb 2008

    work page 2008

  15. [15]

    On quantitative effects of RNA shape abstraction,

    M. E. Nebel and A. Scheid, “On quantitative effects of RNA shape abstraction,” Theory in Biosciences, vol. 128, no. 4, pp. 211–225, 2009

    work page 2009

  16. [16]

    Enumerating a class of lattice paths,

    C. Coker, “Enumerating a class of lattice paths,” Discrete Mathematics, vol. 271, no. 1, pp. 13 – 28, 2003

    work page 2003

  17. [17]

    Identities from weighted motzkin paths,

    W. Y. Chen, S. H. Yan, and L. L. Yang, “Identities from weighted motzkin paths,” Advances in Applied Mathematics , vol. 41, no. 3, pp. 329 – 334, 2008

    work page 2008

  18. [18]

    Motzkin numbers,

    R. Donaghey and L. W. Shapiro, “Motzkin numbers,” Journal of Combinatorial Theory, Series A, vol. 23, no. 3, pp. 291 – 301, 1977

    work page 1977

  19. [19]

    Asymptotics of rna shapes,

    W. A. Lorenz, Y. Ponty, and P. Clote, “Asymptotics of rna shapes,” Journal of Compu- tational Biology, vol. 15, no. 1, pp. 31–63, 2008

    work page 2008

  20. [20]

    Narayana number, chebyshev polynomial and motzkin path on rna abstract shapes,

    S. K. Choi, C. Rim, and H. Um, “Narayana number, chebyshev polynomial and motzkin path on rna abstract shapes,” in 2017 MATRIX Annals (D. R. Wood, J. de Gier, C. E. Praeger, and T. Tao, eds.), pp. 153–156, Springer, 2019

    work page 2017

  21. [21]

    A note on narayana triangles and related polynomials, Ri- ordan arrays, and MIMO capacity calculations,

    P. Barry and A. Hennessy, “A note on narayana triangles and related polynomials, Ri- ordan arrays, and MIMO capacity calculations,” Journal of Integer Sequences , vol. 14, no. 3, pp. 1–26, 2011

    work page 2011

  22. [22]

    Sur certaines ´equations fonctionnelles,

    J. Touchard, “Sur certaines ´equations fonctionnelles,” Proceedings of the International Congress on Mathematics, Toronto (1924) , vol. 1, pp. 465 – 472, 1928

    work page 1924

  23. [23]

    Algebraic languages and polyominoes enumeration,

    M.-P. Delest and G. Viennot, “Algebraic languages and polyominoes enumeration,” The- oretical Computer Science, vol. 34, no. 1, pp. 169 – 206, 1984. 18

    work page 1984

  24. [24]

    Sur les nombres de segner,

    M. E. Catalan, “Sur les nombres de segner,” Rendiconti del Circolo Matematico di Palermo (1884-1940), vol. 1, pp. 190–201, Dec 1887

    work page 1940

  25. [25]

    A forgotten convolution type identity of catalan,

    P. Larcombe, “A forgotten convolution type identity of catalan,” Utilitas Mathematica, vol. 57, 05 2000

    work page 2000

  26. [26]

    Flajolet and R

    P. Flajolet and R. Sedgewick, Analytic Combinatorics. New York, NY, USA: Cambridge University Press, 1 ed., 2009

    work page 2009

  27. [27]

    Singularity analysis of generating functions,

    P. Flajolet and A. Odlyzko, “Singularity analysis of generating functions,” SIAM Journal on Discrete Mathematics , vol. 3, no. 2, pp. 216–240, 1990. 19

    work page 1990