A186761
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k increasing odd cycles (0<=k<=n). A cycle (b(1), b(2), ...) is said to be increasing if, when written with its smallest element in the first position, it satisfies b(1)
1, 0, 1, 1, 0, 1, 1, 4, 0, 1, 9, 4, 10, 0, 1, 33, 56, 10, 20, 0, 1, 235, 218, 211, 20, 35, 0, 1, 1517, 1982, 833, 616, 35, 56, 0, 1, 12593, 14040, 9612, 2408, 1526, 56, 84, 0, 1, 111465, 134248, 72588, 35176, 5838, 3360, 84, 120, 0, 1, 1122819, 1305126, 797461, 276120, 107710, 12516, 6762, 120, 165, 0, 1
Offset: 0
Examples
T(3,1)=4 because we have (1)(23), (12)(3), (13)(2), and (123). T(4,1)=4 because we have (1)(243), (143)(2), (142)(3), and (132)(4). Triangle starts: 1; 0, 1; 1, 0, 1; 1, 4, 0, 1; 9, 4, 10, 0, 1; 33, 56, 10, 20, 0, 1; ...
Links
- Alois P. Heinz, Rows n = 0..170, flattened
Programs
-
Maple
g := exp((t-1)*sinh(z))/(1-z): gser := simplify(series(g, z = 0, 13)): 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], t, k), k = 0 .. n) end do; # yields sequence in triangular form # second Maple program: b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-j)*( `if`(j::odd, x-1, 0)+(j-1)!)*binomial(n-1, j-1), j=1..n))) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)): seq(T(n), n=0..14); # Alois P. Heinz, May 12 2017 -
Mathematica
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n - j]*(If[OddQ[j], x - 1, 0] + (j - 1)!)*Binomial[n - 1, j - 1], {j, 1, n}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)
Formula
E.g.f.: G(t,z) = exp((t-1)*sinh z)/(1-z).
The 5-variate e.g.f. H(x,y,u,v,z) of permutations with respect to size (marked by z), number of increasing odd cycles (marked by x), number of increasing even cycles (marked by y), number of nonincreasing odd cycles (marked by u), and number of nonincreasing even cycles (marked by v), is given by
H(x,y,u,v,z)=exp(((x-u)sinh z + (y-v)(cosh z - 1))*(1+z)^{(u-v)/2}/(1-z)^{(u+v)/2}.
Comments