A144017 Number of n X n X n alternating sign hypermatrices.

1, 1, 2, 14, 924, 852960

Offset: 0

Author

Samuel Zbarsky (sa_zbarsky(AT)yahoo.com), Sep 07 2008

Keywords

• nonn
• hard
• more

Comments

An alternating sign hypermatrix (ASHM) of order n is an n X n X n hypermatrix with entries from {0, 1, -1} such that the nonzero entries of each row, column, and vertical line alternate in sign, beginning and ending with +1.

ASHMs are the three-dimensional analog of alternating sign matrices and generalize Latin squares, as the set of n X n X n ASHMs containing no negative entries is in bijection with the set of n X n Latin squares.

Examples

			For n = 1, the only n X n X n ASHM is [[[1]]].
For n = 2, the two n X n X n ASHMs are
[[[1,0],
  [0,1]],
 [[0,1],
  [1,0]]]
and
[[[0,1],
  [1,0]],
 [[1,0],
  [0,1]]].
		

Links

• R. Brualdi and G. Dahl, Alternating sign matrices and hypermatrices, and a generalization of Latin squares, Advances in Applied Mathematics, 95 (2018), 116 - 151.
• Cian O'Brien, Alternating sign hypermatrix decompositions of Latin-like squares, Advances in Applied Mathematics, 121 (2020), 102097.

Crossrefs

3-dimensional analog of A005130, generalization of A002860.

Programs

Sage

# Program written in Sage
# Returns True if a given list of n n X n ASMs form an ASHM, returns False otherwise
def ASHM(L):
    n = len(L)
    # Searches through the vertical line in position (i,j) of the hypermatrix for each i and j
    for i in range(n):
        for j in range(n):
            # Since the first nonzero entry in each line of an ASHM is +1, the alternating condition is checked
            # as if the previous nonzero entry was -1
            last = -1
            for k in range(n):
                # In each position of the current vertical line, if the sign of the current entry is the opposite
                # of the previous, then the previous sign is updated
                if L[k][i,j]*last == -1:
                    last *= -1
                # Otherwise False is returned unless the current entry is 0
                elif L[k][i,j] != 0:
                    return False
            # If the most recent nonzero entry is not +1 by the time all entries have been checked, False is returned
            if last != 1:
                return False
    # If False has not been returned, return True
    return True
# Generates all combinations of one element from each list in L
def combos(L, current = [[]]):
    # If there are no elements left which have not been combined, then return the combinations already made
    if len(L) == 0:
        return current
    # Otherwise, each element of the next list in L is appended to the current list of combinations made
    output = []
    for K in current:
        for a in L[0]:
            output.append(K + [a])
    return combos(L[1:], output)
# Counts all ASHMs of order n
def count_ASHMs(n):
    # All ASMs of order n are imported as matrices
    asms = []
    for A in AlternatingSignMatrices(n):
        asms.append(A.to_matrix())
    # Initially, zero ASHMs have been counted
    count = 0
    # Every possible combination of n n X n ASMs is checked
    for i in combos([[k for k in range(len(asms))] for m in range(n)]):
        # If the current list of n n X n ASMs forms an ASHM, then it is counted
        count += int(ASHM([asms[i[k]] for k in range(n)]))
    # The final count is returned
    return count
# Note: I ran a more efficient version of this program in Python to obtain the answer for n=5, and even then it took 6 hours.
print(count_ASHMs(0))
print(count_ASHMs(1))
print(count_ASHMs(2))
print(count_ASHMs(3))
print(count_ASHMs(4))
print(count_ASHMs(5))
# Cian O'Brien, May 31 2023

Formula

Verified using 2 computer searches. The search given counts all sequences of n alternating sign matrices of order n that form an ASHM. The other search uses corner-sum matrices, which are known to be in bijection with alternating sign matrices, by counting all 3-dimensional analogs of corner-sum matrices.

Extensions

a(4) corrected and a(5) added, and definition updated by Cian O'Brien, May 31 2023