A261137 Number of set partitions B'_t(n) of {1,2,...,t} into at most n parts, so that no part contains both 1 and t, or both i and i+1 with 1 <= i < t; triangle B'_t(n), t>=0, 0<=n<=t, read by rows.
1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 3, 4, 0, 0, 0, 5, 10, 11, 0, 0, 1, 11, 31, 40, 41, 0, 0, 0, 21, 91, 147, 161, 162, 0, 0, 1, 43, 274, 568, 694, 714, 715, 0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425, 0, 0, 1, 171, 2461, 8824, 14851, 17251, 17686, 17721, 17722
Offset: 0
Examples
Triangle starts: 1; 0, 0; 0, 0, 1; 0, 0, 0, 1; 0, 0, 1, 3, 4; 0, 0, 0, 5, 10, 11; 0, 0, 1, 11, 31, 40, 41; 0, 0, 0, 21, 91, 147, 161, 162; 0, 0, 1, 43, 274, 568, 694, 714, 715; 0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425; ...
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
- D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.
Crossrefs
Programs
-
Maple
g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h), add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1)) end: B:= t-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..t))(g(t, 0$2)): seq(B(t), t=0..12); # Alois P. Heinz, Aug 10 2015 -
Mathematica
StirPrimedGF[0, x_] := 1; StirPrimedGF[1, x_] := 0; StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}]; StirPrimed[0, 0] := 1; StirPrimed[0, _] := 0; StirPrimed[t_, n_] := Coefficient[Series[StirPrimedGF[n, x], {x, 0, t}], x^t]; BPrimed[t_, n_] := Sum[StirPrimed[t, m], {m, 0, n}] (* Second program: *) g[t_, l_, h_] := g[t, l, h] = If[t == 0, If[l == 1, 0, x^h], Sum[If[j == l, 0, g[t - 1, j, Max[h, j]]], {j, 1, h + 1}]]; B[t_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, t}] ][g[t, 0, 0]]; Table[B[t], {t, 0, 12}] // Flatten (* Jean-François Alcover, May 20 2016, after Alois P. Heinz *)
Formula
B't(n) = Sum{i=0..n} A261139(t,i).
Comments