login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001005 Number of ways of partitioning n points on a circle into subsets only of sizes 2 and 3.
(Formerly M1353 N0520)
8

%I M1353 N0520

%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

%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 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 L. 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_

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 06:01 EDT 2019. Contains 328291 sequences. (Running on oeis4.)