This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/SetPartitions

From OeisWiki

Jump to: navigation, search

Set partitions and
Bell numbers.

Set partitions have been studied for a long time. Notice the symbols (called Genji-Kô symbols) used as part of the design for the back cover of a Murasaki imitation from the 19th century. They stand for set partitions. The exact mathematical meaning of these symbols in modern notation will be given below.

KEYWORDS: Set partitions, set partitions with singletons, multiton set partitions, Bell numbers, generalized Bell numbers, Stirling numbers of second kind, central Peirce numbers, double enumerations, Genji-Kô symbols.

Concerned with sequences:  A000012, A000110, A000262, A000296, A002720, A003709, A003712, A003724, A005046, A005493, A006505, A007837, A008277, A008299, A011965, A011966, A011967, A011968, A011969, A011970, A020556, A024429, A024430, A033452, A038041, A057814, A057837, A059385, A059386, A069223, A069948, A071379, A080510, A090209, A090210, A094577, A097147, A131632, A178979, A182924, A182925, A182930, A182932, A182933.

Contents

The four flavors of set partitions

Let us first look at the number of set partitions of {1,2,...,n} in which |k| is the smallest block, 1=n, 1=k=n. This triangle starts:

n\k 1 2 3 4 5 6 7 8 9
1 1                
2 1 0              
3 2 1 1    
4 5 3 2 1    
5 15 10 7 5 4    
6 52 37 27 20 15 11    
7 203 151 114 87 67 52 41    
8 877 674 523 409 322 255 203 162  
9 4140 3263 2589 2066 1657 1335 1080 877 715

The set partitions counted are:

n\k 1 2 3 4 5
1 1        
2 1|2 -      
3 1|23
1|2|3
2|13 3|12
4

1|234
1|2|34
1|3|24
1|4|23

1|2|3|4

2|134
2|3|14

2|4|13

3|124

3|4|12
4|123
5

1|2345
1|2|345
1|3|245
1|4|235
1|5|234
1|23|45
1|24|35
1|25|34
1|2|3|45
1|2|4|35
1|2|5|34
1|3|4|25
1|3|5|24
1|4|5|23

1|2|3|4|5

2|1345
2|3|145
2|4|135
2|5|134
2|13|45
2|14|35
2|15|34
2|3|4|15
2|3|5|14

2|4|5|13

3|1245
3|4|125
3|5|124
3|12|45
3|14|25
3|15|24

3|4|5|12

4|1235
4|5|123
4|12|35
4|13|25

4|15|23

5|1234
5|12|34
5|13|24

5|14|23

Although this is an elementary and natural way to enumerate and count set partitions this pretty triangle is not in the database of OEIS. Amazing. (Edit: it is now A182930.)

And I have not seen the description given above elsewhere either. So this is perhaps difficult to compute? No, this is not the case:

T := proc(n, k) option remember;
  if n = 1 then 1
elif n = k then T(n-1,1) - T(n-1,n-1)
else            T(n-1,k) + T(n, k+1) fi end:

However, it does not take much to realize that the above enumerations do not list all set partitions. Here are the missing ones:

  n   
1 -
2 12
3 123
4 1234, 12|34, 13|24, 14|23
5

12345, 12|345, 13|245, 14|235,
15|234, 23|145, 24|135, 25|134,

34|125, 35|124, 45|123

There is a nice way to display these two sets of set partitions which together give the full set of set partitions using Genji-Kô symbols. Here for the case n = 5:

From these two pictures we can read off their definitions visually: In the first picture each symbol has at least one free column (free means that the column is not connect with any other column). And the second picture shows the complement of this set: Each column of a symbol is joined with at least one other column.

We need some terminology here: we will call the set partitions with free columns partitions with singletons (Ps) and those with only joined columns multiton partitions (Pm). Thus the set partitions are the disjoint union (or direct sum) of partitions with singletons and the multiton partitions.

Counting the symbols gives 11 + 41 = 52. This relation continues: 41 + 162 = 203; 162 + 715 = 877; etc. The general situation is given in the table below.

seq \ n 0 1 2 3 4 5 6 7 8 9 10
  Ps(n)   0 1 1 4 11 41 162 715 3425 17722 98253
A000296 Pm(n)  1 0 1 1 4 11 41 162 715 3425 17722
A000110 P(n)   1 1 2 5 15 52 203 877 4140 21147 115975

We observe two identities:
(1)  card(P(n)) = card(Ps(n)) + card(Pm(n)) 
(2)  card(Pm(n)) = card(Ps(n-1))       (n≥1)

Partitions with singletons and multiton partitions describe the first pair of important attributes in the study of set partitions. The second such pair can also be easily identified from the tables of Genji symbols: Crossing and noncrossing partitions. For example 12|345 is a noncrossing partition and 13|245 is a crossing partition (see the pictures above). The formal definition goes like this:

Given a partition p of the set [n], a crossing in p are four integers [a, b, c, d] with 1 ≤ a < b < c < d ≤ n for which a, c are together in a block, and b, d are together in a different block. A crossing partition then is a partition with crossings, a noncrossing partition is a partition with no crossings.

seq \ n 0 1 2 3 4 5 6 7 8 9 10
A016098 Pc(n)   0 0 0 0 1 10 71 448 2710 16285 99179
A000108 Pn(n)  1 1 2 5 14 42 132 429 1430 4862 16796
A000110 P(n)   1 1 2 5 15 52 203 877 4140 21147 115975


Partition arrays

The Peirce-Bell-Aitken array

A123346, A011971. The table below is the triangle of the numbers of set partitions of {1,2,...,n} in which |k| is the smallest block given at the beginning of this page, displayed as a square array. There is a small but significant difference between this array and the two Peirce-Bell-Aitken [1] [2] [3] square arrays given in the database: it has an additional column at the left hand side.

  A000296 A000110 A011968 A011969 A011970 - -
A000110 1 1 2 5 15 52 203
A005493 0 1 3 10 37 151 674
A011965 1 2 7 27 114 523 2589
A011966 1 5 20 87 409 2066 11155
A011967 4 15 67 322 1657 9089 52922
 - 11 52 255 1335 7432 43833 272947

