|
| |
|
|
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,i-1,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,i-1,k)} will be called a primitive triangle. It is easy to see that b(n) = n(n-1)/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, VB-program
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 3-matrix (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 3-matrix which cannot be completed:
1 1
1 1 or 0 0
0 0 0 1 0 1
|
|
|
PROG
|
see link "VB-program"
|
|
|
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
|
| |
|
|
