A006605 Number of modes of connections of 2n points.

1, 1, 3, 11, 46, 207, 979, 4797, 24138, 123998, 647615, 3428493, 18356714, 99229015, 540807165, 2968468275, 16395456762, 91053897066, 508151297602, 2848290555562, 16028132445156, 90516256568235, 512831902620465, 2914112388802779, 16604034506299314

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• changed

Comments

Number of paths of semilength n staying weakly within the 1st quadrant starting at (0,0) and ending on the X-axis using steps (1,1), (1,-1) and (1,3). - David Scambler, Jun 21 2013

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• H. N. V. Temperley and D. G. Rogers, A note on Baxter's generalization of the Temperley-Lieb operators, pp. 324-328 of Combinatorial Mathematics (Canberra, 1977), Lect. Notes Math. 686, 1978.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..400
• Gi-Sang Cheon, Sung-Tae Jin, and Louis W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Volume 491, 15 February 2016, Pages 123-137.
• Nathan Gabriel, Katherine Peske, Lara Pudwell, and Samuel Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012) # 12.1.5.
• Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
• Simon Plouffe, Approximations of generating functions and a few conjectures, arXiv:0911.4975 [math.NT], 2009, Master's Thesis.
• Lara Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. [_N. J. A. Sloane_, Jan 03 2013]
• Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 13.
• Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, Enumeration of the Motzkin paths above a line of rational slope, Disc. Math. (2024) Vol. 347, Issue 7, 114013.

Crossrefs

Cf. A001006, A143926.

Programs

Magma

A006605:= func< n | (&+[Binomial(2*n,j-1)*Binomial(j,3*n+2-j)/j: j in [Floor((3*n+2)/2)..2*n+1]]) >;
[A006605(n): n in [0..40]]; // G. C. Greubel, Aug 29 2025

Maple

series(RootOf(x^2*g^4+x*g^2-g+1, g), x=0,20); # Mark van Hoeij, Nov 16 2011
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 1,
       2*((910*n^4 -1085*n^3  +227*n^2 +92*n -24) *a(n-1)
         +(936*n^4 -2520*n^3 +1710*n^2 +90*n-216) *a(n-2))/
      (3*n *(117*n^3 +36*n^2 -55*n -18)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 07 2012

Mathematica

Table[1/(2*n+1)*Sum[Binomial[j,2*j-2-3*n]*Binomial[2*n+1,j],{j,0,2*n+1}],{n,0,20}] (* Vaclav Kotesovec after Vladimir Kruchinin, Aug 15 2013 *)

PARI

{a(n)=polcoeff(((1/x)*serreverse(x/(1+x+x^2)^2+x^2*O(x^n)))^(1/2),n)} \\ Paul D. Hanna

SageMath

def A006605(n): return sum(binomial(2*n,j-1)*binomial(j,3*n+2-j)//j for j in range((3*n+2)//2, 2*n+2))
print([A006605(n) for n in range(41)]) # G. C. Greubel, Aug 29 2025

Formula

Reference gives explicit formula.

G.f.: A(x) = (1/x)*serreverse(x/G(x)) where G(x) is g.f. of A001006 (Motzkin numbers). G.f. satisfies: A(x)^2 = (1/x)*serreverse( x/(1+x+x^2)^2 ). - Paul D. Hanna, Mar 20 2005

G.f.: revogf is 1/2*(-x+1+(-(1+x)*(-1+3*x))^(1/2))*x. - Simon Plouffe, Master's Thesis, UQAM 1992

a(n) = A026302(n)/(n+1). - Mark van Hoeij, Jul 02 2010

a(n) = (1/(2*n+1))*Sum_{j=0...2*n+1} binomial(j,2*j-2-3*n)*binomial(2*n+1,j). - Vladimir Kruchinin, Dec 24 2010

a(n) ~ sqrt(89 + 277/sqrt(13)) * ((70 + 26*sqrt(13))/27)^n / (9*sqrt(6*Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 15 2013

With interpolated zeros, the o.g.f. = series reversion of x/(1 + x^2 + x^4) = x + x^3 + 3*x^5 + 11*x^7 + 46*x^9 + .... - Peter Bala, Dec 17 2013

Conjecture: 3*n*(3*n+2)*(3*n+1)*a(n) + (-275*n^3 + 475*n^2 - 328*n + 68)*a(n-1) + 2*(2*n-3)*(139*n^2 - 507*n + 398)*a(n-2) + 180*(2*n-5)*(n-2)*(2*n-3)*a(n-3) = 0. - R. J. Mathar, May 30 2014

Extensions

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 20 2005