The generalized Peirce-Bell-Aitken array

The observation in the last section, that the Peirce-Bell-Aitken square array can be extended in a natural way to the left hand side can be pushed further. The array can be extended to all negative indices of k retaining the basic construction rule:

T(n,k) = T(n,k − 1) + T(n + 1,k − 1)
n\k −5 −4 −3 −2 −1 Bell

0

1 2 3 4 5
0 1 1 1 1 1 1 2 5 15 52 203
1 0 0 0 0 0 1 3 10 37 151 674
2 0 0 0 0 1 2 7 27 114 523 2589
3 0 0 0 1 1 5 20 87 409 2066 11155
4 0 0 1 0 4 15 67 322 1657 9089 52922
5 0 1 −1 4 11 52 255 1335 7432 43833 272947
6 1 −2 5 7 41 203 1080 6097 36401 229114 1515903
7 −3 7 2 34 162 877 5017 30304 192713 1286789 8999244
8 10 −5 32 128 715 4140 25287 162409 1094076 7712455 56767747

And here how to compute this array:

gPBA := proc(k,n) local i; 
add((-1)^(i+n)*binomial(n,i)*combinat[bell](k+i+1),i=0..n)end: 
seq(print([n],seq(gPBA(k,n),k=-5..5)),n=0..8); 

The values from the central diagonal (0,0), (1,1), (2,2),... are the Peirce numbers A094577.

New (?) partition arrays for all pairs n, k integer

The next question is: can we also extended the PBA-array sensible to negative indices of n? These are my two obvious proposals:

n\k −5 −4 −3 −2 −1 Bell

0

1 2 3 4 5
−5 −80 −34 −12 −3 0 1 2 4 8 16 32
−4 46 22 9 3 1 1 2 4 8 16 32
−3 −24 −13 −6 −2 0 1 2 4 8 16 33
−2 11 7 4 2 1 1 2 4 8 17 41
−1 −4 −3 −2 −1 0 1 2 4 9 24 76
0 1 1 1 1 1 1 2 5 15 52 203
1 0 0 0 0 0 1 3 10 37 151 674
2 0 0 0 0 1 2 7 27 114 523 2589
3 0 0 0 1 1 5 20 87 409 2066 11155
                       
n\k −5 −4 −3 −2 −1 Bell

0

1 2 3 4 5
−5 −74 −19 11 28 40 52 67 87 114 151 203
−4 55 30 17 12 12 15 20 27 37 52 76
−3 −25 −13 −5 0 3 5 7 10 15 24 42
−2 12 8 5 3 2 2 3 5 9 18 42
−1 −4 −3 −2 −1 0 1 2 4 9 24 76
0 1 1 1 1 1 1 2 5 15 52 203
1 0 0 0 0 0 1 3 10 37 151 674
2 0 0 0 0 1 2 7 27 114 523 2589
3 0 0 0 1 1 5 20 87 409 2066 11155

In both cases the lower rectangle (n≥0) coincides with the generalized PBA array. In the first case Bell(−n) ← 1 for n > 0; in the second case Bell(−n) ← Bell(n) for n > 0. The basic construction rule T(n, k) = T(n, k-1) + T(n+1, k-1) is still valid for both variants; the value of B(−2) forces the arrays apart.

The second array might by called Bellis bellis as (0,0) radiates the sequence of Bell numbers four times.

A third variant is obtained by setting Bell(−n) ← 0 for n > 0.

n\k −5 −4 −3 −2 −1 Bell

0

1 2 3 4 5
−5 −126 −56 −21 −6 −1 0 0 0 0 0 1
−4 70 35 15 5 1 0 0 0 0 1 6
−3 −35 −20 −10 −4 −1 0 0 0 1 5 17
−2 15 10 6 3 1 0 0 1 4 12 35
−1 −5 −4 −3 −2 −1 0 1 3 8 23 75
0 1 1 1 1 1 1 2 5 15 52 203
1 0 0 0 0 0 1 3 10 37 151 674
2 0 0 0 0 1 2 7 27 114 523 2589
3 0 0 0 1 1 5 20 87 409 2066 11155

Consider the diagonal starting at (2,0), (1,1), .. : 2, 3, 5, 8, 12, 17, 23, 30, .. These numbers have a nice interpretation, it is the number of liberties a big eye of size n gives in the game of Go, as remarked by Andre Engels in A089071.

