|
|
A000296
|
|
Set partitions without singletons: number of partitions of an n-set into blocks of size > 1. Also number of cyclically spaced (or feasible) partitions.
(Formerly M3423 N1387)
|
|
132
|
|
|
1, 0, 1, 1, 4, 11, 41, 162, 715, 3425, 17722, 98253, 580317, 3633280, 24011157, 166888165, 1216070380, 9264071767, 73600798037, 608476008122, 5224266196935, 46499892038437, 428369924118314, 4078345814329009, 40073660040755337, 405885209254049952, 4232705122975949401
(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(k) 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
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
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:
{{1},{2},{3},{4},{5}}
{{1},{2},{3,5},{4}}
{{1},{2,4},{3},{5}}
{{1},{2,5},{3},{4}}
{{1,3},{2},{4},{5}}
{{1,4},{2},{3},{5}}
{{1},{2,4},{3,5}}
{{1,3},{2,4},{5}}
{{1,3},{2,5},{4}}
{{1,4},{2},{3,5}}
{{1,4},{2,5},{3}}
(End)
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
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
|
|
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
|
Steven R. Finch, Moments of sums, April 23, 2004. [Cached copy, with permission of the author]
D. Reidenbach and J. C. Schneider, Morphically Primitive Words. In Pierre Arnoux, Nicolas Bedaride and Julien Cassaigne, editors, Proc. 6th International Conference on Words, WORDS 2007, pages 262-272. 2007. [Different from the paper with the same name, referenced below.]
Daniel Reidenbach and Johannes C. Schneider, Morphically primitive words, Theoretical Computer Science, (2009), 140 (21-23), pp. 2148-2161.
Jeffrey 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.
|
|
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=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
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_{j=1..n} (-1)^(j-1)*B(n-j), 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
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)
Continued fractions:
G.f.: (2/E(0) - 1)/x where E(k) = 1 + 1/(1 + 2*x/(1 - 2*(k+1)*x/E(k+1))).
G.f.: 1/U(0) where U(k) = 1 - x*k - x^2*(k+1)/U(k+1).
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))).
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1+x-k*x)/(1-x/(x-1/G(k+1))).
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)))).
G.f.: 1/(x*Q(0)) where Q(k) = 1 + 1/(x + x^2/(1 - x - (k+1)/Q(k+1))).
G.f.: -(1+(2*x+1)/G(0))/x where G(k) = x*k - x - 1 - (k+1)*x^2/G(k+1).
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)).
G.f.: (1 + x * Sum_{k>=0} (x^k / Product_{p=0..k}(1 - p*x))) / (1 + x). (End)
G.f. A(x) satisfies: A(x) = (1/(1 + x)) * (1 + x * A(x/(1 - x)) / (1 - x)). - Ilya Gutkovskiy, May 21 2021
a(n) ~ exp(n/LambertW(n) - n - 1) * n^(n-1) / (sqrt(1 + LambertW(n)) * LambertW(n)^(n-1)). - Vaclav Kotesovec, Jun 28 2022
|
|
EXAMPLE
|
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)];
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)]
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:
|
|
MATHEMATICA
|
nn = 25; Range[0, nn]! CoefficientList[Series[Exp[Exp[x] - 1 - x], {x, 0, nn}], x]
(* Second program: *)
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 *)
spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:= Join@@Function[s, Prepend[#, s]&/@spsu[ Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];
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 *)
s = 1; Join[{1}, Table[s = BellB[n] - s, {n, 0, 25}]] (* Vaclav Kotesovec, Jun 20 2022 *)
|
|
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 */
(Magma) [1, 0] cat [ n le 1 select 1 else Bell(n)-Self(n-1) : n in [1..40]]; // Vincenzo Librandi, Jun 22 2015
(Python)
from itertools import accumulate, islice
yield from (1, 0)
blist, a, b = (1, ), 0, 1
while True:
blist = list(accumulate(blist, initial = (b:=blist[-1])))
yield (a := b-a)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|