|
|
A186363
|
|
Triangle read by rows: T(n,k) is the number of cycle-up-down permutations of {1,2,...,n} having k fixed points (0 <= k <= n). A permutation is said to be cycle-up-down if it is a product of up-down cycles. A cycle (b(1), b(2), ...) is said to be up-down if, when written with its smallest element in the first position, it satisfies b(1) < b(2) > b(3) < ... .
|
|
2
|
|
|
1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 5, 4, 6, 0, 1, 15, 25, 10, 10, 0, 1, 71, 90, 75, 20, 15, 0, 1, 341, 497, 315, 175, 35, 21, 0, 1, 1945, 2728, 1988, 840, 350, 56, 28, 0, 1, 12135, 17505, 12276, 5964, 1890, 630, 84, 36, 0, 1, 84091, 121350, 87525, 40920, 14910, 3780, 1050, 120, 45, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Sum of entries in row n is A000111(n+1) (the Euler or up-down numbers).
T(n,k) = T(n-k,0)*binomial(n,k).
Sum_{k=0..n} k*T(n,k) = A186365(n).
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. = exp((x-1)z)/(1-sin z).
The trivariate e.g.f. H(t,s,z) of the cycle-up-down permutations of {1,2,...,n} with respect to size (marked by z), number of cycles (marked by t), and number of fixed points (marked by x) is given by H(t,x,z) = exp((x-1)*t*z)/(1-sin(z))^t.
|
|
EXAMPLE
|
T(3,1)=3 because we have (1)(23), (12)(3), and (13)(2).
T(4,2)=6 because we have (1)(2)(34), (1)(23)(4), (1)(24)(3), (12)(3)(4), (13)(2)(4), and (14)(2)(3).
Triangle starts:
1;
0, 1;
1, 0, 1;
1, 3, 0, 1;
5, 4, 6, 0, 1;
15, 25, 10, 10, 0, 1;
|
|
MAPLE
|
G := exp((x-1)*z)/(1-sin(z)): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 10 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 10 do seq(coeff(P[n], x, j), j = 0 .. n) end do; # yields sequence in triangular form
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[k == 0, SeriesCoefficient[Exp[-x]/(1 - Sin[x]), {x, 0, n}] n!, T[n - k, 0] Binomial[n, k]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|