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

1, 0, 0, 0, 1, 1, 0, 0, 3, 1, 0, 1, 10, 8, 1, 0, 0, 30, 50, 15, 1, 0, 1, 91, 280, 155, 24, 1, 0, 0, 273, 1491, 1365, 371, 35, 1, 0, 1, 820, 7728, 11046, 4704, 756, 48, 1, 0, 0, 2460, 39460, 85050, 53382, 13020, 1380, 63, 1

Offset: 0

Author

Mark Wildon, Aug 14 2015

Keywords

• tabl
• nonn

Comments

T'_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 and every card must be moved at least once.

Examples

			Triangle starts:
1;
0,  0;
0,  1,   1;
0,  0,   3,    1;
0,  1,  10,    8,     1;
0,  0,  30,   50,    15,    1;
0,  1,  91,  280,   155,   24,   1;
0,  0, 273, 1491,  1365,  371,  35,  1;
0,  1, 820, 7728, 11046, 4704, 756, 48,  1;
		

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

PARI

T(t, n) = {if ((t==0) && (n==0), return(1)); if (n==0, return(0)); if (n==1, return(1 - t%2)); 1/(2^n*n!)*(sum(k=0,n-1,binomial(n,k)*(-1)^k*(2*(n-k)-1)^t)+(-1)^(n+t));}
tabl(nn) = {for (t=0, nn, for (n=0, t, print1(T(t, n), ", ");); print(););} \\ Michel Marcus, Aug 17 2015

Formula

T'_t(n) = 1/2^n n! sum(k=0..n-1,binomial(n,k)*(-1)^k*(2(n-k)-1)^t)+(-1)^(n+t)/2^n! for n > 1.

G.f. for column n>1: x^n/((1+x)*Product_{j=1..n-1} 1/(1-(2*j-1)*x)).

Asymptotically for n > 1: T'_t(n) equals (2n-1)^t/2^n n!

Extensions

One more row by Michel Marcus, Aug 17 2015

Corrected description in name to agree with section 4.1 in linked paper Mark Wildon, Mar 11 2019