Next consider the diagonal starting at (0,0), (-1,-1), .. : 1, -1, 3, -10, 35, -126, 462, .. The absolute value of which is the total number of leaves in all rooted ordered trees with n edges (Michael Somos' A088218), or the number of ordered partitions of n into n parts (Vladeta Jovovic), or the central numbers of Reinhard Zumkeller's A110555; in fact the triangle in the upper left corner is A110555 as a triangular array, up to an index transformation.

Note also that A011968, A011969, A011970, are the columns starting at (-1,1), (-2,2) and (-3,3) respectively.

Bell numbers

Next let us look closer at the interrelations between the members of the triangle. Let B(n) = card(P(n)) denote the Bell numbers and C(n,k) the binomial coefficients. Further define

U(n)   := sum_{k=0..n} C(n,k)B(k).
S(n)   := sum_{k=0..n} C(n,k)B(k)(-1)^(n-k);
A(n,k) := sum_{i=0..k} C(k,i)B(n-i)(-1)^i;

Then, for n = 0, n = k = 0:

[T1] T(n+2,1)   = U(n)   (0 = n)
[T2] T(n+1,n+1) = S(n)   (0 = n)
[T3] T(n+1,1)   = B(n)   (0 = n)
[T4] T(n+1,k+1) = A(n,k) (0 = n, 0 = k = n)  

From these identities follows

[T5] B(n+1) = U(n)          (0 = n)
[T6] B(n)   = S(n) + S(n+1) (0 = n)

The identity [T5] seems first be proved by Bernstein and Sloane [4].

The number of partitions of {1,2,...,n} in which |m| is the smallest block for some 1 ≤ m ≤ k are the partial row sums of T(n, k).

                         1
                       1, 1
                     2, 3, 4
                   5, 8, 10, 11
                15, 25, 32, 37, 41
            52, 89, 116, 136, 151, 162
        203, 354, 468, 555, 622, 674, 715
  877, 1551, 2074, 2483, 2805, 3060, 3263, 3425

The number of partitions of {1,2,...,n} in which the smallest block is neither |1| nor |n| is A033452(n), and is equal to A005493(n) - Bell(n+1) by a comment of Floor en Lyanne van Lamoen and equal to Bell(n+2) - 2Bell(n+1) by a comment of Vladeta Jovovic.

More general, consider the number of partitions of {1,2,...,n} in which the smallest block is neither |k| nor |n|, 1 ≤ k ≤ n. They connect, generalize and give a combinatorial interpretation for A033452 and A005493.

In the triangle below the diagonal on the left hand side is A033452 (shifted n → n+2) and the the diagonal on the right hand side A005493 (shifted n → n+1).

                         0
                       0, 1
                     1, 2, 3
                   5, 7, 8, 10
                22, 27, 30, 32, 37
           99, 114, 124, 131, 136, 151
        471, 523, 560, 587, 607, 622, 674
  2386, 2589, 2740, 2854, 2941, 3008, 3060, 3263

Generalized Bell numbers

Iterated Bell numbers

A144150 Square array A(n, k), n ≥ 0, k ≥ 0, where the g. f. of column k is 1+g^(k+1)(x) with g = x → exp(x) − 1. Studied by Bell in 1938 [5]. Number of (k+1)-level labeled rooted trees with n leaves.

  A000012 A000110 A000258 A000307 A000357 A000405 A001669 A081624 A081629
A000012 1 1 1 1 1 1 1 1 1
A000012 1 1 1 1 1 1 1 1 1
A000027 1 2 3 4 5 6 7 8 9
A000326 1 5 12 22 35 51 70 92 117
A005945 1 15 60 154 315 561 910 1380 1989
  1 52 358 1304 3455 7556 14532 25488 41709
# From Alois P. Heinz, A144150:
g := proc(p) local b; b := proc(n) option remember; local k;
`if`(n=0,1,add(binomial(n-1,k-1)*p(k)*b(n-k),k=1..n)) end end: 
A144150 := (n, k) -> (g@@k)(1)(n);
seq(print(seq(A144150(n,k),k=0..8)),n=0..5);

Exponential numbers

A189233 Square array A(n, k), n ≥ 0, k ≥ 0, where the e. g. f. of column k is exp(k*(e^x-1)). Studied by Bell in 1934.

expnums := proc(k,n) option remember; local j; `if`(n=0,1,
(1+add(binomial(n-1,j-1)*expnums(k,n-j), j=1..n-1))*k) end:

expnums(-1,n) = 1, -1, 0, 1, 1, -2, -9, -9, 50, 267 
expnums(1,n)  = 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147

More general, for k = -7 ...0

n \ k   0 -1 -2 -3 -4 -5 -6 -7
    A000007 A000587 A000000 A000000 A000000 A000000 A000000 A000000
0 A000012 1 1 1 1 1 1 1 1
1 A001489 0 -1 -2 -3 -4 -5 -6 -7
2 A002378 0 0 2 6 12 20 30 42
3 A000000 0 1 2 -3 -20 -55 -114 -203
4 A000000 0 1 -6 -21 -20 45 246 679
5 A000000 0 -2 -14 24 172 370 318 -644

... and for k = 0 ... 7:

n \ k   0 1 2 3 4 5 6 7
    A000007 A000110 A001861 A027710 A078944 A144180 A144223 A144263
0 A000012 1 1 1 1 1 1 1 1
1 A001477 0 1 2 3 4 5 6 7
2 A002378 0 2 6 12 20 30 42 56
3 A033445 0 5 22 57 116 205 330 497
4 A000000 0 15 94 309 756 1555 2850 4809
5 A000000 0 52 454 1866 5428 12880 26682 50134

Sage has also 'expnums' [6].

Generalized Bell numbers based on convolution.

A182931 Number of partitions of a set of n elements where the partitions are of size k, k ≥ n [7].

n \ k 1 2 3 4 5
  A000110 A000296 A006505 A057837 A057814
0 1 1 1 1 1
1 1 0 0 0 0
2 2 1 0 0 0
3 5 1 1 0 0
4 15 4 1 1 0
5 52 11 1 1 1
6 203 41 11 1 1
7 877 162 36 1 1
8 4140 715 92 36 1

Row sums are A097147.

Gamma(k,x) the incomplete Gamma function.
egf := k-> exp(exp(x)*(1-GAMMA(k,x)/GAMMA(k)));
T := (n,k)-> n!*coeff(series(egf(k),x,n+1),x,n):
seq(print(seq(T(n,k),k=1..8)),n=0..8);

Generalized Bell numbers based on falling factorial powers.

A090210 Some of the ideas behind the generalizations of the Bell numbers given below can be found in Penson et alia [8].

Let B_{n}(x) = sum_{j≥0}(exp(j!/(j-n)!*x-1)/j!) then
T(n,k) = k! [x^k] taylor(B_{n}(x)), where [x^k] denotes the
coefficient of x^k in the Taylor series for B_{n}(x).

Let r_{k-1} = [n+1,...,n+1] (k-1 occurrences of n+1), 
s_{k-1} = [1,...,1] (k-1 occurrences of 1) 
and F the generalized hypergeometric function then 
T(n,k) = exp(-1)*n!^(k-1)*F(r_{k-1}, s_{k-1} | 1).

To illustrate the cross-references of T(n,k) when written as a square array.

n \ k   0 1 2 3 4 5
    A000012 A000012 A002720 A069948 A182925 A182924
0 A000012 1 1 1 1 1 1
1 A000110 1 1 2 5 15 52
2 A020556 1 1 7 87 11657 43833
3 A069223 1 1 34 2971 5513559 149670844
4 A071379 1 1 209 163121 3326922081 ..
5 A090209 1 1 1546 112962661 .. ..
6   1 1 13327 1395857215 .. ..
FFPBell := proc(n, k) local r, s, i;
if k=0 then 1 else 
r := [seq(n+1, i=1..k-1)]; s := [seq(1, i=1..k-1)];
exp(-x)*n!^(k-1)*hypergeom(r, s, x); 
round(evalf(subs(x=1, %), 99)) fi end:

seq(lprint(seq(FFPBell(n, k), k=0..6)), n=0..6);

Generalized Bell numbers based on rising factorial powers.

A182933

Let B_{n}(x) = sum_{j≥0}(exp((j+n-1)!/(j-1)!*x-1)/j!) 
then T(n,k) = k! [x^k] series(B_{n}(x)), where [x^k] denotes 
the coefficient of x^k in the Taylor series for B_{n}(x).

Let r_k = [n+1,...,n+1] (k occurrences of n+1), 
s_k = [1,...,1,2] (k-1 occurrences of 1) 
and F the generalized hypergeometric function then
T(n,k) = exp(-1)*n!^k*F(r_k, s_k | 1).

To illustrate the cross-references of T(n,k) when written as a square array.

n \ k   0 1 2 3 4 5
    A000012 A000262 A182934    
0 A000012 1 1 1 1 1 1
1 A000110 1 1 2 5 15 52
2 A094577 1 3 27 409 9089 272947
3 A182932 1 13 778 104149 25053583 9566642254
4   1 73 37553 57184313 192052025697 ..
5   1 5501 2688546 56410245661 .. ..
6   1 44051 265141267 .. .. ..
RFPBell := proc(n, k) local r, s, i;
r := [seq(n+1, i=1..k)]; s := [seq(1, i=1..k-1), 2];
exp(-x)*n!^k*hypergeom(r, s, x); 
round(evalf(subs(x=1, %), 99)) end:

seq(lprint(seq(RFPBell(n, k), k=0..6)), n=0..6);

Generalized Bell numbers based on generalized Stirling numbers.

Generalized Stirling_2 Triangle k = -1
Sum: A000110 all partitions: A036040 ~ by length: A008277 ~ by biggest part: A080510
1 [1] [1] [1]
1 [1] [1] [1]
2 [1,1] [1,1] [1,1]
5 [1,3,1] [1,3,1] [1,3,1]
15 [1,4,3,6,1] [1,7,6,1] [1,9,4,1]
52 [1,5,10,10,15,10,1] [1,15,25,10,1] [1,25,20,5,1]
 

A000110(n) is the number of set partitions of {1,2,..,n}.
A008277(n, k) is the number of set partitions of {1,2,..,n} with block length k.
A080510(n, k) is the number of set partitions of {1,2,..,n} with maximum block length k.
A036040(n, k) is the number of set partitions of {1,2,..,n} with block lengths given by the k-th integer partition of n, the integer partitions in the order of the Handbook of Mathematical Functions, p. 831.

Thus all the sequences listed in the first (sum) column of the table Generalized Stirling-2 Triangles can be regarded as generalizations of the Bell numbers, that is as row sums of generalized Stirling numbers of the second kind. So let us see to what this amounts.

k         A001844
   
-6 A049412 1 1 7 85 1465 32677
-5 A049120 1 1 6 61 871 15996
-4 A049119 1 1 5 41 465 6721
-3 A049118 1 1 4 25 211 2236
-2 A000262 1 1 3 13 73 501
-1 A000110 1 1 2 5 15 52
0 A000012 1 1 1 1 1 1
1 A001515 1 1 2 7 37 266
2 A015735 1 1 3 17 145 1661
3 A016036 1 1 4 31 361 5626
4 A028575 1 1 5 49 721 14177
5  A028844 1 1 6 71 1261 29906
          A056220    

Partitions of special types

Partitions with equal block sizes

A038041 The number of partitions of n-set with equal block sizes is

 t(n) = \sum_{d | n} \frac{n!}{ d! { \left((n/d)! \right) }^d } \ \ .
A038041 := proc(n) local d;
add(n!/(d!*(n/d)!^d), d = numtheory[divisors](n)) end:

Partitions with distinct block sizes

A007837 The number of partitions of n-set with distinct block sizes can be computed as a(0) = 1 and

 a(n) = -\sum_{1\le k \le n} \binom{n-1}{k-1} s(k) a(n-k) .

Here we use a recursion from a comment of Vladeta Jovovic which we have slightly changed to emphasize the use of some special multinomial coefficients (A182928 and A182927)

 s(n) = \sum_{d | n} (-1)^d \frac{n!}{ d{ \left((n/d)! \right) }^d } \ \ .
s := proc(n) local d;
add((-1)^d*n!/(d*(n/d)!^d),d=numtheory[divisors](n)) end:
a := proc(n) option remember; local k;
`if`(n=0,1,-add(binomial(n-1,k-1)*s(k)*a(n-k),k=1..n)) end:
s(n) = -1, 0, -3, 8, -25, 99, -721, 5704, -40881 
a(n) = 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966

Illustrating Vladeta Jovovic's A131632, which refines A007837 by the number of blocks:

n\k 1 2
1 1  
2 12  
3 123 1|23, 2|13, 3|12
4 1234 1|234, 2|134, 3|124, 4|123
5 12345

1|2345, 2|1345, 3|1245, 4|1235, 5|1234,
12|345, 13|245, 14|235, 15|234, 23|145,
24|135, 25|134, 34|125, 35|124, 45|123

Even-odd set partitions

Following L. Comtet (Advanced Combinatorics, p.226) we give a list of double enumerations based on the parity of length of the partition and the size of blocks. In the table below the sequences include 0s; this differs from the practice of OEIS to suppress 0s if they occur at all even or odd indices. The advantage of our notation is that it makes the combinatorial interpretation more visible and makes errors like calling A005046 the "number of partitions of an n-set into even blocks" less likely.

Number of
blocks
Size of
each block
Seq
offset 1
ID
unrestricted unrestricted 1,2,5,15,52,203 A000110
unrestricted odd 1,1,2,5,12,37,128 A003724
unrestricted even 0,1,0,4,0,31,0,379 A005046
odd unrestricted 1,1,2,7,27,106,443 A024429
even unrestricted 0,1,3,8,25,97,434 A024430
odd odd 1,0,2,0,12,0,128 A003712
odd even 0,1,0,1,0,16,0,211 A059385
even odd 0,1,0,5,0,37,0,457 A003709
even even 0,0,0,3,0,15,0,168 A059386

The exponential generating functions are:

A000110_egf := x -> exp(exp(x)-1);
A003724_egf := x -> exp(sinh(x));
A005046_egf := x -> exp(cosh(x)-1);
A024429_egf := x -> sinh(exp(x)-1);
A024430_egf := x -> cosh(exp(x)-1);
A003712_egf := x -> sinh(sinh(x));
A059385_egf := x -> sinh(cosh(x)-1);
A003709_egf := x -> cosh(sinh(x));
A059386_egf := x -> cosh(cosh(x)-1);

This is only the tip of the iceberg. The interested reader might execute the Maple code below to find many more interesting sequences. They count the set partitions of the above configurations by the number of blocks.

B000110_egf := k -> exp(k*(exp(x)-1));
B003724_egf := k -> exp(k*sinh(x));
B005046_egf := k -> exp(k*(cosh(x)-1));
B024429_egf := k -> sinh(k*(exp(x)-1));
B024430_egf := k -> cosh(k*(exp(x)-1));
B003712_egf := k -> sinh(k*sinh(x));
B059385_egf := k -> sinh(k*(cosh(x)-1));
B003709_egf := k -> cosh(k*sinh(x));
B059386_egf := k -> cosh(k*(cosh(x)-1));

EGF := [B000110_egf,B003724_egf,B005046_egf,B024429_egf,
B024430_egf,B003712_egf,B059385_egf,B003709_egf,B059386_egf]:
for egf in EGF do
T := (n,k) -> n!*coeff(series(egf(k),x,n+1),x,n):
print(egf): seq(lprint(seq(T(n,k),k=1..8)),n=1..8) od:


The complementary Bell numbers

Rényi numbers

The most compact form we have found for the Bell numbers was the exponential generating function A000110_egf(x) = exp(+(exp(x)-1)). Now, what happens if we just change the sign +?

A000587_egf(x) = exp(-(exp(x)-1));
-1, 0, 1, 1, -2, -9, -9, 50, 267, 413, -2180,...

A000587 These numbers were first studied by R. E. Beard (1950) [9] and Alfréd Rényi (1966) [10]. Antal Fekete [11] calls these numbers 'Rényi numbers'. I am following his lead here. The work of Alfréd Rényi on these numbers seems to be overlooked by many authors, possibly because it was written in Hungarian. On OEIS they are called 'Rao Uppuluri-Carpenter' numbers; the reason for this choice remains unclear despite the fact that Rao Uppuluri and Carpenter later also worked on these numbers [12].

Looking closer at A000587_egf := k -> exp(k*(1-exp(x))) we find the square array below.

-1,  -2,   -3,    -4,    -5,    -6,    -7 
 0,   2,    6,    12,    20,    30,    42
 1,   2,   -3,   -20,   -55,  -114,  -203
 1,  -6,  -21,   -20,    45,   246,   679
-2, -14,   24,   172,   370,   318,  -644

Clearly this array is nothing else but the exponential numbers from A189233 for k < 0 already given in a table above.

The combinatorial meaning of the Rényi numbers can be summarized by the comment from F. T. Adams-Watters: "Number of set partitions of 1..n with an even number of parts, minus the number of such partitions with an odd number of parts." This follows also from our table given above. More arithmetically the relation between the Bell numbers and the Rényi numbers can stated as:

A024430 = (Bn + Rn) / 2;
A024429 = (Bn − Rn) / 2.

Proof: cosh(exp(x)−1) − sinh(exp(x)−1) = exp(1−exp(x)).

The generalized Beard-Rényi array

The generalized Beard-Rényi array is the analogue to the generalized Peirce-Bell-Aitken array given above. The basic construction rule still applies:

T(n,k) = T(n,k − 1) + T(n + 1,k − 1)

The core difference is to replace the Bell numbers by the complementary Bell numbers, the Rényi numbers.

n\k −5 −4 −3 −2 −1 Rényi

0

1 2 3 4 5
0 1 1 1 1 -1 1 0 -1 -1 2 9
1 0 0 0 -2 2 -1 -1 0 3 7 0
2 0 0 -2 4 -3 0 1 3 4 -7 -59
3 0 -2 6 -7 3 1 2 1 -11 -52 -99
4 -2 8 -13 10 -2 1 -1 -12 -41 -47 328
5 10 -21 23 -12 3 -2 -11 -29 -6 375 2111
6 -31 44 -35 15 -5 -9 -18 23 381 1736 3001
7 75 -79 50 -20 -4 -9 41 358 1355 1265 -21590
8 -154 129 -70 16 -5 50 317 997 -90 -22855 -155473

And here how to compute this array:

gBR := proc(k,n) local i; 
add((-1)^(i+n+1)*binomial(n,i)*A000587(k+i+1),i = 0..n)end: 
seq(print([n],seq(gBR(k,n),k = -5..5)),n = 0..8); 

Row n = 1 for k ≥ 0 starts -1, -1, 0, 3, 7, 0, -59,... By a comment from Vladeta Jovovic in A074051 this can be computed by the formula

 \text{Row1}(n) = \sum_{0 \le k \le n} (-1)^{k+1} (k^2-3k+1) \left\{{n\atop k}\right\}.

Column k = 1 for n ≥ 0 starts 0, -1, 1, 2, -1, -11, -18,... By a formula from Vladeta Jovovic in A101851 this can be computed as

 \text{Col1}(n) = \sum_{0 \le k \le n} (-1)^{k} k \left\{{n\atop k}\right\}.

Continous generalizations

The Bell polynomials

The Bell polynomial Bn(x) is a polynomial that generalizes the Bell numbers Bn and Rényi numbers Rn such that Bn(1) = Bn and Bn(-1) = Rn. One way to define these polynomials is by Dobinski's formula.

 B_{n}(x) = e^{-x} \sum_{k \ge 0} k^n \frac {x^k}{k!}

The coefficients of the polynomials are in A106800. More about the Bell polynomials can be found in an exposition of K. N. Boyadzhiev [13].

The Bell function

Recently Fredrik Johansson[14] implemented the Bell polynomials using Dobinski's formula because this formula "generalizes to arbitrary complex values for n, not just integers." Johansson writes

Unfortunately, there is a difficulty in implementing Dobinski's formula for general n: the 0th term is singular unless n is a nonnegative real number. Removing the term completely breaks compatibility with the standard definition of the Bell polynomials for n = 0. Keeping it either makes the series undefined, or at best renders the function discontinuous at the single point n = 0 which is certainly not desirable. As a workaround, I changed the formula to

 B_{n}(x) = e^{-x} \left(\mathrm{sinc}(\pi n)+\sum_{k \ge 0} k^n \frac {x^k}{k!} \right)
def Bell_polynomials(n, x) :
    
    def sinc(x) :
        return 1 if x==0 else sin(pi*x)/(pi*x)
        
    def es(s,x) :
        k = var('k')
        return sum((k^s/factorial(k))*x^k, k, 1, oo)
        
    if   n==0 : r = 1
    elif n==1 : r = x 
    elif n==2 : r = x*(x+1)
    else      : r = (sinc(n)+es(n,x))/exp(x)
    return factor(r)

This 'workaround', as Johansson calls it, is a nice idea which does work. Let us look at a few examples.

The Bell polynomials:

for i in (0..5) :
    print Bell_polynomials(i,x)

                 1
                 x
             x (x + 1)
          x (1 + 3 x + x^2 )
      x (1 + 7 x + 6 x^2  + x^3 )
 x (1 + 15 x + 25 x^2  + 10 x^3  + x^4 )

Triangle of Stirling numbers of 2nd kind, S(n,n-k):

for m from 0 to 5 do seq(coeff(Bell(m,x),x,i),i=0..m) od;
           1
          0, 1
        0, 1, 1
       0, 1, 3, 1
     0, 1, 7, 6, 1
  0, 1, 15, 25, 10, 1

The Bell numbers: Bell(i,1), the Rényi numbers: Bell(i,-1).
A mysterious sequence: seq(Bell(i,-i),i=1..9);
-1, 2, -3, -20, 370, -4074, 34293, -138312, -2932533
Another mysterious sequence: seq(Bell(i,i),i=1..9);
1,6,57,756,12880,268098,6593839,187104200,6016681467
The sequence: seq(Bell(-i,i),i=1..9); shows that
Bell(-i,i) = i*hypergeom([seq(1,j=0..i)],[seq(2,j=0..i)],i)/exp(i)).

