A080227 -id:A080227 - cp's OEIS frontend

A186764 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k increasing even cycles (0<=k<=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)

1, 1, 1, 1, 3, 3, 14, 7, 3, 70, 35, 15, 419, 226, 60, 15, 2933, 1582, 420, 105, 23421, 12741, 3423, 630, 105, 210789, 114669, 30807, 5670, 945, 2108144, 1144921, 311160, 55755, 7875, 945, 23189584, 12594131, 3422760, 613305, 86625, 10395, 278279165, 151125052, 41041968, 7429290, 1001385, 114345, 10395

Offset: 0

Emeric Deutsch, Feb 27 2011

Row n contains 1+floor(n/2) entries.
Sum of entries in row n is n!.
T(n,0) = A186765(n).
Sum(k*T(n,k), k>=0) = A080227(n).

			T(3,1)=3 because we have (1)(23), (12)(3), and (13)(2).
T(4,2)=3 because we have (12)(34), (13)(24), and (14)(23).
Triangle starts:
   1;
   1;
   1,  1;
   3,  3;
  14,  7,  3;
  70, 35, 15;
  ...

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

Cf. A186761, A186765, A186766, A186769, A080227.

g := exp((t-1)*(cosh(z)-1))/(1-z): gser := simplify(series(g, z = 0, 15)): for n from 0 to 12 do P[n] := sort(expand(factorial(n)*coeff(gser, z, n))) end do: for n from 0 to 12 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*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)!, 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

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n-j]*Binomial[n-1, j-1]*If[ OddQ[j], (j-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 *)

E.g.f.: G(t,z) = exp((t-1)(cosh z - 1))/(1-z).
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,t,1,1,z).

A230071 Sum over all permutations without double ascents on n elements and each permutation contributes 2 raised to the power of the number of double descents.

Original entry on oeis.org

0, 0, 2, 6, 26, 130, 782, 5474, 43794, 394146, 3941462, 43356082, 520272986, 6763548818, 94689683454, 1420345251810, 22725524028962, 386333908492354, 6954010352862374, 132126196704385106, 2642523934087702122, 55493002615841744562, 1220846057548518380366

Offset: 0

Richard Ehrenborg, Oct 08 2013

nonn

			For n=3 the a(3)= 6 since the 4 permutations 132, 213, 231, 312 all contribute 1 and 321 contributes 2 to the sum. Note when n=4, the permutation 4321 contributes 4 since it has two double descents.
G.f. = 2*x^2 + 6*x^3 + 26*x^4 + 130*x^5 + 782*x^6 + 5474*x^7 + 43794*x^8 + ...

R. Ehrenborg and J. Jung, Descent pattern avoidance, Adv. in Appl. Math., 49 (2012) 375-390.

Cf. A000166, A002627, A080227, A055596, A227918.

a := proc(n) if n < 2 then 0 elif n = 2 then 2 else (2-n)*a(n-3)+a(n-2)+n*a(n-1) fi end: seq(a(n), n=0..9); # Peter Luschny, May 30 2014

a[0] = 0; a[n_] := a[n] = n a[n-1] + (-1)^n + 1;
Array[a, 23, 0] (* Jean-François Alcover, Jul 08 2019, after A080227 *)

E.g.f.: (exp(x)+exp(-x)-2)/(1-x).
a(n) = closest integer to (e-2+1/e)*n! for n > 3.
a(n) = (2-n)*a(n-3) + a(n-2) + n*a(n-1) for n > 2.
a(n) = 2*A080227(n).
a(n) = sum(0<=kA002627(k)). - Peter Luschny, May 30 2014
0 = a(n)*(+a(n+1) - a(n+2) - 3*a(n+3) + a(n+4)) + a(n+1)*(+a(n+1) + a(n+2) - 2*a(n+3)) + a(n+2)*(+a(n+2) + a(n+3) - a(n+4)) + a(n+3)*(+a(n+3)) if n>=0. - Michael Somos, May 30 2014

a(0) and a(1) prepended, partially edited. - Peter Luschny, May 30 2014

cp's OEIS Frontend

A186764 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k increasing even cycles (0<=k<=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)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula