|
%I #46 Mar 08 2024 12:15:33
%S 1,3,16,122,1188,13844,185448,2781348,45868268
%N 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.
%C 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.
%C So T(n, i, k) is a special case of U(n, i, k), described in A101481: a(n) < A101481(n+1).
%C 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".
%C 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.
%C The number of fill matrices with n rows and all "1"- terms concentrated on the last two rows, is A001960(n).
%C See link "Reconstruction of a sequence".
%H Gerhard Kirchner, <a href="/A295928/a295928.pdf">Recursive aspects of fill matrices</a>
%H Gerhard Kirchner, <a href="/A295928/a295928_1.pdf">Number walls</a>
%H Gerhard Kirchner, <a href="/A295928/a295928.txt">VB-program</a>
%H Gerhard Kirchner, <a href="/A295928/a295928_2.pdf">Reconstruction of a sequence</a>
%H Ville Salo, <a href="https://arxiv.org/abs/2002.08730">Cutting Corners</a>, arXiv:2002.08730 [math.DS], 2020.
%H Yuan Yao and Fedir Yudin, <a href="https://arxiv.org/abs/2402.13342">Fine Mixed Subdivisions of a Dilated Triangle</a>, arXiv:2402.13342 [math.CO], 2024.
%e Example (n=2): 0 1 1
%e a(2)=3 1 1 0 1 1 0
%e Example for completing a 3-matrix (3 bottom terms):
%e 1 1 1 1
%e 0 0 -> 1 0 -> 1 1 -> 1 1
%e 1 1 0 1 1 0 1 1 0 1 1 1
%e Example for a 3-matrix which cannot be completed:
%e 1 1
%e 1 1 or 0 0
%e 0 0 0 1 0 1
%o (Visual Basic) ' see link "VB-program"
%Y Cf. A101481, A001960.
%K nonn,more
%O 1,2
%A _Gerhard Kirchner_, Nov 30 2017
|