Thus the Dobinski-Johansson function gives generalized Bell numbers DJ(x) = Bell(x,1) for all real and complex values of x.

DJ := proc(x) `if`(x=0,1, 
(sin(Pi*x)/(Pi*x)+sum(k^x/k!,k=1..infinity))/exp(1)) end:

Just out of curiosity I computed DJ(-1). It has the value 0.484829106995687646310. Simon Plouffe's Inverter [15] helped me to find out that DJ(−1) = (Ei(1)−gamma)/exp(1), Ei the exponential integral.

Set partitions computationally

Counting set partitions efficiently

A000110 Bell numbers: Number of partitions of a set of n labeled elements.

A000110_list := proc(m)
local A, R, n, k;
A := array(0..m-1);
A[0] := 1;
R := 1;
for n from 0 to m-1 do
  A[n] := A[0];
  for k by -1 from n to 1 do
    A[k-1] := A[k-1] + A[k] od;
  R := R,A[0];
od;
R end:
A000110_list(20); 

The same with Sage:

############################################
# n -> [a(0), a(1), ..., a(n)] for n > 0.
############################################

def A000110_generator(m) :
    A = [1]; yield A[0]
    for n in (0..m - 1) :
        for k in range(n, 0, -1) :
            A[k-1] += A[k]
        A.append(A[0])
        yield A[0] 

