A011968 Apply (1+Shift) to Bell numbers.

1, 2, 3, 7, 20, 67, 255, 1080, 5017, 25287, 137122, 794545, 4892167, 31858034, 218543759, 1573857867, 11863100692, 93345011951, 764941675963, 6514819011216, 57556900440429, 526593974392123, 4981585554604074, 48658721593531669, 490110875149889635

Offset

0,2

Comments

Number of set partitions of n+2 with at least one singleton and the smallest element in any singleton is exactly n. The maximum number of singletons is therefore 3. Alternatively, number of set partitions of n+2 with at least one singleton and the largest element in any singleton is exactly 3 (or n+2 if n+2 < 3). For example, a(3)=7 counts the following set partitions of [5]: {1245, 3}, {12, 3, 45}, {124, 3, 5}, {15, 24, 3}, {125, 3, 4}, {14, 25, 3}, {12, 3, 4, 5}. - Olivier Gérard, Oct 29 2007

Let V(N)={v(1),v(2),...,v(N)} denote an ordered set of increasing positive integers containing a pair of adjacent elements that differ by at least 2, that is, v(i),v(i+1) with v(i+1)-v(i) > 1. Then for n > 0, a(n) is the number of partitions of V(n+1) into blocks of nonconsecutive integers. - Augustine O. Munagi, Jul 17 2008

References

Olivier Gérard and Karol Penson, A budget of set partitions statistics, in preparation, unpublished as of Sep 22 2011

Links

Chai Wah Wu, Table of n, a(n) for n = 0..500 n = 0..200 from Vincenzo Librandi.

Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K.; On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841.

Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K.; On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841. [Annotated scanned copy]

Augustine O. Munagi, Extended set partitions with successions, European J. Combin. 29(5) (2008), 1298--1308.

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

Formula

For n >= 1, a(n+1) = exp(-1)*Sum_{k>=0} ((k+1)/k!)*k^n. - Benoit Cloitre, Mar 09 2008

For n >= 1, a(n) = Bell(n) + Bell(n-1). - Augustine O. Munagi, Jul 17 2008

G.f.: G(0) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 19 2012

G.f.: 1 + x*E(0) where E(k) = 1 + 1/(1-x*k-x)/(1-x/(x+1/E(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 20 2013

G.f.: 1 + Sum_{k>=0} ( 1+1/(1-x-x*k) )*x^(k+1)/Product_{i=0..k} (1-x*i). - Sergei N. Gladkovskii, Jan 20 2013

a(n) ~ Bell(n) * (1 + LambertW(n)/n). - Vaclav Kotesovec, Jul 28 2021

Example

a(3)=7 because the set {1,3,4,5} has 7 different partitions into blocks of nonconsecutive integers: 14/35, 135/4, 1/35/4, 13/4/5, 14/3/5, 15/3/4, 1/3/4/5.

Maple

with(combinat): seq(`if`(n>0, bell(n)+bell(n-1), 1), n=0..21); # Augustine O. Munagi, Jul 17 2008

Prog

(Python)
# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A011968_list, blist, b = [1, 2], [1], 1
for _ in range(10**2):
....blist = list(accumulate([b]+blist))
....A011968_list.append(b+blist[-1])
....b = blist[-1] # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

Crossrefs

Cf. A000110, A000296, A011969, A011970.

A diagonal of A011971 and A106436. - N. J. A. Sloane, Jul 31 2012

Cf. A000569, A240936, A321750.

Sequence in context: A222867 A222776 A222890 * A080021 A306666 A032313

Adjacent sequences: A011965 A011966 A011967 * A011969 A011970 A011971

Keyword

nonn

Author

N. J. A. Sloane

Status

approved