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, 3, 16, 122, 1188, 13844, 185448, 2781348, 45868268, 821096828, 15804092592, 324709899276, 7081361097108, 163179784397820, 3958519452109912, 100778473796398524

Offset: 1

Author

Gerhard Kirchner, Nov 30 2017

Keywords

• nonn
• more

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".

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

Examples

			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
		

Links

• Nicolas Bonichon and Pierre-Jean Morel Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
• 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.
• Juliette Schabanel, 3D permutations and triangle solitaire, 2025
• Yuan Yao and Fedir Yudin, Fine Mixed Subdivisions of a Dilated Triangle, arXiv:2402.13342 [math.CO], 2024.

Crossrefs

Cf. A101481, A001960.

Formula

From Juliette Schabanel, Apr 14 2025: (Start)

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).

a(n) ~ cn!e^(sqrt(12n))n^(5/12) (conjectured). (End)

Extensions

a(10)-a(16) from Juliette Schabanel, Apr 14 2025