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
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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

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

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.

L. Smiley, a(7) and a(8)

Index entries for sequences related to rooted trees

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(((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

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)

EXAMPLE

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)

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

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

PROG

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

CROSSREFS

Cf. A321201.

Sequence in context: A117647 A121568 A276464 * A009735 A177245 A283511

Adjacent sequences:  A001002 A001003 A001004 * A001006 A001007 A001008

KEYWORD

nonn,eigen

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Christian G. Bower, Dec 15 1999

STATUS

approved

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 19 13:01 EDT 2019. Contains 328222 sequences. (Running on oeis4.)