A162979 -id:A162979 - cp's OEIS frontend

A129817 Number of alternating fixed-point-free permutations on n letters.

1, 0, 1, 1, 2, 6, 24, 102, 528, 2952, 19008, 131112, 1009728, 8271792, 74167488, 703077552, 7194754368, 77437418112, 890643066048, 10726837356672, 136988469649728, 1825110309733632, 25625477737660608, 374159217291201792, 5728724202727533888, 90961591766739121152, 1508303564683904357568, 25874345243221479539712, 461932949559928514787648, 8513674175717969079785472, 162818666826944872460200128

Offset: 0

Vladeta Jovovic, May 20 2007

nonn

For n > 0, a(2n-1) = A129815(2n-1); for n > 1, a(2n) = A129815(2n) + A129815(2n-2). - Vladimir Shevelev, Apr 29 2008
We conjecture that for n >= 3, A000111(2n)/a(2n) < e < A000111(2n)/A129815(2n), so that A000111(2n)/a(2n) increases while A000111(2n)/A129815(2n) decreases (and both quotients tend to e). - Vladimir Shevelev, Apr 29 2008
From Emeric Deutsch, Aug 06 2009: (Start)
Alternating permutations are also called down-up permutations.
a(n) is also the number of alternating permutations of {1,2,...,n} having exactly 1 fixed point (see the Richard Stanley reference). Example: a(4)=2 because we have 4132 and 3241.
(End)

			a(4) = 2 because we have 3142 and 2143. - _Emeric Deutsch_, Aug 06 2009

R. P. Stanley, Alternating permutations and symmetric functions, arXiv:math/0603520 [math.CO], 2006.

Cf. A000111, A000166, A007779.

Column k=0 of A162979.

nmax = 30;
fo = Exp[e*(ArcTan[q*t] - ArcTan[t])]/(1 - e*t);
fe = Sqrt[(1+t^2)/(1+q^2*t^2)]*Exp[e*(ArcTan[q*t] - ArcTan[t])]/(1-e*t);
Q[n_] := If [OddQ[n] ,  SeriesCoefficient[fo, {t, 0, n}],  SeriesCoefficient[fe, {t, 0, n}]] // Expand;
b[n_] :=  n!*SeriesCoefficient[Sec[x] + Tan[x], {x, 0, n}];
P[n_] := (Q[n] /. e^k_Integer :> b[k]) /. e :> b[1] // Expand;
a[n_] := Coefficient[P[n], q, 0];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, nmax}] (* Jean-François Alcover, Jul 24 2018 *)

a(n) = A162979(n,0). - Alois P. Heinz, Nov 24 2017

a(21) from Alois P. Heinz, Nov 06 2015
a(0)=1 prepended by Alois P. Heinz, Nov 24 2017
a(22)..a(30) from Jean-François Alcover, Jul 24 2018

A162978 Number of fixed points in all alternating (i.e., down-up) permutations of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 4, 15, 52, 257, 1272, 7679, 47864, 346113, 2604380, 22022143, 194053836, 1881735169, 18998097328, 207983607807, 2366490065968, 28880901505025, 365599818496116, 4922617151619071, 68612903386404260, 1010501269355233281, 15376572385777544744

Offset: 1

Emeric Deutsch, Aug 06 2009

nonn

a(n) = Sum_{k>=0} k*A162979(n,k).

a(2n+1) = A162977(2n+1).

			a(4)=4 because in the 5 (=A000111(4)) down-up permutations of {1,2,3,4}, namely 4132, 3142, 2143, 4231, and 3241, we have a total of 1+0+0+2+1=4 fixed points.

Alois P. Heinz, Table of n, a(n) for n = 1..485
R. P. Stanley, Alternating permutations Talk slides.

Cf. A000111, A162977, A162979.

E := sec(x)+tan(x): Eser := series(E, x = 0, 30): for n from 0 to 27 do E[n] := factorial(n)*coeff(Eser, x, n) end do: for n to 12 do a[2*n] := E[2*n]+(-1)^n*E[0]+2*add((-1)^j*E[2*n-2*j], j = 1 .. n-1) end do: for n from 0 to 12 do a[2*n+1] := add((-1)^j*E[2*n+1-2*j], j = 0 .. n) end do: seq(a[n], n = 1 .. 25);

a111[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1) (2^(n+1) - 1) BernoulliB[n+1])/(n+1)]];
a[n_?EvenQ] := With[{m = n/2}, a111[2m] + (-1)^m a111[0] + 2Sum[(-1)^j a111[2m - 2j], {j, 1, m-1}]];
a[n_?OddQ] := With[{m = (n-1)/2}, Sum[(-1)^j a111[2m+1-2j], {j, 0, m}]];
Array[a, 25] (* Jean-François Alcover, Jul 24 2018 *)

a(2n) = E(2n) + (-1)^n*E(0) + 2*Sum_{j=1..n-1} (-1)^j*E(2n-2j), a(2n+1) = Sum_{j=0..n} (-1)^j*E(2n+1-2j), where E(i) = A000111(i) are the Euler (or up-down) numbers.

A162980 Triangle read by rows: T(n,k) is the number of reverse alternating (i.e., up-down) permutations of {1,2,...,n} having k fixed points (n >= 0, 0 <= k <= 1 + floor(n/2)).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 1, 2, 2, 1, 6, 6, 3, 1, 22, 22, 12, 4, 1, 102, 102, 51, 15, 2, 506, 506, 264, 88, 19, 2, 2952, 2952, 1476, 458, 89, 9, 18502, 18502, 9504, 3168, 726, 110, 9, 131112, 131112, 65556, 20868, 4479, 621, 44, 991226, 991226, 504864, 168288, 39696, 6672, 749, 44

Offset: 0

Emeric Deutsch, Aug 06 2009

Row n has 2 + floor(n/2) entries (n>=5).
Sum of entries in row n is the Euler (up-down) number A000111(n).
T(n,0) = T(n,1) = A129815(n) (n>=1).
T(2n-1,n) = T(2n,n+1) = d(n-1), where d(n) = A000166 is a derangement number (see the Chapman & Williams reference).
Sum_{k>=0} k*T(n,k) = A162977(n).

			T(5,2)=3 because we have 15243, 14352, and 25341.
Triangle starts:
    1;
    0,   1;
    0,   0,   1;
    1,   1;
    2,   2,   1;
    6,   6,   3,   1;
   22,  22,  12,   4,   1;
  102, 102,  51,  15,   2;

R. Chapman and L. K. Williams, A conjecture of Stanley on alternating permutations, The Electronic J. of Combinatorics, 14, 2007, #N16.
R. P. Stanley, Alternating permutations and symmetric functions, J. Comb. Theory A 114 (3) (2007) 436-460.

Cf. A000111, A000166, A129815, A162977, A162979.

fo := exp(E*(arctan(q*t)-arctan(t)))/(1-E*t): fe := sqrt((1+q^2*t^2)/(1+t^2))*exp(E*(arctan(q*t)-arctan(t)))/(1-E*t): foser := simplify(series(fo, t = 0, 18)): feser := simplify(series(fe, t = 0, 18)): Q := proc (n) if `mod`(n, 2) = 1 then coeff(foser, t, n) else coeff(feser, t, n) end if end proc: for n from 0 to 16 do Q(n) end do: g := sec(x)+tan(x): gser := series(g, x = 0, 20): for n from 0 to 18 do a[n] := factorial(n)*coeff(gser, x, n) end do: for n from 0 to 15 do P[n] := sort(subs({E = a[1], E^2 = a[2], E^3 = a[3], E^4 = a[4], E^5 = a[5], E^6 = a[6], E^7 = a[7], E^8 = a[8], E^9 = a[9], E^10 = a[10], E^11 = a[11], E^12 = a[12], E^13 = a[13], E^14 = a[14], E^15 = a[15], E^16 = a[16]}, Q(n))) end do: 1; 0, 1; 0, 0, 1; 1, 1; 2, 2, 1; for n from 5 to 13 do seq(coeff(P[n], q, j), j = 0 .. 1+floor((1/2)*n)) end do;

