A261319 Number of set partitions C'_t(n) of {1,2,...,t} into at most n parts, with an even number of elements in each part distinguished by marks and such that no part contains both 1 and t (each unmarked) or both i and i+1 (each unmarked) for some i with 1 <= i < t; triangle C'_t(n), t>=0, 0<=n<=t, read by rows.

1, 0, 0, 0, 1, 2, 0, 0, 3, 4, 0, 1, 11, 19, 20, 0, 0, 30, 80, 95, 96, 0, 1, 92, 372, 527, 551, 552, 0, 0, 273, 1764, 3129, 3500, 3535, 3536, 0, 1, 821, 8549, 19595, 24299, 25055, 25103, 25104

Offset: 0

Author

Mark Wildon, Aug 14 2015

Keywords

• nonn
• tabl

Comments

C'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant, if each shuffle is permitted to flip the orientation of the card it moves.

C't(n) = <(pi-1{BSym_n})^t, 1_{BSym_n}> where pi is the permutation character of the hyperoctahedral group BSym_n = C_2 wreath Sym_n given by its imprimitive action on a set of size 2n. This gives a combinatorial interpretation of C'_t(n) using sequences of box moves on pairs of Young diagrams.

C'_t(t) is the number of set partitions of a set of size t with an even number of elements in each part distinguished by marks and such that no part contains both 1 and t (each unmarked) or both i and i+1 (each unmarked) for some i with 1 <= i < t.

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

Examples

			Triangle starts:
1;
0,  0;
0,  1,   2;
0,  0,   3,    4;
0,  1,  11,   19,    20;
0,  0,  30,   80,    95,    96;
0,  1,  92,  372,   527,   551,   552;
0,  0, 273, 1764,  3129,  3500,  3535,  3536;
0,  1, 821, 8549, 19595, 24299, 25055, 25103, 25104;
		

Links

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

Crossrefs

Cf. A261275, A261318, A261139, A261137.

Programs

Mathematica

TGF[1, x_] := x^2/(1 - x^2); TGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - (2*j - 1)*x), {j, 1, n}];
T[0, 0] := 1; T[, 0] := 0; T[0, ] := 0; T[t_, n_] := Coefficient[Series[TGF[n, x], {x, 0, t}], x^t];
CC[t_, n_] := Sum[T[t, m], {m, 0, n}]

Formula

C't(n) + C'_t(n-1) = Sum{s=0..t-1} binomial(t-1,s)*A261275(s,n-1) for n>=1.

E.g.f.: diagonal is exp(1/2*(exp(2*x)-2*x-1)).

C't(n) = Sum{i=0..n} A261318(t,i).