

A295928


Number of triangular matrices T(n,i,k), k <= i <= n, with entries "0" or "1" with the property that each triple {T(n,i,k), T(n,i,k+1), T(n,i1,k)} containing a single "0" can be successively replaced by {1, 1, 1} until finally no "0" entry remains.


1




OFFSET

1,2


COMMENTS

A triple {T(n,i,k), T(n,i,k+1), T(n,i1,k)} will be called a primitive triangle. It is easy to see that b(n) = n(n1)/2 is the number of such triangles. At each step, exactly one primitive triangle is completed (replaced by {1, 1, 1}). So there are b(n) "0" and n "1"terms. Thus the starting matrix has no complete primitive triangle. Furthermore, any triangular submatrix T(m,i,k), k <= i <= m < n cannot have more than m "1"terms because otherwise it would have less "0"terms than primitive triangles. The replacement of at least one "0"term would complete more than one primitive triangle. This has been excluded.
So T(n, i, k) is a special case of U(n, i, k), described in A101481: a(n) < A101481(n+1).
A start matrix may serve as a pattern for a number wall used on worksheets for elementary mathematics, see link "Number walls". That is why I prefer the more descriptive name "fill matrix".
The algorithm for the sequence is rather slow because each start matrix is constructed separately. There exists a faster recursive algorithm which produces the same terms and therefore is likely to be correct, but it is based on a conjecture. For the theory of the recurrence, see "Recursive aspects of fill matrices". Probable extension a(10)a(14): 821096828, 15804092592, 324709899276, 7081361097108, 163179784397820.
The number of fill matrices with n rows and all "1" terms concentrated on the last two rows, is A001960(n).
See link "Reconstruction of a sequence".


LINKS

Table of n, a(n) for n=1..9.
Gerhard Kirchner, Recursive aspects of fill matrices
Gerhard Kirchner, Number walls
Gerhard Kirchner, VBprogram
Gerhard Kirchner, Reconstruction of a sequence
Ville Salo, Cutting Corners, arXiv:2002.08730 [math.DS], 2020.


EXAMPLE

Example (n=2): 0 1 1
a(2)=3 1 1 0 1 1 0
Example for completing a 3matrix (3 bottom terms):
1 1 1 1
0 0 > 1 0 > 1 1 > 1 1
1 1 0 1 1 0 1 1 0 1 1 1
Example for a 3matrix which cannot be completed:
1 1
1 1 or 0 0
0 0 0 1 0 1


PROG

see link "VBprogram"


CROSSREFS

Cf. A101481, A001960.
Sequence in context: A200793 A141625 A053588 * A035352 A159607 A087018
Adjacent sequences: A295925 A295926 A295927 * A295929 A295930 A295931


KEYWORD

nonn,more


AUTHOR

Gerhard Kirchner, Nov 30 2017


STATUS

approved



