A001680 The partition function G(n,3).

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

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.

Crossrefs

Cf. A001681, A189886.

Column k=3 of A229223.

Programs

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

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

Extensions

More terms added May 13 2009