A377336 Square array read by antidiagonals: T(n,k) is the number of fully symmetric, k-celled, n-dimensional polyhypercubes; n >= 0, k >= 1.

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Author

Pontus von Brömssen, Oct 25 2024

Keywords

• nonn
• tabl

Comments

To be included, a polyhypercube should have all the 2^n*n! symmetries of the n-dimensional hypercube.

Let n >= 1 and m = A171977(n). Then T(n,k) = 0 if neither k nor k-1 is a multiple of m. Also, there exists a number K such that T(n,k) > 0 if k >= K and either k or k-1 is a multiple of m. In particular, T(n,k) > 0 for all sufficiently large k if and only if n is odd. Sketch of proof: Assume that the point of rotation of the symmetries is in the origin and that the center of each cell have integer or half-integer coordinates, depending on whether the point of rotation is in the center of a cell or at the common corner of 2^n cells. The number of cells that are equivalent to a given cell c is n!/(x_0!*x_1!*...)*2^(n-x_0), where x_1, x_2, ... are the frequencies of the absolute values of the nonzero coordinates of c and x_0 is the number of zero coordinates of c. It can be proved that this number is divisible by m unless c is the cell at the origin (in which case x_0 = n and there are no other equivalent cells). (It is sufficient to check the case where all nonzero coordinates have the same absolute value, i.e., that all numbers except 1 in the n-th row of A013609 are divisible by m; the other numbers are multiples of these.) Since either none or all of the cells equivalent to a given cell must be part of the polyhypercube, this proves the first part. For the second part, say that a cell where the absolute values of all coordinates are equal and nonzero is a corner cell, and that a cell with a single nonzero coordinate is a spike cell. Corner cells and spike cells come in sets of 2^n and 2*n equivalent cells, respectively, and the GCD of 2^n and 2*n is already equal to m. Assume that n >= 3 (the case n <= 2 is easily handled), that k >= (4*n-1)^n, and that either k or k-1 is a multiple of m. Start with a solid cube made up of (4*n-1)^n cells. Remove the central cell if k is even, so that the number of remaining cells is congruent to k (mod m). Since GCD(2^n,2*n) = m, we can remove at most 2*n-1 sets of 2^n equivalent corner cells each, until the number of remaining cells is congruent to k (mod 2*n). The resulting polyhypercube is still connected. Then add sets of 2*n spike cells until the total number of cells is equal to k. This proves the second part. The bound k >= (4*n-1)^n resulting from this construction is far from optimal.

Examples

			Array begins:
  n\k| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
  ---+-----------------------------------------------------------
   0 | 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   1 | 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2 | 1  0  0  1  1  0  0  1  2  0  0  3  2  0  0  5  4  0  0 12
   3 | 1  0  0  0  0  0  1  1  0  0  0  0  1  0  0  0  0  1  2  1
   4 | 1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  1  0  0  0
   5 | 1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0
   6 | 1  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0
   7 | 1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0
   8 | 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0
   9 | 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0
  10 | 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
		

Links

• Pontus von Brömssen, Table of n, a(n) for n = 0..5049 (first 100 antidiagonals)
• Index entries for sequences related to polyominoes.

Crossrefs

Cf. A013609, A142886 (2nd row), A171977, A330891, A376791 (3rd row).