login
The partition function G(n,3).
(Formerly M1465 N0579)
21

%I M1465 N0579 #83 Feb 16 2020 07:58:58

%S 1,1,2,5,14,46,166,652,2780,12644,61136,312676,1680592,9467680,

%T 55704104,341185496,2170853456,14314313872,97620050080,687418278544,

%U 4989946902176,37286121988256,286432845428192,2259405263572480,18280749571449664,151561941235370176

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

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

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

%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="/A001680/b001680.txt">Table of n, a(n) for n = 0..653</a> (terms 0..250 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 R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]

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

%H Vladimir 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 ).

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

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

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

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

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

%p G:= proc(n, i) option remember;

%p `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, 3):

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

%p # Recurrence:

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

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

%t 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}]

%Y Cf. A001681, A189886.

%Y Column k=3 of A229223.

%K nonn

%O 0,3

%A _N. J. A. Sloane_. More terms added May 13 2009.