cp's OEIS Frontend

A001681 The partition function G(n,4).

%I A001681 M1481 N0584 #74 Feb 26 2018 09:03:51
%S A001681 1,1,2,5,15,51,196,827,3795,18755,99146,556711,3305017,20655285,
%T A001681 135399720,927973061,6631556521,49294051497,380306658250,
%U A001681 3039453750685,25120541332271,214363100120051,1885987611214092,17085579637664715,159185637725413675
%N A001681 The partition function G(n,4).
%C A001681 Number of '12-3 and 321-4'-avoiding permutations.
%C A001681 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 A001681 Also called restricted Stirling numbers of the second kind (see Mezo). - _N. J. A. Sloane_, Nov 27 2013
%D A001681 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001681 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001681 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 A001681 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 A001681 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 A001681 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 A001681 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 A001681 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=19">Encyclopedia of Combinatorial Structures 19</a>
%H A001681 Vladimir Victorovich Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%H A001681 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 A001681 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 A001681 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 A001681 E.g.f.: exp( x + x^2/2 + x^3/6 + x^4/24 ). - _Ralf Stephan_, Apr 22 2004
%F A001681 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 A001681 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 A001681 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 A001681 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 A001681 G:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A001681        add(G(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))
%p A001681     end:
%p A001681 a:= n-> G(n, 4):
%p A001681 seq(a(n), n=0..30);  # _Alois P. Heinz_, Apr 20 2012
%p A001681 # second Maple program:
%p A001681 a:= proc(n) option remember; `if`(n=0, 1, add(
%p A001681        a(n-i)*binomial(n-1, i-1), i=1..min(n, 4)))
%p A001681     end:
%p A001681 seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 22 2016
%p A001681 # Recurrence:
%p A001681 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 A001681 aList := gfun:-rectoproc(rec, f(n), list): aList(24); # _Peter Luschny_, Feb 26 2018
%t A001681 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 A001681 (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 A001681 vector(33,n,A001681(n-1)) /* _Joerg Arndt_, Jan 25 2011 */
%o A001681 (PARI) x='x+O('x^66); Vec(serlaplace(exp(sum(j=1,4,x^j/j!)))) \\ _Joerg Arndt_, Mar 11 2014
%Y A001681 Cf. A001680, A276924.
%Y A001681 Column k=4 of A229223.
%K A001681 nonn,easy
%O A001681 0,3
%A A001681 _N. J. A. Sloane_
%E A001681 More terms from _Ralf Stephan_, Apr 22 2004