A140662 Number of possible column states for self-avoiding polygons in a slit of width n.

1, 3, 8, 20, 50, 126, 322, 834, 2187, 5797, 15510, 41834, 113633, 310571, 853466, 2356778, 6536381, 18199283, 50852018, 142547558, 400763222, 1129760414, 3192727796, 9043402500, 25669818475, 73007772801, 208023278208, 593742784828, 1697385471210, 4859761676390

Offset

1,2

Comments

Number of Dyck (n+1)-paths whose maximum ascent length is 2. - David Scambler, Aug 22 2012

Number of (n+1)-Motzkin-paths with at least one up-step (see A001006 and the Python program). - Peter Luschny, Dec 03 2024

Links

Table of n, a(n) for n=1..30.

J. Alvarez, E.J. Janse van Rensburg et al. Self-avoiding walks and polygons in slits.

Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See p. 7.

Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 148.

Formula

a(n) = Sum_{m=1..[(n+1)/2]} (n+1)!/((n+1-2m)!m!(m+1)!).

a(n) = A001006(n + 1) - 1. [Corrected by Peter Luschny, Dec 03 2024]

D-finite with recurrence (n+3)*a(n) + (-4*n-7)*a(n-1) + (2*n+3)*a(n-2) + (4*n-5)*a(n-3) + 3*(-n+2)*a(n-4) = 0. - R. J. Mathar, Nov 01 2021

From Peter Luschny, Dec 03 2024: (Start)

a(n) = (1/2)*n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4).

a(n) = n!*[x^n]((exp(x)*(-x^3 + 2*(2*x - 3)*x*BesselI(0,2*x) + (x*(5*x - 4) + 6)*BesselI(1, 2* x)))/x^3). (End)

Example

The 20 Motzkin-paths of length 5 with at least one up-step are: UUDDF, UUDFD, UUFDD, UDUDF, UDUFD, UDFUD, UDFFF, UFUDD, UFDUD, UFDFF, UFFDF, UFFFD, FUUDD, FUDUD, FUDFF, FUFDF, FUFFD, FFUDF, FFUFD, FFFUD.

Maple

a := n -> n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4)/2:
seq(simplify(a(n)), n = 1..30);  # Peter Luschny, Dec 03 2024

Prog

(Python)
# A generator of the Motzkin-paths with at least one up-step.
C = str.count
def aGen(n: int): # -> Generator[str, Any, list[str]]
    a = [""]
    for w in a:
        if len(w) == n + 1:
            if (C(w, "U") > 0 and C(w, "U") == C(w, "D")): yield w
        else:
            for j in "UDF":
                u = w + j
                if C(u, "U") >= C(u, "D"): a += [u]
    return a
for n in range(1, 6):
    SAP = [w for w in aGen(n)]
    print(len(SAP), ":", SAP)  # Peter Luschny, Dec 03 2024

Crossrefs

Cf. A055151, A080159, A088617, A107131, A097610.

Cf. A001006.

Column k=2 of A203717 (shifted).

Sequence in context: A026582 A187003 A101893 * A174198 A396787 A384176

Adjacent sequences: A140659 A140660 A140661 * A140663 A140664 A140665

Keyword

easy,nonn

Author

R. J. Mathar, Jul 11 2008

Status

approved