cp's OEIS Frontend

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.

%I A261137 #48 Apr 28 2021 21:04:48
%S A261137 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,
%T A261137 21,91,147,161,162,0,0,1,43,274,568,694,714,715,0,0,0,85,820,2227,
%U A261137 3151,3397,3424,3425,0,0,1,171,2461,8824,14851,17251,17686,17721,17722
%N 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.
%C A261137 B'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant.
%C A261137 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.
%C A261137 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.
%C A261137 B'_t(n) = B'_t(t) if n > t.
%H A261137 Alois P. Heinz, <a href="/A261137/b261137.txt">Rows n = 0..140, flattened</a>
%H A261137 John R. Britnell and Mark Wildon, <a href="http://arxiv.org/abs/1507.04803">Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D</a>, arXiv:1507.04803 [math.CO], 2015.
%H A261137 D. E. Knuth and O. P. Lossers, <a href="http://www.jstor.org/stable/27642185">Partitions of a circular set</a>, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.
%F A261137 B'_t(n) = Sum_{i=0..n} A261139(t,i).
%e A261137 Triangle starts:
%e A261137   1;
%e A261137   0, 0;
%e A261137   0, 0, 1;
%e A261137   0, 0, 0,  1;
%e A261137   0, 0, 1,  3,   4;
%e A261137   0, 0, 0,  5,  10,   11;
%e A261137   0, 0, 1, 11,  31,   40,   41;
%e A261137   0, 0, 0, 21,  91,  147,  161,  162;
%e A261137   0, 0, 1, 43, 274,  568,  694,  714,  715;
%e A261137   0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425;
%e A261137   ...
%p A261137 g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
%p A261137        add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))
%p A261137     end:
%p A261137 B:= t-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..t))(g(t, 0$2)):
%p A261137 seq(B(t), t=0..12);  # _Alois P. Heinz_, Aug 10 2015
%t A261137 StirPrimedGF[0, x_] := 1; StirPrimedGF[1, x_] := 0;
%t A261137 StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}];
%t A261137 StirPrimed[0, 0] := 1; StirPrimed[0, _] := 0;
%t A261137 StirPrimed[t_, n_] := Coefficient[Series[StirPrimedGF[n, x], {x, 0, t}], x^t];
%t A261137 BPrimed[t_, n_] := Sum[StirPrimed[t, m], {m, 0, n}]
%t A261137 (* Second program: *)
%t A261137 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}]];
%t A261137 B[t_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, t}] ][g[t, 0, 0]];
%t A261137 Table[B[t], {t, 0, 12}] // Flatten (* _Jean-François Alcover_, May 20 2016, after _Alois P. Heinz_ *)
%Y A261137 Cf. A000296, A261139.
%Y A261137 For columns n=3-8 see: A001045, A006342, A214142, A214167, A214188, A214239.
%K A261137 nonn,tabl
%O A261137 0,14
%A A261137 _Mark Wildon_, Aug 10 2015