|
|
A322770
|
|
Array read by upwards antidiagonals: T(m,n) = number of set partitions into distinct parts of the multiset consisting of one copy each of x_1, x_2, ..., x_m, and two copies each of y_1, y_2, ..., y_n, for m >= 0, n >= 0.
|
|
10
|
|
|
1, 1, 1, 2, 3, 5, 5, 9, 18, 40, 15, 31, 70, 172, 457, 52, 120, 299, 801, 2295, 6995, 203, 514, 1393, 4025, 12347, 40043, 136771, 877, 2407, 7023, 21709, 70843, 243235, 875936, 3299218, 4140, 12205, 38043, 124997, 431636, 1562071, 5908978, 23308546, 95668354
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. (Background information.)
|
|
LINKS
|
|
|
FORMULA
|
Knuth gives a recurrence using the Bell numbers A000110 (see Maple program).
|
|
EXAMPLE
|
The array begins:
1, 1, 5, 40, 457, 6995, 136771, ...
1, 3, 18, 172, 2295, 40043, 875936, ...
2, 9, 70, 801, 12347, 243235, 5908978, ...
5, 31, 299, 4025, 70843, 1562071, 41862462, ...
15, 120, 1393, 21709, 431636, 10569612, 310606617, ...
52, 514, 7023, 124997, 2781372, 75114998, 2407527172, ...
203, 2407, 38043, 764538, 18885177, 559057663, 19449364539, ...
...
|
|
MAPLE
|
B := n -> combinat[bell](n):
Q := proc(m, n) local k; global B; option remember;
if n = 0 then B(m) else
(1/2)*( Q(m+2, n-1) + Q(m+1, n-1) - add( binomial(n-1, k)*Q(m, k), k=0..n-1) ); fi; end; # Q(m, n) (which is Knuth's notation) is T(m, n)
|
|
MATHEMATICA
|
Q[m_, n_] := Q[m, n] = If[n == 0, BellB[m], (1/2)(Q[m+2, n-1] + Q[m+1, n-1] - Sum[Binomial[n-1, k] Q[m, k], {k, 0, n-1}])];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|