login
A327913
Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.
3
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 22, 34, 22, 6, 1, 1, 7, 34, 76, 76, 34, 7, 1, 1, 8, 50, 152, 221, 152, 50, 8, 1, 1, 9, 70, 280, 557, 557, 280, 70, 9, 1, 1, 10, 95, 482, 1264, 1736, 1264, 482, 95, 10, 1, 1, 11, 125, 787, 2630, 4766, 4766, 2630, 787, 125, 11, 1
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
Manfred Krause, A simple proof of the Gale-Ryser theorem, American Mathematical Monthly, 1996.
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
Main diagonal is A029894.
Cf. A028657 (nonequivalent binary n X m matrices).
Sequence in context: A094526 A088699 A101515 * A028657 A053534 A104881
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Oct 30 2019
STATUS
approved