login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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