A001005 - OEIS

%I M1353 N0520 #111 Sep 22 2023 07:13:22

%S 1,0,1,1,2,5,8,21,42,96,222,495,1177,2717,6435,15288,36374,87516,

%T 210494,509694,1237736,3014882,7370860,18059899,44379535,109298070,

%U 269766655,667224480,1653266565,4103910930,10203669285,25408828065,63364046190,158229645720,395632288590,990419552730

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

%C 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

%C 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H Vincenzo Librandi, <a href="/A001005/b001005.txt">Table of n, a(n) for n = 0..200</a>

%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.

%H F. R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>

%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=396">Encyclopedia of Combinatorial Structures 396</a>

%H T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.

%H Len Smiley, <a href="http://www.math.uaa.alaska.edu/~smiley/A001005_7_8.pdf">a(7) and a(8)</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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

%F a(n) = sum(((n)!/(k!*j!*(n-k-j+1)!)*[2*k+3*j=n], k=0..floor(n/2), j=0..floor(n/3)). - _Len Smiley_, Jun 18 2005

%F 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

%F 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

%F 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

%F From _Wolfdieter Lang_, Nov 05 2018: (Start)

%F 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.)

%F 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.

%F 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.

%F (End)

%e 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

%e From _Wolfdieter Lang_, Nov 05 2018: (Start)

%e 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.

%e 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)

%p 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

%p 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

%t 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 *)

%t CoefficientList[ InverseSeries[x/(1+x^2+x^3) + O[x]^66]/x, x] (* _Jean-François Alcover_, Feb 15 2016, after _Joerg Arndt_*)

%o (PARI) Vec(serreverse(x/(1+x^2+x^3)+O(x^66))/x) /* _Joerg Arndt_, Aug 19 2012 */

%Y Cf. A321201.

%K nonn,eigen

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_, Dec 15 1999