|
|
A001681
|
|
The partition function G(n,4).
(Formerly M1481 N0584)
|
|
11
|
|
|
1, 1, 2, 5, 15, 51, 196, 827, 3795, 18755, 99146, 556711, 3305017, 20655285, 135399720, 927973061, 6631556521, 49294051497, 380306658250, 3039453750685, 25120541332271, 214363100120051, 1885987611214092, 17085579637664715, 159185637725413675
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of '12-3 and 321-4'-avoiding permutations.
Set partitions into sets of size at most 4. The e.g.f. for partitions into sets of size at most s is exp( sum(j=1..s, x^j/j!) ). [Joerg Arndt, Dec 07 2012]
Also called restricted Stirling numbers of the second kind (see Mezo). - N. J. A. Sloane, Nov 27 2013
|
|
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
|
E.g.f.: exp( x + x^2/2 + x^3/6 + x^4/24 ). - Ralf Stephan, Apr 22 2004
a(n) = n! * sum(k=1..n, 1/k! * sum(j=0..k, C(k,j) * sum(i=j..n-k+j, C(j,i-j) * C(k-j,n-3*k+3*j-i) * 2^(5*k-4*j+i-2*n) * 3^(j-k)))). [Vladimir Kruchinin, Jan 25 2011]
a(n) = G(n,4) with G(0,i) = 1, G(n,i) = 0 for n>0 and i<1, otherwise G(n,i) = Sum_{j=0..floor(n/i)} G(n-i*j,i-1) * n!/(i!^j*(n-i*j)!*j!). - Alois P. Heinz, Apr 20 2012
Recurrence: 6*a(n) = 6*a(n-1) + 6*(n-1)*a(n-2) + 3*(n-2)*(n-1)*a(n-3) + (n-3)*(n-2)*(n-1)*a(n-4). - Vaclav Kotesovec, Sep 15 2013
a(n) ~ n^(3*n/4)*exp(31*(6*n)^(1/4)/64 + 5*sqrt(6*n)/16 + (6*n)^(3/4)/6 - 3*n/4 - 21/32)/(2*6^(n/4)) * (1 + 1599*6^(3/4)/(40960*n^(1/4)) + 280873603/1677721600*sqrt(6/n) + 33870741297579 /240518168576000 *6^(1/4)/n^(3/4)). - Vaclav Kotesovec, Sep 15 2013
|
|
MAPLE
|
G:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(G(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))
end:
a:= n-> G(n, 4):
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
a(n-i)*binomial(n-1, i-1), i=1..min(n, 4)))
end:
# Recurrence:
rec := {(-n^3-6*n^2-11*n-6)*f(n) + (-3*n^2-15*n-18)*f(n+1) + (-6*n-18)*f(n+2) - 6*f(n+3) + 6*f(n+4)=0, f(0)=1, f(1)=1, f(2)=2, f(3)=5}:
aList := gfun:-rectoproc(rec, f(n), list): aList(24); # Peter Luschny, Feb 26 2018
|
|
MATHEMATICA
|
g[n_, k_] := g[n, k] = If[n == 0, 1, If[k<1, 0, Sum[g[n-k*j, k-1]*n!/k!^j/(n-k*j)!/j!, {j, 0, n/k}]]]; Table[g[n, 4], {n, 0, 24}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)
|
|
PROG
|
(PARI) A001681(n)=n!*sum(k=1, n, 1/k!*sum(j=0, k, binomial(k, j)*sum(i=j, n-k+j, binomial(j, i-j)*binomial(k-j, n-3*k+3*j-i)*2^(5*k-4*j+i-2*n)*3^(j-k))));
(PARI) x='x+O('x^66); Vec(serlaplace(exp(sum(j=1, 4, x^j/j!)))) \\ Joerg Arndt, Mar 11 2014
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|