A380392 Irregular triangle read by rows: T(n,k) is the number of n X n binary matrices containing k South-East paths of 1's connecting the top left and bottom right corners.

1, 1, 1, 13, 2, 1, 461, 26, 13, 8, 1, 2, 1, 61708, 1454, 953, 568, 325, 112, 178, 76, 22, 46, 48, 2, 16, 4, 4, 8, 8, 0, 1, 2, 1, 32348492, 340768, 279142, 168300, 125121, 44436, 81857, 24666, 25375, 28182, 19759, 4476, 17477, 4334, 7123, 6436, 4314, 1708, 5534

Offset

0,4

Comments

A South-East path of 1's in a binary matrix is a path of connected 1's with steps South (0,-1) and East (1,0). Here 1's are said to be connected if they are adjacent in the same row or column.

Conjecture: The average number of South-East paths of 1's in all n X n binary matrices is A001790(n-1)/A101926(n-1). - John Tyler Rascoe, Feb 21 2025

Links

John Tyler Rascoe, Rows n = 0..5, flattened

John Tyler Rascoe, Python program.

Example

Triangle begins:
     k=0   1   2  3  4  5  6
 n=0   1;
 n=1   1,  1;
 n=2  13,  2,  1;
 n=3 461, 26, 13, 8, 1, 2, 1;
 ...
For row n = 3 the possible South-East paths are:
 A.       B.       C.       D.       E.       F.
 [1 1 1]  [1 1 0]  [1 1 0]  [1 0 0]  [1 0 0]  [1 0 0]
 [0 0 1]  [0 1 1]  [0 1 0]  [1 1 1]  [1 1 0]  [1 0 0]
 [0 0 1]  [0 0 1]  [0 1 1]  [0 0 1]  [0 1 1]  [1 1 1]
The 3 X 3 matrix below does not contain any of the paths A-F so it is counted under T(3,0) = 461.
 [1 0 1]
 [1 1 1]
 [1 0 0]
The 3 X 3 matrix below contains paths A, B, and D so it is counted under T(3,3) = 8.
 [1 1 1]
 [1 1 1]
 [1 0 1]

Prog

(Python) # see links

Crossrefs

Cf. A000984 (row lengths), A001790, A002416 (row sums), A086266, A101926, A261242, A369285.

Sequence in context: A010223 A010222 A086266 * A217436 A040166 A100395

Adjacent sequences: A380389 A380390 A380391 * A380393 A380394 A380395

Keyword

nonn,tabf

Author

John Tyler Rascoe, Jan 23 2025

Status

approved