|
|
A001680
|
|
The partition function G(n,3).
(Formerly M1465 N0579)
|
|
21
|
|
|
1, 1, 2, 5, 14, 46, 166, 652, 2780, 12644, 61136, 312676, 1680592, 9467680, 55704104, 341185496, 2170853456, 14314313872, 97620050080, 687418278544, 4989946902176, 37286121988256, 286432845428192, 2259405263572480, 18280749571449664, 151561941235370176
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of '12-3 and 21-3'-avoiding permutations.
Set partitions into sets of size at most 3. 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 ).
a(n) = n! * sum(k=1..n, 1/k! * sum(j=0..k, C(k,j) * C(j,n-3*k+2*j) * 2^(-n+2*k-j) * 3^(j-k))). [Vladimir Kruchinin, Jan 25 2011]
a(n) = G(n,3) 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
D-finite with recurrence 2*a(n) -2*a(n-1) +2*(-n+1)*a(n-2) -(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Jan 25 2013
Proof of foregoing recurrence: The partition containing n can be a singleton (a(n-1) partitions of the remaining terms), a doubleton ((n-1) choices for its companion times a(n-2) partitions of the remaining terms) or a tripleton ((n-1) choose 2 choices for its companions times a(n-3) partitions for the remaining terms), so a(n) = a(n-1) + (n-1)a(n-2) + (n-1)*(n-2)/2 * a(n-3). - Micah E. Fogel, Feb 14 2013
a(n) ~ n^(2*n/3)*exp(1/2*(2*n)^(2/3)+2/3*(2*n)^(1/3)-2*n/3-4/9)/(sqrt(3)*2^(n/3)). - Vaclav Kotesovec, May 29 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, 3):
# Recurrence:
rec := {(-n^2-3*n-2)*f(n)+(-2*n-4)*f(n+1)-2*f(n+2)+2*f(n+3)=0, f(0)=1, f(1)=1, f(2)=2}:
aList := gfun:-rectoproc(rec, f(n), list): aList(25); # Peter Luschny, Feb 26 2018
|
|
MATHEMATICA
|
Table[Sum[n!/(m!2^(n+j-2m)3^(m-j))Binomial[m, j]Binomial[j, n+2j-3m], {m, 0, n}, {j, 0, 3m-n}], {n, 0, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|