A129817 -id:A129817 - cp's OEIS frontend

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

0, 0, 1, 2, 6, 22, 102, 506, 2952, 18502, 131112, 991226, 8271792, 73176262, 703077552, 7121578106, 77437418112, 883521487942, 10726837356672, 136104948161786, 1825110309733632

Offset: 1

Vladeta Jovovic, May 20 2007

From Emeric Deutsch, Aug 06 2009: (Start)
Reverse alternating permutations are called also up-down permutations.
a(n) is also the number of reverse alternating permutations having exactly 1 fixed point (see the Stanley reference). Example: a(4)=2 because we have 1423 and 2314.
(End)

			a(4)=2 because we have 3412 and 2413. [_Emeric Deutsch_, Aug 06 2009]

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

Cf. A000111, A000166, A007779, A129817.

a(2n-1) = A129817(2n-1). [Emeric Deutsch, Aug 06 2009]

a(21) from Alois P. Heinz, Jun 11 2015

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

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 0, 2, 2, 1, 6, 6, 3, 1, 24, 24, 11, 2, 102, 102, 51, 15, 2, 528, 528, 252, 68, 9, 2952, 2952, 1476, 458, 89, 9, 19008, 19008, 9240, 2728, 493, 44, 131112, 131112, 65556, 20868, 4479, 621, 44, 1009728, 1009728, 495360, 152448, 31182, 4054, 265, 8271792, 8271792, 4135896, 1334928, 300954, 47670, 4959, 265

Offset: 0

Emeric Deutsch, Aug 06 2009

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

			T(5,2)=3 because we have 32415, 41325, and 52314.
Triangle starts:
    1;
    0,   1;
    1,   0;
    1,   1,   0;
    2,   2,   1;
    6,   6,   3,   1;
   24,  24,  11,   2;
  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, A129817, A162978, A162980.

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): 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^14 = a[14], E^15 = a[15], E^16 = a[16], 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]}, Q(n))) end do: for n from 0 to 13 do seq(coeff(P[n], q, j), j = 0 .. ceil((1/2)*n)) end do;

nmax = 13;
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;
a[n_] := n!*SeriesCoefficient[Sec[x] + Tan[x], {x, 0, n}];
P[n_] := (Q[n] /. e^k_Integer :> a[k]) /. e :> a[1] // Expand;
Table[Switch[n, 0, {1}, 1, {0, 1}, 2, {1, 0}, 3, {1, 1, 0}, , CoefficientList[P[n], q]] , {n, 0, nmax}] // Flatten (* _Jean-François Alcover, Jul 23 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).

A137590 Number of alternating full cycles on n letters.

Original entry on oeis.org

1, 0, 1, 1, 3, 10, 39, 173, 882, 5052, 32163, 225230, 1720635, 14240070, 126917155, 1211969509, 12345020175, 133604426410, 1530993953307, 18518559411876, 235785621577351, 3152221563324450, 44148864630732711, 646438923481545230, 9876859207608319344, 157195096511273995860

Offset: 1

Vladimir Shevelev, Apr 26 2008

nonn

a(n) is the number of full cycles pi of elements 1,2,...,n for which pi(1)pi(3)<...
Calculations show that A000111(n)/n gives a highly good approximation to a(n). Examples: A000111(8)/8=1385/8=173.1 while a(8)=173; A000111(12)/12=225230.4 while a(12)=225230.
For all n except 2, a(n) is also the number of full cycles pi of elements 1,2,...,n for which pi(1)>pi(2)..., although it is not obvious that the number of up-down cycles should be equal to the number of down-up cycles. See the Stanley link. - Justin M. Troyka, Jun 11 2015

			a(3)=1 because we have 231; a(4)=1 because we have 2413; a(5)=3 because we have 24153, 34251, and 45231. - _Emeric Deutsch_, Jul 03 2009

V. Shevelev, On connection between the numbers of permutations and full cycles with some restrictions on positions and up-down structure, arXiv:0803.2396 [math.CO], 2008-2010.
R. P. Stanley, Alternating permutations and symmetric functions, J. Combin. Theory Ser. A 114 (2007), 436-460.

Cf. A000111, A129815, A129817.

t[n_, 0] := If[n==0, 1, 0]; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, n-k];
e[n_] := t[n, n];
a[n_] := If[OddQ[n], (1/n) Sum[MoebiusMu[d] (-1)^((d-1)/2) e[n/d], {d, Divisors[n]}], k = IntegerExponent[n, 2]; m = n/2^k; If[m > 1, (1/n) Sum[ MoebiusMu[d] e[n/d], {d, Divisors[m]}], (1/n)(e[n]-1)]];
Array[a, 30] (* Jean-François Alcover, Jan 23 2019 *)

E(n) = if (n<1, n==0, n--; n! * polcoeff( 1 / (1 - sin(x + x * O(x^n))), n));
a(n) = if (n % 2, (1/n)*sumdiv(n, d, moebius(d)*(-1)^((d-1)/2)*E(n/d)), k = valuation(n, 2); m = n/2^k; if (m > 1, (1/n)*sumdiv(m, d, moebius(d)*E(n/d)), (1/n)*(E(n) - 1))); \\ Michel Marcus, Jun 14 2015

Write E(n) = A000111(n), the number of alternating permutations on n letters. If n is odd, then a(n) = (1/n) Sum_{d|n} mu(d) (-1)^{(d-1)/2} E(n/d). If n is even but not a power of 2, then write n = 2^k m where m is odd, and then a(n) = (1/n) Sum_{d|m} mu(d) E(n/d). If n is a power of 2 and n >= 4, then a(n) = (1/n) (E(n) - 1). It follows from these formulas that a(n) ~ E(n)/n. See the Stanley link. - Justin M. Troyka, Jun 11 2015

More terms from Justin M. Troyka, Jun 11 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A162979 Triangle read by rows: T(n,k) is the number of alternating (i.e., down-up) permutations of {1,2,...,n} having k fixed points (n >= 0, 0 <= k <= ceiling(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

A137590 Number of alternating full cycles on n letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions