|
|
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
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
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.
|
|
LINKS
|
|
|
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!
|
|
EXAMPLE
|
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;
|
|
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]
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected description in name to agree with section 4.1 in linked paper Mark Wildon, Mar 11 2019
|
|
STATUS
|
approved
|
|
|
|