|
| |
|
|
A001005
|
|
Number of ways of partitioning n points on a circle into subsets only of sizes 2 and 3.
(Formerly M1353 N0520)
|
|
11
|
|
|
|
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
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
|
|
|
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
|
|
|
|
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
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
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, 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 *)
|
|
|
PROG
|
(PARI) Vec(serreverse(x/(1+x^2+x^3)+O(x^66))/x) /* Joerg Arndt, Aug 19 2012 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,eigen
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
