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