cp's OEIS Frontend

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.

%I A295928 #53 Apr 20 2025 10:47:29
%S A295928 1,3,16,122,1188,13844,185448,2781348,45868268,821096828,15804092592,
%T A295928 324709899276,7081361097108,163179784397820,3958519452109912,
%U A295928 100778473796398524
%N 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.
%C A295928 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 A295928 So T(n, i, k) is a special case of U(n, i, k), described in A101481: a(n) < A101481(n+1).
%C A295928 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 A295928 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 A295928 The number of fill matrices with n rows and all "1"- terms concentrated on the last two rows, is A001960(n).
%C A295928 See link "Reconstruction of a sequence".
%C A295928 Number of 3-permutations of size n avoiding the patterns (12,12) and (312, 231) (explicit bijection with fill matrices). - _Juliette Schabanel_, Apr 14 2025
%H A295928 Nicolas Bonichon and Pierre-Jean Morel <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.
%H A295928 Gerhard Kirchner, <a href="/A295928/a295928.pdf">Recursive aspects of fill matrices</a>
%H A295928 Gerhard Kirchner, <a href="/A295928/a295928_1.pdf">Number walls</a>
%H A295928 Gerhard Kirchner, <a href="/A295928/a295928.txt">VB-program</a>
%H A295928 Gerhard Kirchner, <a href="/A295928/a295928_2.pdf">Reconstruction of a sequence</a>
%H A295928 Ville Salo, <a href="https://arxiv.org/abs/2002.08730">Cutting Corners</a>, arXiv:2002.08730 [math.DS], 2020.
%H A295928 Juliette Schabanel, <a href="https://arxiv.org/abs/2502.14657"> 3D permutations and triangle solitaire</a>, 2025
%H A295928 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.
%F A295928 From _Juliette Schabanel_, Apr 14 2025: (Start)
%F A295928 G.f. satisfies T(x)-1-x=I^3(x)∆^3T(x)-3I^2(x)∆^2T(x)+ 3I(x)(∆T(x)-1) with ∆T(x) = (xT(x))' and T(x)= 1 +I(x)∆T(x) (proved).
%F A295928 a(n) ~ cn!e^(sqrt(12n))n^(5/12) (conjectured). (End)
%e A295928 Example (n=2):    0     1    1
%e A295928     a(2)=3       1 1   0 1  1 0
%e A295928 Example for completing a 3-matrix (3 bottom terms):
%e A295928     1        1       1       1
%e A295928    0 0  ->  1 0 ->  1 1 ->  1 1
%e A295928   1 1 0    1 1 0   1 1 0   1 1 1
%e A295928 Example for a 3-matrix which cannot be completed:
%e A295928     1        1
%e A295928    1 1  or  0 0
%e A295928   0 0 0    1 0 1
%o A295928 (Visual Basic) ' see link "VB-program"
%Y A295928 Cf. A101481, A001960.
%K A295928 nonn,more
%O A295928 1,2
%A A295928 _Gerhard Kirchner_, Nov 30 2017
%E A295928 a(10)-a(16) from _Juliette Schabanel_, Apr 14 2025