OFFSET
0,5
COMMENTS
Only matrices in which both row and columns sums are weakly increasing need to be considered. If order is also considered then the number of possibilities is given by A328887(n, m).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325
Manfred Krause, A simple proof of the Gale-Ryser theorem, American Mathematical Monthly, 1996.
Wikipedia, Gale-Ryser theorem
EXAMPLE
Array begins:
=============================================
n\m | 0 1 2 3 4 5 6 7
----+----------------------------------------
0 | 1 1 1 1 1 1 1 1 ...
1 | 1 2 3 4 5 6 7 8 ...
2 | 1 3 7 13 22 34 50 70 ...
3 | 1 4 13 34 76 152 280 482 ...
4 | 1 5 22 76 221 557 1264 2630 ...
5 | 1 6 34 152 557 1736 4766 11812 ...
6 | 1 7 50 280 1264 4766 15584 45356 ...
7 | 1 8 70 482 2630 11812 45356 153228 ...
...
T(2,2) = 7. The following 7 matrices each have different row/column sums.
[0 0] [0 0] [0 1] [0 0] [0 1] [0 1] [1 1]
[0 0] [0 1] [1 0] [1 1] [0 1] [1 1] [1 1]
PROG
(PARI)
T(n, m)={local(Cache=Map());
my(F(b, c, t, w)=my(hk=Vecsmall([b, c, t, w]), z);
if(!mapisdefined(Cache, hk, &z),
z = if(w&&c, sum(i=0, b, sum(j=ceil((t+i)/w), min(t+i, c), self()(i, j, t+i-j, w-1))), !t);
mapput(Cache, hk, z)); z);
F(n, n, 0, m)
}
(Python) # After PARI implementation.
from functools import cache
@cache
def F(b, c, t, w):
if w == 0:
return 1 if t == 0 else 0
return sum(
sum(
F(i, j, t + i - j, w - 1)
for j in range((t + i - 1) // w, min(t + i, c) + 1)
)
for i in range(b + 1)
)
A327913 = lambda n, m: F(n, n, 0, m)
for n in range(10):
print([A327913(n, m) for m in range(0, 8)]) # Peter Luschny, Apr 09 2021
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Oct 30 2019
STATUS
approved