A127743 Triangular array where T(n,k) is the number of set partitions of n with k atomic parts.

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

Offset: 1

Author

Alford Arnold, Feb 24 2007

Keywords

• nonn
• tabl

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.

From Mike Zabrocki: (Start)

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

From Peter Bala, Aug 05 2014: (Start)

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)

Examples

			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.
From _Philippe Deléham_, Aug 03 2007: (Start)
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)
		

Links

• G. C. Greubel, Rows n=1..100 of triangle, flattened

Crossrefs

Cf. A000041, A000110 (row sums), A074664 (1st column), A048996, A072881, A036043, A036042, A084938.

Programs

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

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

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

Extensions

Edited by Franklin T. Adams-Watters, Jan 25 2010