list(A000110_generator(15))

A000587 Rényi numbers (or Uppuluri-Carpenter numbers): the complementary Bell numbers.

A000587_list := proc(m)
local A, R, n, k; 
A := array(0..m-1);
A[m-1] := 1;
R := 1;
for n from 0 to m-1 do
  A[m-1-n] := -A[m-1];
  for k from m-n to m-1 do
    A[k] := A[k] + A[k-1] od;
  R := R,A[m-1];
od;
R end:
A000587_list(20);

The same with Sage:

############################################
# n -> [a(0), a(1), ..., a(n)] for n > 0.
############################################

def A000587_generator(n):
    yield 1; yield -1; A = [-1]
    for j in (0..n-2) :
        A.append(-A[0])
        for k in range(j,-1,-1) :
            A[k] += A[k+1]
        yield A[0]

list(A000587_generator(15))

A000296 Number of multiton partitions of a set of n labeled elements.

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);

The same with Sage:

############################################
# n -> [a(0), a(1), ..., a(n)] for n > 0.
############################################

def A000296_generator(n) :
    yield 1; yield 0; A = [1]
    for i in (0..n-2) :
        A.append(A[0] - A[i])
        A[i] = A[0]
        for k in range(i,0,-1) :
            A[k-1] = A[k-1] + A[k]
        yield A[0] - A[i+1]
        
