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

Author

Thomas Scheuerle, Nov 24 2022

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• Bert Dobbelaere, Python program

Crossrefs

Cf. A000165, A358655.

Programs

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

Formula

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

Extensions

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