|
| |
|
|
A000296
|
|
Number of partitions of an n-set into blocks of size >1. Also number of cyclically spaced (or feasible) partitions.
(Formerly M3423 N1387)
|
|
42
|
|
|
|
1, 0, 1, 1, 4, 11, 41, 162, 715, 3425, 17722, 98253, 580317, 3633280, 24011157, 166888165, 1216070380, 9264071767, 73600798037, 608476008122, 5224266196935, 46499892038437, 428369924118314, 4078345814329009
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
a(n+2)=p(n+1) where p(x) is the unique degree-n polynomial such that p(k)=A000110(n) for k=0,1,...,n. - Michael Somos, Oct 07 2003
Number of complete rhyming schemes.
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
Row sums of the triangle of associated Stirling numbers of second kind A008299 . - Philippe Deléham, Feb 10 2005
Row sums of the triangle of basic multinomial coefficients A178866. [From Johannes W. Meijer, June 21, 2010]
a(n) = 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
|
|
|
REFERENCES
|
E. Bach, Random bisection and evolutionary walks, J. Applied Probability, v. 38, pp. 582-596, 2001.
H. D. Becker, Solution to problem E 461, American Math Monthly 48 (1941), 701-702.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
Eva Czabarka, Peter L. Erdos, Virginia Johnson, Anne Kupczok and Laszlo A. Szekely, Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons, Arxiv preprint arXiv:1108.6015, 2011
E. A. Enneking and J. C. Ahuja, Generalized Bell numbers, Fib. Quart., 14 (1976), 67-73.
Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, Arxiv preprint arXiv:1104.4323, 2011.
Martin Gardner in Sci. Amer. May 1977.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011; http://repository.wit.ie/1693/1/AoifeThesis.pdf
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012; http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf. - From ~~~
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 436).
E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411, 2013
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 228.
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.
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
|
T. D. Noe, Table of n, a(n) for n=0..100
S. R. Finch, Moments of sums
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 16
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Peter Luschny, Set partitions
Toufik Mansour and Mark Shattuck, A recurrence related to the Bell numbers, INTEGERS 11 (2011), #A67.
Tilman Piesk, Table showing non-singleton partitions for n=1...6
J. Riordan, Cached copy of paper
Index entries for related partition-counting sequences
|
|
|
FORMULA
|
E.g.f.: exp(exp(x) - 1 - x).
B(n) = a(n) + a(n+1), where B = A000110 = Bell numbers [Becker]
Inverse binomial transform of Bell numbers (A000110).
a(n)= sum((k)^n/(k+1)!, k = -1 .. infinity)/exp(1). - Vladeta Jovovic and Karol A. Penson, Feb 02 2003
a(n)= sum(((-1)^(n-k))*binomial(n, k)*Bell(k), k=0..n) = (-1)^n + Bell(n) - A087650(n), with Bell(n)=A000110(n). Wolfdieter Lang, Dec 01 2003
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
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
a(n)=(-1)^n + sum[(-1)^(j-1)*B(n-j),j=1..n], where B(q) are the Bell numbers (A000110). - Emeric Deutsch, Oct 29 2006
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]
G.f.: (2/E(0) - 1)/x where E(k)= 1 + 1/(1 + 2*x/(1 - 2*(k+1)*x/E(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 20 2012
G.f.: 1/U(0) where U(k)= 1 - x*k - x^2*(k+1)/U(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Oct 11 2012
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) )); (continued fraction). - Sergei N. Gladkovskii, Dec 19 2012
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1+x-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013
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)))); (continued fraction). - Sergei N. Gladkovskii, May 13 2013
G.f.: 1/(x*Q(0)), where Q(k)= 1 + 1/(x + x^2/(1 - x - (k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 13 2013
|
|
|
EXAMPLE
|
For n = 4 the a(4)=card({{{1,2},{3,4}},{{1,4},{2,3}},{{1,3},{2,4}},{{1,2,3,4}}})=4.
|
|
|
MAPLE
|
spec := [ B, {B=Set(Set(Z, card>1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..30)];
with(combinat): a:=n->(-1)^n+sum((-1)^(j-1)*bell(n-j), j=1..n): seq(a(n), n=0..30); # Emeric Deutsch, Oct 29 2006
f:=exp(exp(x)-1-x): fser:=series(f, x=0, 31): 1, seq(n!*coeff(fser, x^n), n=1..23); # Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Nov 22 2006
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 (zerinvarylajos(AT)yahoo.com), Dec 16 2007
# [a(0), a(1), .., a(n)]
A000296_list := proc(n)
local A, R, i, k;
if n = 0 then RETURN(1) fi;
A := array(0..n-1);
A[0] := 1; R := 1;
for i from 0 to n-2 do
A[i+1] := A[0] - A[i];
A[i] := A[0];
for k from i by -1 to 1 do
A[k-1] := A[k-1] + A[k] od;
R := R, A[i+1];
od;
R, A[0]-A[i] end:
A000296_list(100); # Peter Luschny, Apr 9 2011
|
|
|
MATHEMATICA
|
nn = 25; Range[0, nn]! CoefficientList[Series[Exp[Exp[x] - 1 - x], {x, 0, nn}], x]
|
|
|
PROG
|
(PARI) a(n) = if(n<2, n==0, subst( polinterpolate( Vec( serlaplace( exp( exp( x+O(x^n)/x )-1 ) ) ) ), x, n) )
|
|
|
CROSSREFS
|
Cf. A000110, A005493, A006505, A057814, A057837, A105794.
Sequence in context: A214167 A214188 A214239 * A032265 A151273 A149271
Adjacent sequences: A000293 A000294 A000295 * A000297 A000298 A000299
|
|
|
KEYWORD
|
nonn,easy,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms, new description from Christian G. Bower, Nov 15 1999.
Becker reference from D. E. Knuth, Dec 20 2003
|
|
|
STATUS
|
approved
|
| |
|
|
