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

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001681 The partition function G(n,4).
(Formerly M1481 N0584)
9
1, 1, 2, 5, 15, 51, 196, 827, 3795, 18755, 99146, 556711, 3305017, 20655285, 135399720, 927973061, 6631556521, 49294051497, 380306658250, 3039453750685, 25120541332271, 214363100120051, 1885987611214092, 17085579637664715, 159185637725413675 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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]

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..200

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394, 2017.

David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 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, 2012.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 19

Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565

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, 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 + x^4/24 ). - Ralf Stephan, Apr 22 2004

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)))). [From  Vladimir Kruchinin, Jan 25 2011]

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

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

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

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, 4):

seq(a(n), n=0..30);  # Alois P. Heinz, Apr 20 2012

# second Maple program:

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

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

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Sep 22 2016

MATHEMATICA

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 *)

PROG

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

vector(33, n, A001681(n-1)) /* Joerg Arndt, Jan 25 2011 */

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

CROSSREFS

Cf. A001680, A276924.

Column k=4 of A229223.

Sequence in context: A287253 A117426 A201168 * A192553 A053553 A276721

Adjacent sequences:  A001678 A001679 A001680 * A001682 A001683 A001684

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Ralf Stephan, Apr 22 2004

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 May 29 06:46 EDT 2017. Contains 287243 sequences.