|
|
A127743
|
|
Triangular array where T(n,k) is the number of set partitions of n with k atomic parts.
|
|
4
|
|
|
1, 1, 1, 2, 2, 1, 6, 5, 3, 1, 22, 16, 9, 4, 1, 92, 60, 31, 14, 5, 1, 426, 252, 120, 52, 20, 6, 1, 2146, 1160, 510, 209, 80, 27, 7, 1, 11624, 5776, 2348, 904, 335, 116, 35, 8, 1, 67146, 30832, 11610, 4184, 1481, 507, 161, 44, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Triangular array distributing the Bell numbers (A000110). The value associated with each partition is the product of A074664(k) for each part of size k, times the number of compositions associated with the partition (A048996 & A072881). The value for T(n,k) is the total of these values for each partition of n into k parts.
Calculating the appropriate weights can be done by "working backward". Suppose for example we know the weights for 1 through 6 and desire the weight for the partitions of seven: Substitute the weights for each partition value and multiply. For example, 7 = 4+3 so f([4,3]) = 6*2 = 12; adjusting for the number of permutations of [4,3] we now have 2*12 = 24. Continuing in this manner for each partition of seven and summing to 451 we now know all of the values except that associated with the partition [7] which must be 877 - 451 = 426.
Every set partition can be uniquely split into "atomic" set partitions or is itself already atomic.
{{1},{2},{3}} = {{1}}|{{1}}|{{1}}
{{1},{23}} = {{1}}|{{12}}
{{12},{3}} = {{12}}|{{1}}
{{13},{2}} is already atomic
{{123}} is already atomic
where this operation | is defined as {A1,...,Ar}|{B1,...,Bs} = {A1,...,Ar,B1+n,...,Bs+n}
where Bi+n = {bi1+n,bi2+n,...,bik+n} if Bi = {bi1,bi2,...,bik} and n = |A1|+|A2|+...+|Ar|. (End)
Subtriangle (n >= 1 and 1 <= k <= n} of triangle given by [0,1,1,2,1,3,1,4,1,5,1,6,...] DELTA [1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 03 2007
Let B(x) = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + ... denote the o.g.f. for the Bell numbers A000110. Let f(x) = (B(x) - 1)/(x*B(x)) = 1 + x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for the first column of this array. Then this array appears to be the Riordan array (f(x), x*f(x)).
If true, this gives the o.g.f. of the array as (B(x) - 1)/( x*(t + (1 - t)*B(x)) ) = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ... and also the hockey-stick recurrence: T(n+1,k+1) = T(n,k) + T(n-1,k) + 2*T(n-2,k) + 6*T(n-3,k) + 22*T(n-4,k) + ..., n,k >= 1. (End)
|
|
LINKS
|
|
|
FORMULA
|
T(n, m) = Sum_{k=1..n-m}( Sum_{i=1..n-m-k}(T(k+i, k)*C(n-m-k-1, n-m-k-i))*C(k+m-1, k) ) + C(n-1, n-m). - Vladimir Kruchinin, Mar 21 2015
|
|
EXAMPLE
|
The partitions of 4 are
4 31 22 211 1111
and the products are
1*6 2*2 1*1 3*1 1*1
therefore row 4 of the table is
6 5 3 1.
Triangle begins:
1;
1, 1;
2, 2, 1;
6, 5, 3, 1;
22, 16, 9, 4, 1;
92, 60, 31, 14, 5, 1;
426, 252, 120, 52, 20, 6, 1;
2146, 1160, 510, 209, 80, 27, 7, 1; ...
Triangle [0,1,1,2,1,3,1,4,1,...] DELTA [1,0,0,0,0,0,...] begins:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 6, 5, 3, 1;
0, 22, 16, 9, 4, 1;
0, 92, 60, 31, 14, 5, 1;
0, 426, 252, 120, 52, 20, 6, 1;
0, 2146, 1160, 510, 209, 80, 27, 7, 1; ...
(End)
|
|
MATHEMATICA
|
T[n_, m_] := T[n, m] = Sum[Sum[T[k+i, k]*Binomial[n-m-k-1, n-m-k-i], {i, 1, n-m-k}]*Binomial[k+m-1, k], {k, 1, n-m}] + Binomial[n-1, n-m]; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 23 2015, after Vladimir Kruchinin *)
|
|
PROG
|
(Maxima)
T(n, m):=sum((sum(T(k+i, k)*binomial(n-m-k-1, n-m-k-i), i, 1, n-m-k))*binomial(k+m-1, k), k, 1, n-m)+binomial(n-1, n-m); /* Vladimir Kruchinin, Mar 21 2015 */
(PARI) {T(n, m) = sum(k=1, n-m, (sum(i=1, n-m-k, (T(k+i, k)*binomial(n-m-k-1, n-m-k-i))*binomial(k+m-1, k)))) + binomial(n-1, n-m)};
for(n=1, 10, for(m=1, n, print1(T(n, m), ", "))) \\ G. C. Greubel, Dec 06 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|