login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001680 The partition function G(n,3).
(Formerly M1465 N0579)
15
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 (list; graph; refs; listen; history; text; internal format)
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

Alois P. Heinz, Table of n, a(n) for n = 0..250

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.

I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013.

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

Conjecture: 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 conjecture: 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

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

Cf. A001681, A189886.

Column k=3 of A229223.

Sequence in context: A240615 A240616 A240617 * A275424 A107268 A231211

Adjacent sequences:  A001677 A001678 A001679 * A001681 A001682 A001683

KEYWORD

nonn

AUTHOR

N. J. A. Sloane. More terms added May 13 2009.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 23 14:53 EDT 2017. Contains 289688 sequences.