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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000296 Number of partitions of an n-set into blocks of size >1. Also number of cyclically spaced (or feasible) partitions.
(Formerly M3423 N1387)
47
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. - Johannes W. Meijer, Jun 21 2010

Row sums of A105794. - Peter Bala, Jan 14 2015

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

Martin Gardner in Sci. Amer. May 1977.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 436).

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.

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.

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

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

Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv preprint arXiv:1104.4323, 2011.

E. A. Enneking and J. C. Ahuja, Generalized Bell numbers, Fib. Quart., 14 (1976), 67-73.

S. R. Finch, Moments of sums

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.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 16

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

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.

T. Mansour, A. O. Munagi, Set partitions with circular successions, European Journal of Combinatorics, 42 (2014), 207-216.

I. Mezo, Periodicity of the last digits of some combinatorial sequences, J. Integer Seq. 17, Article 14.1.1, 2014.

E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411, 2013

Tilman Piesk, Table showing non-singleton partitions for n=1...6

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv math.CO.0606404.

Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.

J. Riordan, Cached copy of paper

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.

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

G.f.: -(1+(2*x+1)/G(0))/x, where G(k) = x*k - x - 1 - (k+1)*x^2/G(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Jul 20 2013

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) ); (continued fraction). - Sergei N. Gladkovskii, Oct 19 2013

G.f.: (1+x*sum{k>=0, x^k/prod[p=0..k, 1-p*x]})/(1+x). - Sergei N. Gladkovskii, Jan 25 2014

a(n) = sum(i=1..n-1, binomial(n-1,i)*a(n-i-1)), a(0)=1. - Vladimir Kruchinin, Feb 22 2015

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): A000296 :=n->(-1)^n+sum((-1)^(j-1)*bell(n-j), j=1..n): seq(A000295(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, 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, 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 09 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) )

(Maxima)

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

CROSSREFS

Cf. A000110, A005493, A006505, A057814, A057837, A105794.

A diagonal of triangle in A106436.

Sequence in context: A214167 A214188 A214239 * A032265 A151273 A149271

Adjacent sequences:  A000293 A000294 A000295 * A000297 A000298 A000299

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms, new description from Christian G. Bower, Nov 15 1999

Becker reference from Don Knuth, Dec 20 2003

Reference to my paper added by Jeffrey Shallit, Jan 23 2015

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified May 5 02:47 EDT 2015. Contains 257332 sequences.