A261275 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; triangle C_t(n), t>=0, 0<=n<=t, read by rows.

1, 0, 1, 0, 2, 3, 0, 4, 10, 11, 0, 8, 36, 48, 49, 0, 16, 136, 236, 256, 257, 0, 32, 528, 1248, 1508, 1538, 1539, 0, 64, 2080, 6896, 9696, 10256, 10298, 10299, 0, 128, 8256, 39168, 66384, 74784, 75848, 75904, 75905, 0, 256, 32896, 226496, 475136, 586352, 607520, 609368, 609440, 609441

Offset

0,5

Comments

C_t(n) is the number of sequences of t 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^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.

C_t(n) = C_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.

Formula

G.f.: sum(t>=0, n>=0, C_t(n)x^t/t!y^n) = exp(y/2 (exp(2*x)-1))/(1-y).

C_t(n) = Sum_{i=0..n} A075497(t,i).

Example

Triangle starts:
  1;
  0,  1;
  0,  2,    3;
  0,  4,   10,   11;
  0,  8,   36,   48,   49;
  0, 16,  136,  236,  256,   257;
  0, 32,  528, 1248, 1508,  1538,  1539;
  0, 64, 2080, 6896, 9696, 10256, 10298, 10299;
  ...

Maple

with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
       `if`(i<1, 0, add(x^j*multinomial(n, n-i*j, i$j)/j!*add(
        binomial(i, 2*k), k=0..i/2)^j*b(n-i*j, i-1), j=0..n/i))))
    end:
T:= n-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..n))(b(n$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Aug 13 2015

Mathematica

CC[t_, n_] := Sum[2^(t - m)*StirlingS2[t, m], {m, 0, n}];
Table[CC[t, n], {t, 0, 12}, {n, 0, t}] // Flatten
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[x^j*multinomial[n, Join[{n - i*j}, Table[i, j]]]/j!*Sum[Binomial[i, 2*k], {k, 0, i/2}]^j*b[n - i*j, i - 1], {j, 0, n/i}]]];
T[n_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, n} ] ][b[n, n]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

Crossrefs

Columns n=0,1,2,3 give A000007, A000079, A007582, A233162 (proved for n=3 in reference above).

Main diagonal gives A004211.

Cf. A075497.

Sequence in context: A344276 A363966 A258818 * A140326 A261781 A211402

Adjacent sequences: A261272 A261273 A261274 * A261276 A261277 A261278

Keyword

nonn,tabl

Author

Mark Wildon, Aug 13 2015

Status

approved