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) < ... .

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

Offset: 0

Author

Emeric Deutsch, Feb 28 2011

Keywords

• nonn
• tabl

Comments

Sum of entries in row n is A000111(n+1) (the Euler or up-down numbers).

T(n,0) = A186364(n).

T(n,k) = T(n-k,0)*binomial(n,k).

Sum_{k=0..n} k*T(n,k) = A186365(n).

Examples

			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;
		

Links

• E. Deutsch and S. Elizalde, Cycle up-down permutations, arXiv:0909.5199v1 [math.CO].

Crossrefs

Cf. A186364, A186365.

Programs

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]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 24 2018 *)

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.