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
Seiichi Manyama, Table of n, a(n) for n = 0..653 (terms 0..250 from Alois P. Heinz)
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 18
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
T. Mansour, Restricted permutations by patterns of type 2-1, arXiv:math/0202219 [math.CO], 2002.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and J. Int. Seq. 17 (2014) #14.1.1.
F. L. Miksa, L. Moser and M. Wyman, Restricted partitions of finite sets, Canad. Math. Bull., 1 (1958), 87-96.
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):
seq(a(n), n=0..30); # Alois P. Heinz, Apr 20 2012
# 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
N. J. A. Sloane. More terms added May 13 2009.
STATUS
approved