A186763 Number of increasing odd cycles in all permutations of {1,2,...,n}.
0, 1, 2, 7, 28, 141, 846, 5923, 47384, 426457, 4264570, 46910271, 562923252, 7318002277, 102452031878, 1536780478171, 24588487650736, 418004290062513, 7524077221125234, 142957467201379447, 2859149344027588940, 60042136224579367741
Offset: 0
Keywords
A186766
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k nonincreasing odd cycles (0<=k<=floor(n/3)). 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)
1, 1, 2, 5, 1, 20, 4, 77, 43, 472, 238, 10, 2585, 2385, 70, 21968, 16504, 1848, 157113, 189695, 15792, 280, 1724064, 1591082, 310854, 2800, 15229645, 21449481, 3100614, 137060, 204738624, 213397204, 59267252, 1583120, 15400, 2151199429, 3347368503, 676271024, 51981644, 200200
Offset: 0
Comments
Examples
T(3,1)=1 because we have (132). T(4,1)=4 because we have (1)(243), (143)(2), (142)(3), and (132)(4). Triangle starts: 1; 1; 2; 5,1; 20,4; 77,43;
Links
- Alois P. Heinz, Rows n = 0..200, flattened
Programs
-
Maple
g := exp((1-t)*sinh(z))*(1+z)^((t-1)*1/2)/(1-z)^((t+1)*1/2): gser := simplify(series(g, z = 0, 16)): 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::even, (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)): seq(T(n), n=0..14); # Alois P. Heinz, Apr 13 2017 -
Mathematica
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n-j]*Binomial[n-1, j-1]*If[ EvenQ[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]]; 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-t)sinh z)*(1+z)^{(t-1)/2}/(1-z)^{(t+1)/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,t,1,z).
A184958
Number of nonincreasing even cycles in all permutations of {1,2,...,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)
0, 0, 0, 0, 5, 25, 269, 1883, 20103, 180927, 2172149, 23893639, 326640467, 4246326071, 65675585793, 985133786895, 17069814958319, 290186854291423, 5579050805341613, 106001965301490647, 2241684406438644939, 47075372535211543719
Offset: 0
Keywords
Examples
a(4) = 5 because the only permutations of {1,2,3,4} having nonincreasing even cycles are (1243), (1324), (1342), (1423), and (1432).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..450
Programs
-
Maple
g := (1/2*(2*(1-cosh(z))-ln(1-z^2)))/(1-z): gser := series(g, z = 0, 27): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 21);
-
Mathematica
With[{nn=30},CoefficientList[Series[1/2(2(1-Cosh[x])-Log[1-x^2])/(1-x), {x,0,nn}],x]Range[0,nn]!] (* Harvey P. Dale, Oct 22 2011 *) Table[(n! HarmonicNumber[n] - HypergeometricPFQ[{1, -n}, {}, -1] + (-1)^(n + 1) HypergeometricPFQ[{1, -n}, {}, 1] + n! (2 + (-1)^n LerchPhi[-1, 1, 1 + n] - Log[2]))/2, {n, 0, 20}] (* Benedict W. J. Irwin, May 30 2016 *)
Formula
a(n) = Sum_{k>=0} k*A186769(n,k).
E.g.f.: (1/2) * (2*(1-cosh(z)) - log(1-z^2))/(1-z).
a(n) ~ n!/2 * (log(n/2) - 1/exp(1) + 2 - exp(1) + gamma), where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 05 2013
a(n) = (n!*H(n)-2F0(1,-n;;-1) + (-1)^(n+1)*2F0(1,-n;;1)+n!*(2+(-1)^n*LerchPhi(-1,1,n+1)-log(2)))/2, where H(n) is the n-th harmonic number. - Benedict W. J. Irwin, May 30 2016
Comments
Examples
Links
Crossrefs
Programs
Maple
Mathematica
a=0;Table[a=n*a+(1/2)(1-(-1)^n),{n,0,30}] (* Vladimir Joseph Stephan Orlovsky, Apr 02 2011 *) CoefficientList[Series[Sinh[x]/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 05 2013 *)Formula