|
|
A261139
|
|
S'_t(n) is the number of set partitions of {1,2,...,t} into exactly n parts such that no part contains both 1 and t or both i and i+1 for some i with 1 <= i < t; triangle S'_t(n), t >= 0, 0 <= n <= t, read by rows.
|
|
10
|
|
|
1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 5, 5, 1, 0, 0, 1, 10, 20, 9, 1, 0, 0, 0, 21, 70, 56, 14, 1, 0, 0, 1, 42, 231, 294, 126, 20, 1, 0, 0, 0, 85, 735, 1407, 924, 246, 27, 1, 0, 0, 1, 170, 2290, 6363, 6027, 2400, 435, 35, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,14
|
|
COMMENTS
|
S'_t(n) is the number of sequences of t non-identity top-to-random shuffles of a deck of n cards that move each card at some time, and overall leave the deck invariant. (See link below.) A261137 may be defined by B'_t(n) = Sum_{m=0..n} S'_t(m).
|
|
LINKS
|
|
|
FORMULA
|
G.f. for column n > 1: x^n/((1+x)*Product_{j=1..n-1} (1-j*x)).
S'_t(n) ~ (n-1)^t/n! as t tends to infinity.
Recurrence: S'_t(n) = S'_{t-1}(n-1) + (n-1)*S'_{t-1}(n) for n >= 3.
S'_t(n) = (1/n!) * Sum_{j=0..n} (-1)^(n-j) * binomial(n, j) * ((j-1)^t + (-1)^t * (j-1)) for t>0. - Andrew Howroyd, Apr 08 2017
Sum_{n=0..t} (n-1)*S'_{t-1}(n) + n*S'_{t-2}(n) = A000296(t) for t >= 3. - Yuchun Ji, Feb 23 2021
|
|
EXAMPLE
|
Triangle starts:
1;
0, 0;
0, 0, 1;
0, 0, 0, 1;
0, 0, 1, 2, 1;
0, 0, 0, 5, 5, 1;
0, 0, 1, 10, 20, 9, 1;
0, 0, 0, 21, 70, 56, 14, 1;
0, 0, 1, 42, 231, 294, 126, 20, 1;
0, 0, 0, 85, 735, 1407, 924, 246, 27, 1;
...
|
|
MAPLE
|
g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
add(`if`(j=l, 0, g(t-1, j, max(h, j))), j=1..h+1))
end:
S:= t-> (p-> seq(coeff(p, x, i), i=0..t))(g(t, 0$2)):
|
|
MATHEMATICA
|
StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}]; T[0, 0] = 1; T[_, 0] = T[_, 1] = 0; T[n_, k_] := SeriesCoefficient[ StirPrimedGF[k, x], {x, 0, n}]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* script completed by Jean-François Alcover, Jan 31 2016 *)
|
|
PROG
|
(PARI)
a(n, k)=if(k==0, n==0, sum(j=0, k, binomial(k, j) * (-1)^(k-j) * ((j-1)^n + (-1)^n * (j-1))) / k!);
for(n=0, 10, for(k=0, n, print1( a(n, k), ", "); ); print(); ); \\ Andrew Howroyd, Apr 08 2017
|
|
CROSSREFS
|
The same as A105794, except for the first two columns.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|