login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
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)
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.
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)
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
Cf. A000041, A000110 (row sums), A074664 (1st column), A048996, A072881, A036043, A036042, A084938.
Sequence in context: A189175 A271776 A171486 * A125278 A134558 A344639
KEYWORD
nonn,tabl
AUTHOR
Alford Arnold, Feb 24 2007
EXTENSIONS
Edited by Franklin T. Adams-Watters, Jan 25 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:58 EDT 2024. Contains 371235 sequences. (Running on oeis4.)