A358629 a(n) is the number of signed permutations W of V = (1, 2, ..., n) such that the dot product V*W = 0.

0, 2, 0, 16, 48, 558, 4444, 62246, 692598, 11722730, 196824592, 3896202680, 86626174698, 2018770217402, 51681142218502, 1418482891697258, 41404316055037624, 1304323691188387488, 43501661519771535260, 1538705372277647632786

Offset

1,2

Comments

Let V be an n-vector of the numbers 1 to n in sequence and let W be an n-vector of a signed permutation of these numbers. Numbers in W may be either positive or negative. a(n) is the number of vectors W which allow the scalar product V*W = 0. We include identity as a permutation. We allow all combinations of positive and negative signs in W; this means 2^n combinations of signs.

Another interpretation of this sequence: A signed permutohedron is also called the Coxeter permutohedron of the family C_n and has A000165(n) vertices. If we choose one vertex of such a permutohedron and define a hyperplane through the origin by the normal vector pointing from this vertex to the origin, then a(n) is the number of vertices which lie on this hyperplane.

The group G(r, n) is the group of n X n matrices such that there is exactly one nonzero entry in each row and column, and this entry is an r-th root of unity. Let the matrix M be a member of G(2, n) (hyperoctahedral group), then a(n) is the number of M where V'*(M*V) = 0 holds. Each vertex of our Coxeter permutohedron C_n corresponds to one such M acting as M*V. V is here an n-vector [1, 2, ..., n]. V' means the transpose of V.

Links

Table of n, a(n) for n=1..20.

Bert Dobbelaere, Python program

Formula

Trivially, a(n) <= n! * (2^n - 1). - Charles R Greathouse IV, Jan 07 2023

Example

The cases of a(4) = 16 are:
  [1, 2, 3, 4] * [-4,-1,-2, 3] = -4 - 2 -  6 + 12 = 0.
  [1, 2, 3, 4] * [-2,-3, 4,-1] = -2 - 6 + 12 -  4 = 0.
  [1, 2, 3, 4] * [-3,-4, 1, 2] = -3 - 8 +  3 +  8 = 0.
  [1, 2, 3, 4] * [-4,-3, 2, 1] = -4 - 6 +  6 +  4 = 0.
  [1, 2, 3, 4] * [-2, 1,-4, 3] = -2 + 2 - 12 + 12 = 0.
  [1, 2, 3, 4] * [-4, 3,-2, 1] = -4 + 6 -  6 +  4 = 0.
  [1, 2, 3, 4] * [-2, 1, 4,-3] = -2 + 2 + 12 - 12 = 0.
  [1, 2, 3, 4] * [-3, 4, 1,-2] = -3 + 8 +  3 -  8 = 0.
  [1, 2, 3, 4] * [ 4, 1, 2,-3] =  4 + 2 +  6 - 12 = 0.
  [1, 2, 3, 4] * [ 2, 3,-4, 1] =  2 + 6 - 12 +  4 = 0.
  [1, 2, 3, 4] * [ 3, 4,-1,-2] =  3 + 8 -  3 -  8 = 0.
  [1, 2, 3, 4] * [ 4, 3,-2,-1] =  4 + 6 -  6 -  4 = 0.
  [1, 2, 3, 4] * [ 2,-1, 4,-3] =  2 - 2 + 12 - 12 = 0.
  [1, 2, 3, 4] * [ 4,-3, 2,-1] =  4 - 6 +  6 -  4 = 0.
  [1, 2, 3, 4] * [ 2,-1,-4, 3] =  2 - 2 - 12 + 12 = 0.
  [1, 2, 3, 4] * [ 3,-4,-1, 2] =  3 - 8 -  3 +  8 = 0.

Prog

(PARI) a(n) = my(v=[1..n], nb=0); forperm(v, p, for (i=1, 2^(n-1)-1, my(w = vector(n, k, if (bittest(i, k-1), -p[k], p[k]))); if (v*w~ == 0, nb++); ); ); 2*nb; \\ Michel Marcus, Nov 30 2022
(PARI) a(n)=my(m=n-1, N=2^m-1, s); forperm(n, U, for(i=1, n, U[i]*=2*i); my(t=sum(i=1, n, U[i])/2); for(i=1, N, t+=U[valuation(i, 2)+1]*=-1; if(t==0, s++))); 2*s \\ Charles R Greathouse IV, Jan 07 2023

Crossrefs

Cf. A000165, A358655.

Sequence in context: A346119 A009266 A009246 * A338448 A012414 A098336

Adjacent sequences: A358626 A358627 A358628 * A358630 A358631 A358632

Keyword

nonn,more

Author

Thomas Scheuerle, Nov 24 2022

Extensions

a(12)-a(20) from Bert Dobbelaere, Jan 26 2023

Status

approved