|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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):
|
|
CROSSREFS
|
Cf. A028657 (nonequivalent binary n X m matrices).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|