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

Author

Mark Wildon, Aug 10 2015

Keywords

• nonn
• tabl

Comments

B'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant.

B't(n) = <chi^t, 1{Sym_n}> where chi is the degree n-1 constituent of the natural permutation character of the symmetric group Sym_n. This gives a combinatorial interpretation of B'_t(n) using sequences of box moves on Young diagrams.

B'_t(t) is the number of set partitions of a set of size t into parts of size at least 2 (A000296); this is also the number of cyclically spaced partitions of a set of size t.

B'_t(n) = B'_t(t) if n > t.

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

Cf. A000296, A261139.

For columns n=3-8 see: A001045, A006342, A214142, A214167, A214188, A214239.

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