%I M1481 N0584 #74 Feb 26 2018 09:03:51

%S 1,1,2,5,15,51,196,827,3795,18755,99146,556711,3305017,20655285,

%T 135399720,927973061,6631556521,49294051497,380306658250,

%U 3039453750685,25120541332271,214363100120051,1885987611214092,17085579637664715,159185637725413675

%N The partition function G(n,4).

%C Number of '12-3 and 321-4'-avoiding permutations.

%C 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]

%C Also called restricted Stirling numbers of the second kind (see Mezo). - _N. J. A. Sloane_, Nov 27 2013

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Seiichi Manyama, <a href="/A001681/b001681.txt">Table of n, a(n) for n = 0..609</a> (terms 0..200 from Alois P. Heinz)

%H Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1701.08394">Analysis of the Gift Exchange Problem</a>, arXiv:1701.08394 [math.CO], 2017.

%H David Applegate and N. J. A. Sloane, <a href="http://arxiv.org/abs/0907.0513">The Gift Exchange Problem</a>, arXiv:0907.0513 [math.CO], 2009.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1210.6908">Some instances of a sub-permutation problem on pattern avoiding permutations</a>, arXiv preprint arXiv:1210.6908 [math.CO], 2012.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=19">Encyclopedia of Combinatorial Structures 19</a>

%H Vladimir Victorovich Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.

%H T. Mansour, <a href="https://arxiv.org/abs/math/0202219">Restricted permutations by patterns of type 2-1</a>, arXiv:math/0202219 [math.CO], 2002.

%H I. Mezo, <a href="http://arxiv.org/abs/1308.1637">Periodicity of the last digits of some combinatorial sequences</a>, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">J. Int. Seq. 17 (2014) #14.1.1</a> .

%H F. L. Miksa, L. Moser and M. Wyman, <a href="http://dx.doi.org/10.4153/CMB-1958-010-2">Restricted partitions of finite sets</a>, Canad. Math. Bull., 1 (1958), 87-96.

%F E.g.f.: exp( x + x^2/2 + x^3/6 + x^4/24 ). - _Ralf Stephan_, Apr 22 2004

%F 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]

%F 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

%F 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

%F 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

%p G:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(G(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))

%p end:

%p a:= n-> G(n, 4):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Apr 20 2012

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 1, add(

%p a(n-i)*binomial(n-1, i-1), i=1..min(n, 4)))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 22 2016

%p # Recurrence:

%p 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}:

%p aList := gfun:-rectoproc(rec, f(n), list): aList(24); # _Peter Luschny_, Feb 26 2018

%t 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_ *)

%o (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))));

%o vector(33,n,A001681(n-1)) /* _Joerg Arndt_, Jan 25 2011 */

%o (PARI) x='x+O('x^66); Vec(serlaplace(exp(sum(j=1,4,x^j/j!)))) \\ _Joerg Arndt_, Mar 11 2014

%Y Cf. A001680, A276924.

%Y Column k=4 of A229223.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Ralf Stephan_, Apr 22 2004