A001005 Number of ways of partitioning n points on a circle into subsets only of sizes 2 and 3.

1, 0, 1, 1, 2, 5, 8, 21, 42, 96, 222, 495, 1177, 2717, 6435, 15288, 36374, 87516, 210494, 509694, 1237736, 3014882, 7370860, 18059899, 44379535, 109298070, 269766655, 667224480, 1653266565, 4103910930, 10203669285, 25408828065, 63364046190, 158229645720, 395632288590, 990419552730

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• eigen

Comments

a(n) is also the number of rooted trees on n nodes such that each node has 0, 2, or 3 children. - Patrick Devlin, Mar 04 2012

a(n) is the number of Motzkin paths that have no flatsteps (F) at ground level and avoid a factor of the form FMF with M a Motzkin path (possibly empty). For example, a(5) = 5 counts UDUFD, UFDUD, UFUDD, UUDFD, UUFDD but not UFFFD. Proof: Such a path can have at most one flatstep at height 1 before the first return to ground level or else the first component will contain an FMF. Hence, with a dot denoting concatenation, such a path is either empty or has the form U.P1.D.P2 or the form U.P1.F.P2.D.P3 where P1, P2, P3 are all paths of the type being counted. Hence the gf F(x) = 1 + x^2 + x^3 + 2*x^4 + ... satisfies F = 1 + x^2*F^2 + x^3*F^3. - David Callan, Nov 21 2021

Examples

			a(7)=21: 7 rotations of [12][34][567], 7 rotations of [12][45][367], 7 rotations of [12][37][456]. - _Len Smiley_, Jun 18 2005
From _Wolfdieter Lang_, Nov 05 2018: (Start)
a(7) = b(8)/8, where b(8) = (d^7/dx^7)((1 + x^2 + x^3)^8)/7! evaluated for x = 0, which is 168, and 168/8 = 21.
a(7) =(1/8)*8!/((8-(2+1))!*2!*1!) =(1/8)*8!/(5!*2!)= 168/8 = 21, from the only solution [e2, e3] = [2, 1] of 2*e2 + 3*e3 = 7. (End)
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
• F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
• Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 396
• T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
• Len Smiley, a(7) and a(8)
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A321201.

Programs

Maple

a:=proc(n::nonnegint) local k,j; a(n):=0; for k from 0 to floor(n/2) do for j from 0 to floor(n/3) do if (2*k+3*j=n) then a(n):=a(n)+(n)!/(k!*j!*(n-k-j+1)!) fi od od; print(a(n)) end proc; seq(a(i),i=0..30); # Len Smiley, Jun 18 2005
A001005 := n -> ifelse(n=0, 1, add(binomial(n, k-1)*binomial(k, n-2*k)/k, k = 1 + iquo(n-1,3)..iquo(n,2))): seq(A001005(n), n=0..35); # Peter Luschny, Oct 18 2022

Mathematica

Table[Sum[(n)!/(k!*j!*(n - k - j + 1)!) * KroneckerDelta[2*k + 3*j - n], {k, 0, Floor[n/2]}, {j, 0, Floor[n/3]}], {n, 0, 20}] (* Ricardo Bittencourt, Jun 09 2013 *)
CoefficientList[ InverseSeries[x/(1+x^2+x^3) + O[x]^66]/x, x] (* Jean-François Alcover, Feb 15 2016, after Joerg Arndt*)

PARI

Vec(serreverse(x/(1+x^2+x^3)+O(x^66))/x) /* Joerg Arndt, Aug 19 2012 */

Formula

G.f. for a(n-1), with a(-1) = 0, satisfies A(x)=x*(1+A(x)^2+A(x)^3). - Christian G. Bower, Dec 15 1999

a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..floor(n/3)} n!/(k!*j!*(n-k-j+1)!)*[2*k+3*j=n]. - Len Smiley, Jun 18 2005

Recurrence: 2*(n+1)*(2*n+3)*(26*n+1)*a(n) = -(n-1)*(26*n^2 + 53*n + 18)*a(n-1) + 6*(n-1)*(78*n^2 + 42*n - 25)*a(n-2) + 31*(n-2)*(n-1)*(26*n+27)*a(n-3). - Vaclav Kotesovec, Aug 14 2013

a(n) ~ c*d^n/n^(3/2), where d = ((6371-624*sqrt(78))^(1/3)+(6371+624*sqrt(78))^(1/3)-1)/12 = 2.610718613276039349818649... is the root of the equation 4d^3 + d^2 - 18d - 31 = 0 and c = d^2 / (2*sqrt(Pi)*sqrt(1 + 3*d + sqrt(1 + 3*d))) = 0.559628309722556021604897336422272... - Vaclav Kotesovec, Aug 14 2013, updated Jun 27 2018

a(n) = Sum_{k=1..floor(n/2)} C(n,k-1)*C(k,n-2k)/k, n > 0. - Michael D. Weiner, Mar 02 2015

From Wolfdieter Lang, Nov 05 2018: (Start)

The o.g.f of a(n) is G(x) = F^[-1](x)/x, where F^[-1](x) is the compositional inverse of F(y) = y/(1 + y^2 + y^3), that is F(F^[-1](x)) = x, identically. (Compare this with the g.f. given above, and see the Pari and Mathematica programs below.)

a(n) = b(n+1)/(n+1), for n >= 0, where b(n+1) is the coefficient of x^n of (1 + x^2 + x^3)^(n+1). This follows from the Lagrange inversion series for G(x) = F^[-1](x)/x.

a(n) = (1/(n+1))*(Sum_{2*e2 + 3*e3 = n} (n+1)!/(n+1 - (e2 + e3))!*e2!*e3!) (from the multinomial formula for (x1 + x2 + x3)^(n+1)). For the solutions of 2*e2 + 3*e3 = n see the array A321201.

(End)

Extensions

More terms from Christian G. Bower, Dec 15 1999