A187244 Triangle read by rows: T(n,k) is the number of permutations of [n] having k cycles with 2 alternating runs (it is assumed that the smallest element of the cycle is in the first position), 0<=k<=floor(n/3).

1, 1, 2, 5, 1, 17, 7, 78, 42, 463, 247, 10, 3315, 1550, 175, 27164, 11049, 2107, 247975, 92596, 22029, 280, 2492539, 906427, 220734, 9100, 27422698, 10044963, 2264724, 184415, 328607417, 122314296, 25036462, 3028025, 15400, 4266367567, 1607778568, 307273681, 44800184, 800800

Offset: 0

Author

Emeric Deutsch, Mar 07 2011

Keywords

• nonn
• tabf

Comments

Number of entries in row n is 1+floor(n/3).

Sum of entries in row n is n!.

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

Sum(k*T(n,k), k>=0) = A187246(n).

Examples

			T(4,1)=7 because we have (132)(4), (142)(3), (1)(243), (143)(2), (1432), (1243), and (1342).
Triangle starts:
1;
1;
2;
5,1;
17,7;
78,42;
463, 247, 10;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A187245, A187246.

Programs

Maple

G := exp((1/4)*(t-1)*(2*z-4*exp(z)+exp(2*z)+3))/(1-z): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 13 do seq(coeff(P[n], t, k), k = 0 .. floor((1/3)*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)*binomial(n-1, j-1)*
      `if`(j=1, 1, (j-1)!+(2^(j-2)-1)*(x-1)), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..14);  # Alois P. Heinz, Apr 15 2017

Mathematica

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n - j]*Binomial[n - 1, j - 1]* If[j == 1, 1, (j - 1)! + (2^(j - 2) - 1)*(x - 1)], {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, May 03 2017, after Alois P. Heinz *)

Formula

E.g.f.: G(t,z) = exp[(1/4)(t-1)(2z-4exp(z)+exp(2z)+3)]/(1-z).

The 4-variate g.f. H(u,v,w,z) (exponential with respect z), where u marks number of cycles with 1 alternating run, v marks number of cycles with 2 alternating runs, w marks the number of all cycles, and z marks the size of the permutation, is given by

H(u,v,w,z)=exp[(1/4)w((v-1)(exp(2z)+2z)+4(u-v)exp(z)+1-4u+3v)]/(1-z)^w.

We have G(t,z)=H(1,t,1,z).