(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))
|