A347601 a(n) is the number of positive Euler permutations of order n.

1, 0, 0, 2, 7, 16, 102, 1042, 8109, 63280, 642220, 7500626, 89458803, 1135216800, 15935870034, 241410428162, 3858227881945, 65327424977824, 1176448390679256, 22388999178300514, 447692501190569823, 9395318712874789744, 206713705368363820990, 4755693997171333347506

Offset

0,4

Comments

Let M be the tangent matrix of dimension n X n. The definition of the tangent matrix is given in A346831. An Euler permutation of order n is a permutation sigma of {1,...,n} if P = Product_{k=1..n} M(k, sigma(k)) does not vanish. We say sigma is a positive Euler permutation of order n (or sigma in EP(n)) if P = 1 and a negative Euler permutation of order n (or sigma in EN(n)) if P = -1.

a(n) = card(EP(n)), the number of positive Euler permutations of order n. A table of positive Euler permutations is given in A347766. Related sequences are A347599 (Genocchi permutations) and A347600 (Seidel permutations).

Links

Table of n, a(n) for n=0..23.

Formula

Let |S| denote the cardinality of a set S. Following identities hold for n >= 0:

a(n) + A347602(n) = |EP(n) | + |EN(n) | = A000166(n) (rencontres numbers),

a(2n) - A347602(2n) = |EP(2n)| - |EN(2n)| = A122045(n) (Euler numbers),

a(n) - A347602(n) = |EP(n) | - |EN(n) | = A347598(n).

Example

Illustrating the decomposition of the rencontres numbers and the Euler numbers:
The third column is the sum of the first two columns and the fourth column is the difference between the first two. The fourth column is the sum of the last two.
[n]  A347601     A347602      A000166       A347598      A122045   A347597
--------------------------------------------------------------------------
[ 0] 1,           0,           1,            1,          1,          [0]
[ 1] 0,           0,           0,            0,          0,          0,
[ 2] 0,           1,           1,           -1,         -1,          [0]
[ 3] 2,           0,           2,            2,          0,          2,
[ 4] 7,           2,           9,            5,          5,          [0]
[ 5] 16,          28,          44,          -12,         0,         -12,
[ 6] 102,         163,         265,         -61,        -61,         [0]
[ 7] 1042,        812,         1854,         230,        0,          230,
[ 8] 8109,        6724,        14833,        1385,       1385,       [0]
[ 9] 63280,       70216,       133496,      -6936,       0,         -6936,
[10] 642220,      692741,      1334961,     -50521,     -50521,      [0].

Maple

# Uses function TangentMatrix from A346831.
EulerPermutations := proc(n, sgn) local M, P, N, s, p, m;
   M := TangentMatrix(n); P := 0; N := 0;
   for p in Iterator:-Permute(n) do
      m := mul(M[k, p(k)], k = 1..n);
      if m =  0 then next fi;
      if m =  1 then P := P + 1 fi;
      if m = -1 then N := N + 1 fi; od;
   if sgn = 'pos' then P else N fi end:
A347601 := n -> `if`(n = 0, 1, EulerPermutations(n, 'pos')):
seq(A347601(n), n = 0..8);

Prog

(Julia)
using Combinatorics
function TangentMatrix(N)
    M = zeros(Int, N, N)
    H = div(N + 1, 2)
    for n in 1:N - 1
        for k in 0:n - 1
            M[n - k, k + 1] = n < H ? 1 : -1
            M[N - n + k + 1, N - k] = n < N - H ? -1 : 1
        end
    end
M end
function EulerPermutations(n, sgn)
    M = TangentMatrix(n)
    S = 0
    for p in permutations(1:n)
        sgn == prod(M[k, p[k]] for k in 1:n) && (S += 1)
    end
S end
PositiveEulerPermutations(n) = EulerPermutations(n, 1)

Crossrefs

Cf. A000166, A122045, A346831, A347597, A347598, A347602 (neg. perm.), A347766 (table), A347599, A347600, A346719 (bisection even indices).

Sequence in context: A079815 A362760 A325510 * A375880 A006883 A023269

Adjacent sequences: A347598 A347599 A347600 * A347602 A347603 A347604

Keyword

nonn

Author

Peter Luschny, Sep 10 2021

Status

approved