list(A000296_generator(15))

A094577 Central Peirce numbers: Number of set partitions of {1,2,..,2n+1} in which |n+1| is the smallest of its block.

A094577_list := proc(m)
local A, R, M, n, k, j;
M := m+m-1; A := array(1..M);
j := 1; R := 1; A[1] := 1;
for n from 2 to M do
   A[n] := A[1];
   for k from n by -1 to 2 do
      A[k-1] := A[k-1] + A[k]
   od;
   if is(n, odd) then
      j := j+1; R := R, A[j] fi
od;
[R] end:
A094577_list(20); 

The same with Sage:

############################################
# n -> [a(0), a(1), ..., a(n)] for n > 0.
############################################

def A094577_generator(m) :
    A = [1]; yield 1
    for n in (1..m) :
        A.append(A[0])
        for k in range(n, 0, -1) :
            A[k-1] += A[k]
        if is_even(n) :
            yield A[n//2]
         
list(A094577_generator(15))

A020556 Central singleton numbers: Number of set partitions with singletons of {1,2,..,2n+1} in which |n+1| is the smallest of its block.

T := proc(n, k) option remember;
  if n = 1 then 1
elif n = k then T(n-1,1) - T(n-1,n-1)
else T(n-1,k) + T(n, k+1) fi end:

A020556 := n -> T(2*n+1,n+1);
seq(A020556(n),n=0..99);

Generating set partitions (with Maple)

Generating set partitions with Maple is straightforward.

spec := [S,{S=Set(U,card ≥ 1),U=Set(Z,card ≥ 1)},labeled]:
combstruct[allstructs](spec, size=4);

The result is, however, pretty useless.

[Set(Set(Z[4]),Set(Z[1]),Set(Z[2],Z[3])),Set(Set(Z[4],Z[3]),
Set(Z[2]),Set(Z[1])),Set(Set(Z[1],Z[2]),Set(Z[3]),Set(Z[4])),
Set(Set(Z[4],Z[3]),Set(Z[1],Z[2])),Set(Set(Z[1],Z[4],Z[2]),
Set(Z[3])),Set(Set(Z[2]),Set(Z[1],Z[4],Z[3])),Set(Set(Z[4]),
Set(Z[1],Z[2],Z[3])),Set(Set(Z[3]),Set(Z[2]),Set(Z[4]),Set(Z[1])),
Set(Set(Z[3]),Set(Z[2]),Set(Z[1],Z[4])),Set(Set(Z[3]),Set(Z[1]),
Set(Z[4],Z[2])),Set(Set(Z[1],Z[4],Z[2],Z[3])),Set(Set(Z[2]),
Set(Z[4]),Set(Z[1],Z[3])),Set(Set(Z[2],Z[3]),Set(Z[1],Z[4])),
Set(Set(Z[1]),Set(Z[4],Z[2],Z[3])),Set(Set(Z[4],Z[2]),
Set(Z[1],Z[3]))]

Thus we have to write our own version, which will generate in the forgoing example this output:

1234,13|2|4,2|4|3|1,234|1,14|23,24|13,34|2|1,23|4|1,12|34,
12|4|3,24|3|1,14|2|3,124|3,134|2,123|4.
toString := proc(p) local s,t,i; 
s := convert(p,string); t := NULL; 
for i from 2 to length(s) - 3 do
if s[i] = "}" and s[i+1] = "," and not(s[i-1] = "}") then t := t,`|`;
elif s[i] = "}" and s[i+1] = "}" and s[i+2] = "," then t := t,`,`; 
elif member(s[i],{"{"," ",",","}"}) then ;
else t := cat(t,s[i]) fi od end:

with(combstruct):
SetPartitions := proc(opt,n,k) local P,G,F,j,w,parts; 

parts := proc(n,b) local i,T,P; 
allstructs([B,{B=Set(Set(Z,card≥b))},labelled],size=n):
eval(subs(Set=(()->{args}),seq(Z[i]=i,i=1..n),%)) end:

G := (p,k)->`if`(k=min(op(map(op,select(s->nops(s)=1,p)))),p,NULL):
F := `if`(opt='cardsingle' or opt='cardmulti' or opt='cardall',
      nops,toString);
P := `if`(opt='multiton' or opt='cardmulti',parts(n,2),parts(n,1));

if opt='multiton' or opt='cardmulti' or opt='cardall' or opt='all'
then F(P) elif k > 0 then F({seq(G(w,k),w=P)}) 
else seq(F({seq(G(w,j),w=P)}),j=1..n) fi end:

Usage and test:

n:=4:
SetPartitions('all',n,0);
SetPartitions('cardall',n,0);
SetPartitions('multiton',n,0);
SetPartitions('cardmulti',n,0);
seq(print([k],
SetPartitions('singleton',n,k)),k=1..n);
SetPartitions('cardsingle',n,0);

Results:

> "1234,13|2|4,2|4|3|1,234|1,14|23,24|13,34|2|1,23|4|1,12|34,
  12|4|3,24|3|1,14|2|3,124|3,134|2,123|4"
> 15
> "1234,14|23,24|13,12|34"
> 4
> [1],"24|3|1,23|4|1,234|1,34|2|1,2|4|3|1"
  [2],"14|2|3,134|2,13|2|4"
  [3],"3|4|12,3|124"
  [4],"4|123"
> 5,3,2,1

Generating set partitions with restricted growth strings

Finally we generate set partitions in a standalone fashion based on restricted growth strings. Below a 'goto'-free port from Joerg Arndt's C++ code in his Matters Computational [16].

# N Length of strings
# I s[k] <= f[k]+I
# I = 1 --> RGS for set partitions
Rgs := proc(N,I) local j, s, f, L, next_str;

next_str := proc() local k,j,sk,m1,mp;
# Returns index of first changed element in s[],
# Returns zero if current string is the last

k := N;
do
  k := k-1;
  if k = 0 then RETURN(0) fi;

  sk := s[k] + 1;
  m1 := f[k - 1];
  mp := m1 + I;

  if sk > mp  # "carry"
  then
    s[k] := 0;
  else
    s[k] := sk;
    if sk = mp then m1 := m1 + I fi;
    for j from k to N-1 do f[j] := m1 od;
    RETURN(k);
  fi
od
end;

s := array(0..N-1);  # restricted growth string
f := array(0..N-1);  # values F(k)
for j from 0 to N-1 do s[j] := 0 od;
for j from 0 to N-1 do f[j] := 0 od;

L := NULL;
do
  L := L, convert(s,list);
  if next_str() = 0 then break fi;
od;
[L] end:

Classification := proc(s) local L,i,m;
m := 1 + max(op(s));
L := [seq([],i=1..m)];
for i from 1 to nops(s) do
  L[s[i]+1] := [op(L[s[i]+1]),i];
od;
L end:

SetPartitions := proc(n) local P,S,s;
P := NULL; S := Rgs(n,1);
for s in S do P := P,Classification(s) od:
[P] end:

The same with Sage using generators:

# Returns index of first changed element in s[],
# Returns zero if current string is the last
def next_rgs(N, s, f) :
    k = N
    while True :
        k -= 1
        if k == 0 : 
            return 0

        sk = s[k] + 1
        m1 = f[k - 1]
        mp = m1 + 1

        if sk > mp : # carry
            s[k] = 0
        else :
            s[k] = sk
            if sk == mp :
                m1 += 1
            for j in (k..N-1) :
                f[j] = m1
            return k

# N Length of strings
def rgs_generator(N) :
    
    s = [0 for j in range(N)] # restricted growth string
    f = [0 for j in range(N)] # values F(k)

    while True :
        yield s
        if next_rgs(N, s, f) == 0 : 
            return
     
def classification(s) : 
    L = [[] for i in (0..max(s))]
    for i in range(len(s)) : 
        L[s[i]].append(i)
    return L
    
def set_partitions_generator(n) : 
    for s in rgs_generator(n) :
        yield classification(s)

for p in set_partitions_generator(4) : print p
SetPartitions(5);

[[[1,2,3,4,5]],       [[1,2,3,4],[5]],
[[1,2,3,5],[4]],      [[1,2,3],[4,5]],
[[1,2,3],[4],[5]],    [[1,2,4,5],[3]],
[[1,2,4],[3,5]],      [[1,2,4],[3],[5]],
[[1,2,5],[3,4]],      [[1,2],[3,4,5]],
[[1,2],[3,4],[5]],    [[1,2,5],[3],[4]],
[[1,2],[3,5],[4]],    [[1,2],[3],[4,5]],
[[1,2],[3],[4],[5]],  [[1,3,4,5],[2]],
[[1,3,4],[2,5]],      [[1,3,4],[2],[5]],
[[1,3,5],[2,4]],      [[1,3],[2,4,5]],
[[1,3],[2,4],[5]],    [[1,3,5],[2],[4]],
[[1,3],[2,5],[4]],    [[1,3],[2],[4,5]],
[[1,3],[2],[4],[5]],  [[1,4,5],[2,3]],
[[1,4],[2,3,5]],      [[1,4],[2,3],[5]],
[[1,5],[2,3,4]],      [[1],[2,3,4,5]],
[[1],[2,3,4],[5]],    [[1,5],[2,3],[4]],
[[1],[2,3,5],[4]],    [[1],[2,3],[4,5]],
[[1],[2,3],[4],[5]],  [[1,4,5],[2],[3]],
[[1,4],[2,5],[3]],    [[1,4],[2],[3,5]],
[[1,4],[2],[3],[5]],  [[1,5],[2,4],[3]],
[[1],[2,4,5],[3]],    [[1],[2,4],[3,5]],
[[1],[2,4],[3],[5]],  [[1,5],[2],[3,4]],
[[1],[2,5],[3,4]],    [[1],[2],[3,4,5]],
[[1],[2],[3,4],[5]],  [[1,5],[2],[3],[4]],
[[1],[2,5],[3],[4]],  [[1],[2],[3,5],[4]],
[[1],[2],[3],[4,5]],  [[1],[2],[3],[4],[5]]].

The listing reveals a nice fact: Our triangle A182930 from which we started counts the set partitions in a way which can be simply described as: Number of set partitions of {1,2,..,n} in which |k| is the smallest singleton block. We say a block A is smaller than B if the index of A is smaller than the index of B (the parts of the partitions in the order above, called 'standard order' by Joerg). Note that this order has nothing to do with regard to what element is 'in' the block nor has something to do with the block size.

Set partitions of a 4-set using Genji Genji-Kô symbols. The plot illustrates an algorithm to generate the partitions.

Shows also the modern notation of the set partition when a pointing device (mouse) is placed over a symbol. As this effect does not take place on this wiki go to Commons and click on the picture.

References

  1. Charles S. Peirce, On the Algebra of Logic, American Journal of Mathematics, Vol. 3, 15-57, 1880. Reprinted in Collected Papers.
  2. E. T. Bell, Exponential numbers, American Mathematical Monthly 41, 411-419, 1934.
  3. A. C. Aitken, A problem on combinations, Edinburgh Math. Notes 28 (1933), 18-33.
  4. M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226//228, 57-72, 1995.
  5. E. T. Bell, The Iterated Exponential Integers, Annals of Mathematics, 39 (1938), 539-557.
  6. Sage: sage.combinat.expnums.
  7. E. A. Enneking and J. C. Ahuja, Generalized Bell numbers, Fib. Quart. 14, 67-73, 1976.
  8. K. A. Penson, P. Blasiak, A. Horzela, A. I. Solomon and G. H. E. Duchamp, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. 50, 083512, 2009.
  9. R. E. Beard, On the coefficients in the expansion of e^e^t and e^e^(-t), J. Inst. Actuar. 76 (1950), 152–163.
  10. Alfréd Rényi, Új modszerek es eredmenyek a kombinatorikus analfzisben. I. MTA III Oszt. Ivozl., 16 (1966), 77-105. (Paper is in Hungarian, title is: New methods and results in combinatorial analysis.)
  11. Antal E. Fekete, Apropos Bell and Stirling Numbers, Crux Mathematicorum with Mathematical Mayhem, Canadian Mathematical Society, Volume 25 Number 5 (Sep 1999), 274-281. http://www.math.ca/crux/v25/n5
  12. V. R. Rao Uppuluri and J. A. Carpenter, Numbers generated by the function exp(1-e^x), Fib. Quart. 7 (1969), 437-448.
  13. K. N. Boyadzhiev, Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals. Abstract and Applied Analysis (2009), http://www.hindawi.com/journals/aaa/2009/168672/
  14. Fredrik Johansson, Computing (generalized) Bell numbers, March 2009, http://fredrik-j.blogspot.com/2009/03/computing-generalized-bell-numbers.html
  15. Simon Plouffe, Inverter, http://pi.lacim.uqam.ca/eng/
  16. Joerg Arndt, Fxtbook, 17.3.5 F-increment RGS, p. 366.
Personal tools