A358655 a(n) is the number of distinct scalar products which can be formed by pairs of signed permutations (V, W) of [n].

1, 2, 7, 24, 61, 111, 183, 281, 409, 571, 771, 1013, 1301, 1639, 2031, 2481, 2993, 3571, 4219, 4941, 5741, 6623, 7591, 8649, 9801, 11051, 12403, 13861, 15429, 17111, 18911, 20833, 22881, 25059, 27371, 29821, 32413, 35151, 38039, 41081, 44281, 47643

Offset: 0

Author

Thomas Scheuerle, Nov 25 2022

Keywords

• nonn
• easy

Comments

Let V be an n-vector of the numbers 1 to n in order and let W be an n-vector of any signed permutation of these numbers. Numbers in W may be either positive or negative. a(n) is the number of different values for the scalar product V*W for all possible W. We allow all combinations of positive and negative signs in W.

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 a vector of one vertex of such a permutohedron to the origin, and cut this permutohedron in slices by hyperplanes which are orthogonal to this vector such that in each slice lies at least one vertex of this permutohedron, then a(n) is the count of such slices obtained by this process.

a(n) is odd if the plane through the origin is occupied by vertices, this means A358629(n) > 0.

For n > 3 all possible planes are occupied by vertices and thus a nice formula ( see formula section ) exists.

The permutohedra for small n are:

n = 2 Octagon.

n = 3 Truncated cuboctahedron.

n = 4 Omnitruncated tesseract.

n = 5 Omnitruncated 5-cube.

Examples

			a(2) = 7
Columns in the table below:
A: Result of the scalar product.
B: Count of combinations for this result.
C: An example.
    A  B      C
    5  1  [ 2,  1]*[ 2, 1]
    4  1  [ 1,  2]*[ 2, 1]
    3  1  [ 2, -1]*[ 2, 1]
    0  2  [ 1, -2]*[ 2, 1]
   -3  1  [-2,  1]*[ 2, 1]
   -4  1  [-1, -2]*[ 2, 1]
   -5  1  [-2, -1]*[ 2, 1]
We have 7 rows. The sum over B is A000165(2).
For a(2) all vectors C are part of the vertices of an octagon.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• Thomas Scheuerle, The permutohedron for a(3) a truncated cuboctahedron.
• Thomas Scheuerle, The truncated cuboctahedron of a(3) with 24 planes intersecting in at least one vertex.
• Thomas Scheuerle, The octagon of a(2) with 7 planes intersecting in at least one vertex.
• Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Crossrefs

Cf. A000165, A188475, A358629.

Programs

Mathematica

LinearRecurrence[{4, -6, 4, -1}, {1, 2, 7, 24, 61, 111, 183, 281}, 50] (* Paolo Xausa, Oct 02 2024 *)

Formula

a(n) = (2*n^3 + 3*n^2 + n + 3)/3 = A188475(n), for n > 3 (because valid if A000165(n)/2 > A188475(n)).

From Stefano Spezia, Nov 28 2022: (Start)

G.f.: (1 - 2*x + 5*x^2 + 4*x^3 - 15*x^5 + 16*x^6 - 5*x^7)/(1 - x)^4.

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n > 7. (End)