%I #34 Jan 22 2020 02:19:23
%S 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,
%T 1,2146,1160,510,209,80,27,7,1,11624,5776,2348,904,335,116,35,8,1,
%U 67146,30832,11610,4184,1481,507,161,44,9,1
%N Triangular array where T(n,k) is the number of set partitions of n with k atomic parts.
%C 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.
%C 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.
%C From _Mike Zabrocki_: (Start)
%C Every set partition can be uniquely split into "atomic" set partitions or is itself already atomic.
%C {{1},{2},{3}} = {{1}}|{{1}}|{{1}}
%C {{1},{23}} = {{1}}|{{12}}
%C {{12},{3}} = {{12}}|{{1}}
%C {{13},{2}} is already atomic
%C {{123}} is already atomic
%C where this operation | is defined as {A1,...,Ar}|{B1,...,Bs} = {A1,...,Ar,B1+n,...,Bs+n}
%C where Bi+n = {bi1+n,bi2+n,...,bik+n} if Bi = {bi1,bi2,...,bik} and n = |A1|+|A2|+...+|Ar|. (End)
%C 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
%C From _Peter Bala_, Aug 05 2014: (Start)
%C 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)).
%C 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)
%H G. C. Greubel, <a href="/A127743/b127743.txt">Rows n=1..100 of triangle, flattened</a>
%F 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
%e The partitions of 4 are
%e 4 31 22 211 1111
%e and the products are
%e 1*6 2*2 1*1 3*1 1*1
%e therefore row 4 of the table is
%e 6 5 3 1.
%e From _Philippe Deléham_, Aug 03 2007: (Start)
%e Triangle begins:
%e 1;
%e 1, 1;
%e 2, 2, 1;
%e 6, 5, 3, 1;
%e 22, 16, 9, 4, 1;
%e 92, 60, 31, 14, 5, 1;
%e 426, 252, 120, 52, 20, 6, 1;
%e 2146, 1160, 510, 209, 80, 27, 7, 1; ...
%e Triangle [0,1,1,2,1,3,1,4,1,...] DELTA [1,0,0,0,0,0,...] begins:
%e 1;
%e 0, 1;
%e 0, 1, 1;
%e 0, 2, 2, 1;
%e 0, 6, 5, 3, 1;
%e 0, 22, 16, 9, 4, 1;
%e 0, 92, 60, 31, 14, 5, 1;
%e 0, 426, 252, 120, 52, 20, 6, 1;
%e 0, 2146, 1160, 510, 209, 80, 27, 7, 1; ...
%e (End)
%t 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_ *)
%o (Maxima)
%o 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 */
%o (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)};
%o for(n=1, 10, for(m=1, n, print1(T(n,m), ", "))) \\ _G. C. Greubel_, Dec 06 2018
%Y Cf. A000041, A000110 (row sums), A074664 (1st column), A048996, A072881, A036043, A036042, A084938.
%K nonn,tabl
%O 1,4
%A _Alford Arnold_, Feb 24 2007
%E Edited by _Franklin T. Adams-Watters_, Jan 25 2010