|
|
A186769
|
|
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k nonincreasing even cycles (0<=k<=floor(n/4)). 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 even if it has an even number of entries. For example, the permutation (1528)(347)(6) has 1 nonincreasing even cycles.
|
|
11
|
|
|
1, 1, 2, 6, 19, 5, 95, 25, 451, 269, 3157, 1883, 21092, 18353, 875, 189828, 165177, 7875, 1660351, 1764749, 203700, 18263861, 19412239, 2240700, 197541565, 237001478, 43736682, 721875, 2568040345, 3081019214, 568576866, 9384375, 33029787974, 43065489284, 10638945317, 444068625
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Row n has 1+floor(n/4) entries.
Sum of entries in row n is n!.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: G(t,z)=exp((1-t)(cosh z - 1))*(1+z)^{(1-t)/2}/(1-z)^{(1+t)/2}.
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}.
We have: G(t,z) = H(1,1,1,t,z).
|
|
EXAMPLE
|
T(4,1)=5 because we have (1243), (1324), (1342), (1423), and (1432).
Triangle starts:
1;
1;
2;
6;
19,5;
95,25;
451,269;
|
|
MAPLE
|
g := exp((1-t)*(cosh(z)-1))*(1+z)^((1-t)*1/2)/(1-z)^((1+t)*1/2): gser := simplify(series(g, z = 0, 18)): for n from 0 to 14 do P[n] := sort(expand(factorial(n)*coeff(gser, z, n))) end do; for n from 0 to 14 do seq(coeff(P[n], t, k), k = 0 .. floor((1/4)*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::odd, (j-1)!, 1+x*((j-1)!-1)), j=1..n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
|
|
MATHEMATICA
|
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n-j]*Binomial[n - 1, j - 1]*If[ OddQ[j], (j - 1)!, 1 + x*((j - 1)! - 1)], {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|