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)<b(2)<b(3)<... . A cycle is said to be odd if it has an odd number of entries. For example, the permutation (152)(347)(6)(8) has 3 increasing odd cycles.

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,8

Comments

Sum of entries in row n is n!.

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

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

Links

Alois P. Heinz, Rows n = 0..170, flattened

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

Example

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

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

Crossrefs

Cf. A186762, A186763, A186764, A186766, A186769.

Sequence in context: A342911 A221483 A121408 * A199786 A348129 A189245

Adjacent sequences: A186758 A186759 A186760 * A186762 A186763 A186764

Keyword

nonn,tabl

Author

Emeric Deutsch, Feb 27 2011

Status

approved