nmax = 10;
fo = Exp[e*(ArcTan[q*t] - ArcTan[t])]/(1 - e*t);
fe = Sqrt[(1+q^2 t^2)/(1+t^2)]*Exp[e*(ArcTan[q*t] - ArcTan[t])]/(1-e*t);
Q[n_] := If[OddQ[n], SeriesCoefficient[fo, {t, 0, n}], SeriesCoefficient[fe, {t, 0, n}]] // Expand;
b[n_] := n!*SeriesCoefficient[Sec[x] + Tan[x], {x, 0, n}];
P[n_] := (Q[n] /. e^k_Integer :> b[k]) /. e :> b[1] // Expand;
T[n_, k_] := Coefficient[P[n], q, k];
Table[CoefficientList[P[n], q], {n, 0, nmax}] // Flatten (* Jean-François Alcover, Jul 24 2018, from Maple *)

The row generating polynomials can be obtained from Proposition 6.1 of the Stanley reference (see the Maple program).

A303564 Number T(n,k) of derangements of [n] having exactly k peaks; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 1, 3, 6, 5, 33, 6, 11, 152, 102, 21, 663, 1068, 102, 43, 2778, 9060, 2952, 85, 11413, 68250, 50796, 2952, 171, 46332, 477978, 679368, 131112, 341, 186867, 3192192, 7824834, 3349224, 131112, 683, 750878, 20648088, 81751824, 64791576, 8271792

Offset: 0

Alois P. Heinz, Apr 26 2018

			T(5,0) = 5: 51234, 53124, 53214, 54123, 54213.
T(5,1) = 33: 21453, 21534, 23451, 23514, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34512, 34521, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45123, 45213, 51423, 51432, 53412, 53421, 54132, 54231.
T(5,2) = 6: 23154, 24153, 34152, 34251, 45132, 45231.
Triangle T(n,k) begins:
    1;
    0;
    1;
    1,      1;
    3,      6;
    5,     33,        6;
   11,    152,      102;
   21,    663,     1068,      102;
   43,   2778,     9060,     2952;
   85,  11413,    68250,    50796,     2952;
  171,  46332,   477978,   679368,   131112;
  341, 186867,  3192192,  7824834,  3349224,  131112;
  683, 750878, 20648088, 81751824, 64791576, 8271792;

Alois P. Heinz, Rows n = 0..20, flattened
Wikipedia, Derangement

Columns k=0-1 give: A001045(n-1) for n>0, A301272.
Row sums give A000166.
Cf. A008303 (the same for permutations), A004526, A129815, A129817, A162979, A162980, A216963, A303648 (the same for involutions).

b:= proc(s, i, j) option remember; expand(`if`(s={}, 1, add(
      `if`(k=nops(s), 0, b(s minus {k}, `if`(j>k, 0, j), k)*
      `if`(i>0 and j>0 and ik, x, 1)), k=s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, degree(p))))(b({$1..n}, 0$2)):
seq(T(n), n=0..12);

b[s_, i_, j_] := b[s, i, j] = Expand[If[s == {}, 1, Sum[If[k == Length[s], 0, b[s ~Complement~ {k}, If[j > k, 0, j], k]*If[i > 0 && j > 0 && i < j && j > k, x, 1]], {k, s}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Max[0, Exponent[p, x]]}]][b[Range[n], 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 31 2018, from Maple *)

T(2*n+1,n) = A129815(2*n+1) = A129817(2*n+1) = A162979(2*n+1,0) = A162980(2*n+1,0).

cp's OEIS Frontend

A129817 Number of alternating fixed-point-free permutations on n letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A162978 Number of fixed points in all alternating (i.e., down-up) permutations of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A162980 Triangle read by rows: T(n,k) is the number of reverse alternating (i.e., up-down) permutations of {1,2,...,n} having k fixed points (n >= 0, 0 <= k <= 1 + floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303564 Number T(n,k) of derangements of [n] having exactly k peaks; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula