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

1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 2, 4, 11, 6, 1, 16, 18, 40, 35, 10, 1, 104, 142, 178, 195, 85, 15, 1, 688, 1236, 1106, 1148, 665, 175, 21, 1, 5116, 10832, 9300, 7728, 5173, 1820, 322, 28, 1, 44224, 98492, 91680, 63284, 42168, 18165, 4284, 546, 36, 1, 438560, 964172, 974924, 627420, 378620, 181797, 53361, 9030, 870, 45, 1

Offset: 0

Author

Emeric Deutsch, Mar 07 2011

Keywords

• nonn
• tabl

Comments

Sum of entries in row n is n!.

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

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

Examples

			T(3,2)=3 because we have (1)(23), (12)(3), and (13)(2).
T(4,0)=2 because we have (1423) and (1324).
T(4,1)=4 because we have (1234), (1243), (1342), and (1432).
Triangle starts:
1;
0,1;
0,1,1;
0,2,3,1;
2,4,11,6,1;
16,18,40,35,10,1;
		

Links

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

Crossrefs

Cf. A187248, A187249.

Programs

Maple

G := exp((1/4)*(t-1)*(2*z-1+exp(2*z)))/(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 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)*binomial(n-1, j-1)*
      `if`(j=1, x, (j-1)!+2^(j-2)*(x-1)), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..12);  # 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, x, (j-1)! + 2^(j-2)*(x-1)], {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 18 2017, after Alois P. Heinz *)

Formula

E.g.f.: G(t,z) = exp[(1/4)(t-1)(2z - 1 + exp(2z))]/(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(t,t,1,z).