login
Triangle T(M, N): Number of M X N matrices where 1<N<=M, all elements are distinct, all elements are at least 0 and at most M*N-1, and every 2 X 2 block of elements has the same sum.
0

%I #47 Sep 27 2024 20:55:00

%S 24,112,376,768,2160,20352,5376,5904,86208,51840,64512,56736,1628352,

%T 1342656,44084736

%N Triangle T(M, N): Number of M X N matrices where 1<N<=M, all elements are distinct, all elements are at least 0 and at most M*N-1, and every 2 X 2 block of elements has the same sum.

%C This sequence is given in this order: (2,2), (3,2), (3,3), (4,2), (4,3), (4,4), etc.

%C The idea of the program below is that the first row, first column, and the (1,1)th element uniquely determine the rest of the matrix. Hence, all permutations of m+n integers in the range 0..m*n-1 are generated to fill the first row, first column, and (1,1). Then the empty spots in the matrix are filled in and if at any point a condition is violated (duplicate, < 0, >= M*N), the program immediately moves on to the next permutation.

%C Much of the conversation in the main chat room of the Programming Puzzles and Code Golf Stack Exchange site - the Nineteenth Byte - following the linked message in the Links section deals with finding the terms of this sequence.

%C Observation: at least the first 15 terms are divisible by 8. - _Omar E. Pol_, Oct 20 2015, Nov 21 2015

%C When M and N are both even, the block sum is 2(MN-1). When one or both is odd the block sum can vary: e.g., for M=N=3, it varies from 12 to 20. - _Peter J. Taylor_, Oct 21 2015

%C When M and N are both even, all solutions are toroidal: the block sums created by wrapping from the last column to the first column or the last row to the first row also equal 2(MN-1). When one of M or N is even, all solutions are cylindrical, with wrapping in the even dimension, but they are toroidal only in the trivial case of Odd X 2. When both M and N are odd, except in the trivial case of 1 X 1, solutions do not wrap in either direction. - _Peter J. Taylor_, Oct 21 2015

%H The Nineteenth Byte, <a href="http://chat.stackexchange.com/transcript/message/24811363#24811363">Originating chat message</a>, ChatRoom.

%e One 3 X 3 solution (with a sum of 19) is:

%e 0 4 2

%e 8 7 6

%e 3 1 5

%e One 4 X 4 solution (with a sum of 30) is:

%e 0 3 4 7

%e 12 15 8 11

%e 1 2 5 6

%e 13 14 9 10

%e One 5 X 5 solution (with a sum of 48) is:

%e 0 24 1 23 2

%e 9 15 8 16 7

%e 10 14 11 13 12

%e 19 5 18 6 17

%e 20 4 21 3 22

%e The triangle T(M, N) begins:

%e M\N 2 3 4 5 6 ...

%e 2: 24

%e 3: 112 376

%e 4: 768 2160 20352

%e 5: 5376 5904 86208 51840

%e 6: 64512 56736 1628352 1342656 44084736

%e ...reformatted. - _Wolfdieter Lang_, Dec 16 2015

%o (Python)

%o from itertools import permutations as P

%o n = 4; m = 4; permutes = P(range(m*n), m+n); counter = 0

%o for p in permutes:

%o grid = [p[:n]]

%o for i in range(m-1):

%o grid.append([p[n+i]]+[-1]*(n-1))

%o grid[1][1] = p[-1]

%o s = p[0]+p[1]+p[n]+p[-1]

%o has = list(p)

%o fail = 0

%o for y in range(1,m):

%o for x in range(1,n):

%o if x == y == 1: continue

%o r = s - (grid[y-1][x-1] + grid[y-1][x] + grid[y][x-1])

%o if r not in has and 0 <= r < m*n:

%o grid[y][x]=r

%o has.append(r)

%o else:

%o fail = 1

%o break

%o if fail: break

%o if not fail:

%o counter += 1

%o print(counter)

%K nonn,tabl,more

%O 2,1

%A _Lee Burnette_, Oct 20 2015