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,14

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.

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.

Formula

B'_t(n) = Sum_{i=0..n} A261139(t,i).

Example

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

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

Crossrefs

Cf. A000296, A261139.

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

Sequence in context: A238797 A025120 A025096 * A319341 A086798 A378408

Adjacent sequences: A261134 A261135 A261136 * A261138 A261139 A261140

Keyword

nonn,tabl

Author

Mark Wildon, Aug 10 2015

Status

approved