cp's OEIS Frontend

A001680 The partition function G(n,3).

%I A001680 M1465 N0579 #86 Jul 08 2025 00:15:01
%S A001680 1,1,2,5,14,46,166,652,2780,12644,61136,312676,1680592,9467680,
%T A001680 55704104,341185496,2170853456,14314313872,97620050080,687418278544,
%U A001680 4989946902176,37286121988256,286432845428192,2259405263572480,18280749571449664,151561941235370176
%N A001680 The partition function G(n,3).
%C A001680 Number of '12-3 and 21-3'-avoiding permutations.
%C A001680 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 A001680 Also called restricted Stirling numbers of the second kind (see Mezo). - _N. J. A. Sloane_, Nov 27 2013
%D A001680 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001680 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001680 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 A001680 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 A001680 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 A001680 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 A001680 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 A001680 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 A001680 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=18">Encyclopedia of Combinatorial Structures 18</a>
%H A001680 Vladimir Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%H A001680 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 A001680 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 A001680 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 A001680 E.g.f.: exp ( x + x^2 / 2 + x^3 / 6 ).
%F A001680 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 A001680 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 A001680 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 A001680 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 A001680 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 A001680 G:= proc(n, i) option remember;
%p A001680       `if`(n=0, 1, `if`(i<1, 0,
%p A001680        add(G(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))
%p A001680     end:
%p A001680 a:= n-> G(n, 3):
%p A001680 seq(a(n), n=0..30); # _Alois P. Heinz_, Apr 20 2012
%p A001680 # Recurrence:
%p A001680 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 A001680 aList := gfun:-rectoproc(rec,f(n),list): aList(25); # _Peter Luschny_, Feb 26 2018
%t A001680 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 A001680 Cf. A001681, A189886.
%Y A001680 Column k=3 of A229223.
%K A001680 nonn
%O A001680 0,3
%A A001680 _N. J. A. Sloane_
%E A001680 More terms added May 13 2009