|
%I M3423 N1387 #322 Feb 13 2024 10:52:38
%S 1,0,1,1,4,11,41,162,715,3425,17722,98253,580317,3633280,24011157,
%T 166888165,1216070380,9264071767,73600798037,608476008122,
%U 5224266196935,46499892038437,428369924118314,4078345814329009,40073660040755337,405885209254049952,4232705122975949401
%N Set partitions without singletons: number of partitions of an n-set into blocks of size > 1. Also number of cyclically spaced (or feasible) partitions.
%C a(n+2) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A000110(k) for k = 0, 1, ..., n. - _Michael Somos_, Oct 07 2003
%C Number of complete rhyming schemes.
%C Whereas the Bell number B(n) (A000110(n)) is the number of terms in the polynomial that expresses the n-th moment of a probability distribution as a function of the first n cumulants, these numbers give the number of terms in the corresponding expansion of the _central_ moment as a function of the first n cumulants. - Michael Hardy (hardy(AT)math.umn.edu), Jan 26 2005
%C a(n) is the number of permutations on [n] for which the left-to-right maxima coincide with the descents (entries followed by a smaller number). For example, a(4) counts 2143, 3142, 3241, 4123. - _David Callan_, Jul 20 2005
%C From _Gus Wiseman_, Feb 10 2019: (Start)
%C Also the number of stable partitions of an n-cycle, where a stable partition of a graph is a set partition of the vertex set such that no edge has both ends in the same block. A bijective proof is given in David Callan's article. For example, the a(5) = 11 stable partitions are:
%C {{1},{2},{3},{4},{5}}
%C {{1},{2},{3,5},{4}}
%C {{1},{2,4},{3},{5}}
%C {{1},{2,5},{3},{4}}
%C {{1,3},{2},{4},{5}}
%C {{1,4},{2},{3},{5}}
%C {{1},{2,4},{3,5}}
%C {{1,3},{2,4},{5}}
%C {{1,3},{2,5},{4}}
%C {{1,4},{2},{3,5}}
%C {{1,4},{2,5},{3}}
%C (End)
%C Also number of partitions of {1, 2, ..., n-1} with singletons. E.g., a(4) = 4: {1|2|3, 12|3, 13|2, 1|23}. Also number of cyclical adjacencies partitions of {1, 2, ..., n-1}. E.g., a(4) = 4: {12|3, 13|2, 1|23, 123}. The two partitions can be mapped by a Kreweras bijection. - _Yuchun Ji_, Feb 22 2021
%C Also the k-th central moment of a Poisson random variable with mean 1. a(n) = E[(X-1)^n, X~Poisson(1)]. - _Thomas Dybdahl Ahle_, Dec 14 2022
%D Martin Gardner in Sci. Amer. May 1977.
%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 436).
%D G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 228.
%D Reidenbach, Daniel, and Johannes C. Schneider. "Morphically primitive words." (2009). See Table 1. Available from https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4561/1/Reidenbach_Schneider_TCS_Morphically_primitive_words_Final_version.pdf [Do not delete this reference, because I do not know if the similar link below (which does not seem to work) refers to an identical version of the article. - _N. J. A. Sloane_, Jul 14 2018]
%D J. Riordan, A budget of rhyme scheme counts, pp. 455-465 of Second International Conference on Combinatorial Mathematics, New York, April 4-7, 1978. Edited by Allan Gewirtz and Louis V. Quintas. Annals New York Academy of Sciences, 319, 1979.
%D J. Shallit, A Triangle for the Bell numbers, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.
%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 Alois P. Heinz, <a href="/A000296/b000296.txt">Table of n, a(n) for n = 0..575</a> (first 101 terms from T. D. Noe)
%H Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>.
%H E. Bach, <a href="http://www.jstor.org/stable/3215908">Random bisection and evolutionary walks</a>, J. Applied Probability, v. 38, pp. 582-596, 2001.
%H M. Bauer and O. Golinelli, <a href="http://arxiv.org/abs/cond-mat/0007127">Random incidence matrices: Moments of the spectral density</a>, arXiv:cond-mat/0007127 [cond-mat.stat-mech], 2000-2001. See Sect. 3.2; J. Stat. Phys. 103, 301-307 (2001).
%H H. D. Becker, <a href="http://www.jstor.org/stable/2303322">Solution to problem E 461</a>, American Math Monthly 48 (1941), 701-702.
%H F. R. Bernhart, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discr. Math., 204 (1999) 73-112.
%H F. R. Bernhart, <a href="/A000296/a000296_1.pdf">Fundamental chromatic numbers</a>, Unpublished. (Annotated scanned copy)
%H F. R. Bernhart & N. J. A. Sloane, <a href="/A001683/a001683.pdf">Correspondence, 1977</a>.
%H J. R. Britnell and M. Wildon, <a href="http://arxiv.org/abs/1507.04803">Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D</a>, arXiv 1507.04803 [math.CO], 2015.
%H David Callan, <a href="https://arxiv.org/abs/math/0508052">On conjugates for set partitions and integer compositions</a> [math.CO].
%H Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot, and Bruno Patrou, <a href="http://arxiv.org/abs/1505.03474">State complexity of catenation combined with a boolean operation: a unified approach</a>, arXiv preprint arXiv:1505.03474 [cs.FL], 2015.
%H Robert Coquereaux and Jean-Bernard Zuber, <a href="https://arxiv.org/abs/2305.01100">Counting partitions by genus. II. A compendium of results</a>, arXiv:2305.01100 [math.CO], 2023. See p. 3.
%H Éva Czabarka, Péter L. Erdős, Virginia Johnson, Anne Kupczok and László A. Székely, <a href="http://arxiv.org/abs/1108.6015">Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons</a>, arXiv preprint arXiv:1108.6015 [math.CO], 2011.
%H Gesualdo Delfino and Jacopo Viti, <a href="http://arxiv.org/abs/1104.4323">Potts q-color field theory and scaling random cluster model</a>, arXiv preprint arXiv:1104.4323 [hep-th], 2011.
%H E. A. Enneking and J. C. Ahuja, <a href="http://www.fq.math.ca/Scanned/14-1/enneking.pdf">Generalized Bell numbers</a>, Fib. Quart., 14 (1976), 67-73.
%H Steven R. Finch, <a href="/A000296/a000296.pdf">Moments of sums</a>, April 23, 2004. [Cached copy, with permission of the author]
%H Robert C. Griffiths, P. A. Jenkins, and S. Lessard, <a href="https://arxiv.org/abs/1604.04145">A coalescent dual process for a Wright-Fisher diffusion with recombination and its application to haplotype partitioning</a>, arXiv preprint arXiv:1604.04145 [q-bio.PE], 2016.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=16">Encyclopedia of Combinatorial Structures 16</a>.
%H V. P. Johnson, <a href="http://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H Peter Luschny, <a href="https://oeis.org/wiki/User:Peter_Luschny/SetPartitions">Set partitions</a>.
%H Gregorio Malajovich, <a href="https://arxiv.org/abs/1606.03410">Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric</a>, arXiv preprint arXiv:1606.03410 [math.NA], 2016.
%H Toufik Mansour and Mark Shattuck, <a href="http://www.emis.de/journals/INTEGERS/papers/l67/l67.Abstract.html">A recurrence related to the Bell numbers</a>, INTEGERS 11 (2011), #A67.
%H T. Mansour and A. O. Munagi, <a href="http://dx.doi.org/10.1016/j.ejc.2014.06.008">Set partitions with circular successions</a>, European Journal of Combinatorics, 42 (2014), 207-216.
%H I. Mezo, <a href="http://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">Periodicity of the last digits of some combinatorial sequences</a>, J. Integer Seq. 17, Article 14.1.1, 2014.
%H Scott Morrison, Noah Snyder, and Dylan P. Thurston, <a href="https://arxiv.org/abs/2402.03637">Towards the quantum exceptional series</a>, arXiv:2402.03637 [math.QA], 2024. See p. 39.
%H E. Norton, <a href="http://arxiv.org/abs/1302.5411">Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions</a>, arXiv preprint arXiv:1302.5411 [math.RA], 2013.
%H Aleksandar Petojević, Marjana Gorjanac Ranitović, and Milinko Mandić, <a href="https://www.researchgate.net/publication/368535673_New_equivalents_for_Kurepa%27s_hypothesis_for_left_factorial">New equivalents for Kurepa's hypothesis for left factorial</a>, Univ. Novi Sad (2023).
%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:Set_partitions_with_no_singletons_until_place_n.svg">Table showing non-singleton partitions for n = 1..6</a>.
%H R. A. Proctor, <a href="https://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way for Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2006-2007.
%H Jocelyn Quaintance and Harris Kwong, <a href="http://www.emis.de/journals/INTEGERS/papers/n29/n29.Abstract.html">A combinatorial interpretation of the Catalan and Bell number difference tables</a>, Integers, 13 (2013), #A29.
%H Daniel Reidenbach and Johannes C. Schneider, <a href="https://repository.lboro.ac.uk/articles/Morphically_primitive_words/9402479">Morphically primitive words</a>, (2009). See Table 1.
%H Daniel Reidenbach and Johannes C. Schneider, <a href="https://doi.org/10.1016/j.tcs.2009.01.020">Morphically primitive words</a>, Theoretical Computer Science, (2009), 140 (21-23), pp. 2148-2161.
%H J. Riordan, <a href="/A005000/a005000.pdf">Cached copy of paper</a>.
%H Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/shallit-bell-triangle.pdf">A Triangle for the Bell numbers</a>, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.
%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%F E.g.f.: exp(exp(x) - 1 - x).
%F B(n) = a(n) + a(n+1), where B = A000110 = Bell numbers [Becker].
%F Inverse binomial transform of Bell numbers (A000110).
%F a(n)= Sum_{k>=-1} (k^n/(k+1)!)/exp(1). - _Vladeta Jovovic_ and _Karol A. Penson_, Feb 02 2003
%F a(n) = Sum_{k=0..n} ((-1)^(n-k))*binomial(n, k)*Bell(k) = (-1)^n + Bell(n) - A087650(n), with Bell(n) = A000110(n). - _Wolfdieter Lang_, Dec 01 2003
%F O.g.f.: A(x) = 1/(1-0*x-1*x^2/(1-1*x-2*x^2/(1-2*x-3*x^2/(1-... -(n-1)*x-n*x^2/(1- ...))))) (continued fraction). - _Paul D. Hanna_, Jan 17 2006
%F a(n) = Sum_{k = 0..n} {(-1)^(n-k) * Sum_{j = 0..k}((-1)^j * binomial(k,j) * (1-j)^n)/ k!} = sum over row n of A105794. - _Tom Copeland_, Jun 05 2006
%F a(n) = (-1)^n + Sum_{j=1..n} (-1)^(j-1)*B(n-j), where B(q) are the Bell numbers (A000110). - _Emeric Deutsch_, Oct 29 2006
%F Let A be the upper Hessenberg matrix of order n defined by: A[i, i-1] = -1, A[i,j] = binomial(j-1, i-1), (i <= j), and A[i, j] = 0 otherwise. Then, for n >= 2, a(n) = (-1)^(n)charpoly(A,1). - _Milan Janjic_, Jul 08 2010
%F From _Sergei N. Gladkovskii_, Sep 20 2012, Oct 11 2012, Dec 19 2012, Jan 15 2013, May 13 2013, Jul 20 2013, Oct 19 2013, Jan 25 2014: (Start)
%F Continued fractions:
%F G.f.: (2/E(0) - 1)/x where E(k) = 1 + 1/(1 + 2*x/(1 - 2*(k+1)*x/E(k+1))).
%F G.f.: 1/U(0) where U(k) = 1 - x*k - x^2*(k+1)/U(k+1).
%F G.f.: G(0)/(1+2*x) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-x-1) - x*(2*k+1)*(2*k+3)*(2*x*k-x-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k-1)/G(k+1))).
%F G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1+x-k*x)/(1-x/(x-1/G(k+1))).
%F G.f.: 1 + x^2/(1+x)/Q(0) where Q(k) = 1-x-x/(1-x*(2*k+1)/(1-x-x/(1-x*(2*k+2)/Q(k+1)))).
%F G.f.: 1/(x*Q(0)) where Q(k) = 1 + 1/(x + x^2/(1 - x - (k+1)/Q(k+1))).
%F G.f.: -(1+(2*x+1)/G(0))/x where G(k) = x*k - x - 1 - (k+1)*x^2/G(k+1).
%F G.f.: T(0) where T(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x*k)*(1-x-x*k)/T(k+1)).
%F G.f.: (1+x*Sum_{k>=0} x^k/Product_{p=0..k}(1-p*x)/(1+x). (End)
%F a(n) = Sum_{i=1..n-1} binomial(n-1,i)*a(n-i-1), a(0)=1. - _Vladimir Kruchinin_, Feb 22 2015
%F G.f. A(x) satisfies: A(x) = (1/(1 + x)) * (1 + x * A(x/(1 - x)) / (1 - x)). - _Ilya Gutkovskiy_, May 21 2021
%F a(n) ~ exp(n/LambertW(n) - n - 1) * n^(n-1) / (sqrt(1 + LambertW(n)) * LambertW(n)^(n-1)). - _Vaclav Kotesovec_, Jun 28 2022
%e a(4) = card({{{1, 2}, {3, 4}}, {{1, 4}, {2, 3}}, {{1, 3}, {2, 4}}, {{1, 2, 3, 4}}}) = 4.
%p spec := [ B, {B=Set(Set(Z,card>1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..30)];
%p with(combinat): A000296 :=n->(-1)^n + add((-1)^(j-1)*bell(n-j),j=1..n): seq(A000295(n),n=0..30); # _Emeric Deutsch_, Oct 29 2006
%p f:=exp(exp(x)-1-x): fser:=series(f, x=0, 31): 1, seq(n!*coeff(fser, x^n), n=1..23); # _Zerinvary Lajos_, Nov 22 2006
%p G:={P=Set(Set(Atom,card>=2))}: combstruct[gfsolve](G,unlabeled,x): seq(combstruct[count]([P,G,labeled], size=i), i=0..23); # _Zerinvary Lajos_, Dec 16 2007
%p # [a(0),a(1),..,a(n)]
%p A000296_list := proc(n)
%p local A, R, i, k;
%p if n = 0 then RETURN(1) fi;
%p A := array(0..n-1);
%p A[0] := 1; R := 1;
%p for i from 0 to n-2 do
%p A[i+1] := A[0] - A[i];
%p A[i] := A[0];
%p for k from i by -1 to 1 do
%p A[k-1] := A[k-1] + A[k] od;
%p R := R,A[i+1];
%p od;
%p R,A[0]-A[i] end:
%p A000296_list(100); # _Peter Luschny_, Apr 09 2011
%t nn = 25; Range[0, nn]! CoefficientList[Series[Exp[Exp[x] - 1 - x], {x, 0, nn}], x]
%t (* Second program: *)
%t a[n_] := a[n] = If[n==0, 1, Sum[Binomial[n-1, i]*a[n-i-1], {i, 1, n-1}]]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Feb 06 2016, after _Vladimir Kruchinin_ *)
%t spsu[_,{}]:={{}};spsu[foo_,set:{i_,___}]:= Join@@Function[s,Prepend[#,s]&/@spsu[ Select[foo,Complement[#, Complement[set,s]]=={}&], Complement[set,s]]]/@Cases[foo,{i,___}];
%t Table[Length[spsu[Select[Subsets[Range[n]],Select[Partition[Range[n],2,1,1], Function[ed,Complement[ed,#]=={}]]=={}&],Range[n]]],{n,8}] (* _Gus Wiseman_, Feb 10 2019 *)
%t s = 1; Join[{1}, Table[s = BellB[n] - s, {n, 0, 25}]] (* _Vaclav Kotesovec_, Jun 20 2022 *)
%o (PARI) a(n) = if(n<2, n==0, subst( polinterpolate( Vec( serlaplace( exp( exp( x+O(x^n)/x )-1 ) ) ) ), x, n) )
%o (Maxima)
%o a(n):=if n=0 then 1 else sum(binomial(n-1,i)*a(n-i-1),i,1,n-1); /* _Vladimir Kruchinin_, Feb 22 2015 */
%o (Magma) [1,0] cat [ n le 1 select 1 else Bell(n)-Self(n-1) : n in [1..40]]; // _Vincenzo Librandi_, Jun 22 2015
%o (Python)
%o from itertools import accumulate, islice
%o def A000296_gen():
%o yield from (1,0)
%o blist, a, b = (1,), 0, 1
%o while True:
%o blist = list(accumulate(blist, initial = (b:=blist[-1])))
%o yield (a := b-a)
%o A000296_list = list(islice(A000296_gen(),20)) # _Chai Wah Wu_, Jun 22 2022
%Y Cf. A000110, A005493, A006505, A057814, A057837.
%Y A diagonal of triangle in A106436.
%Y Row sums of the triangle of associated Stirling numbers of second kind A008299. - _Philippe Deléham_, Feb 10 2005
%Y Row sums of the triangle of basic multinomial coefficients A178866. - _Johannes W. Meijer_, Jun 21 2010
%Y Row sums of A105794. - _Peter Bala_, Jan 14 2015
%Y Row sums of A261139, main diagonal of A261137.
%Y Column k=0 of A216963.
%Y Column k=0 of A124323.
%Y Cf. A000126, A001610, A066982, A169985, A240936.
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_
%E More terms, new description from _Christian G. Bower_, Nov 15 1999
%E a(23) corrected by _Sean A. Irvine_, Jun 22 2015
|
