A274651 Triangle read by rows: T(n,k), (1<=k<=n), in which each term is the least positive integer such that no row, column, diagonal, or antidiagonal contains a repeated term.

1, 2, 3, 4, 1, 2, 3, 5, 4, 6, 6, 2, 1, 3, 4, 5, 4, 6, 2, 7, 8, 7, 8, 3, 1, 6, 5, 9, 9, 6, 10, 5, 8, 3, 11, 7, 8, 11, 9, 4, 1, 7, 10, 6, 5, 12, 7, 13, 8, 2, 9, 4, 11, 10, 14, 10, 9, 5, 12, 3, 1, 2, 13, 7, 8, 11, 11, 12, 8, 13, 5, 4, 3, 10, 9, 15, 14, 16, 13, 10, 11, 7, 9, 2, 1, 12, 8, 5, 17, 15, 18

Offset: 1

Author

Omar E. Pol, Jul 02 2016

Keywords

• nonn
• tabl
• look

Comments

Analog of A269526, but note that this is a right triangle.

The same rule applied to an equilateral triangle gives A269526.

We construct the triangle by reading from left to right in each row, starting with T(1,1) = 1.

Presumably every diagonal and every column is also a permutation of the positive integers, but the proof does not seem so straightforward. Of course, neither the rows nor the antidiagonals are permutations of the positive integers, since they are finite in length.

Omar E. Pol's conjecture that every column and every diagonal of the triangle is a permutation of the positive integers is true: see the link in A274650 (duplicated below). - N. J. A. Sloane, Jun 07 2017

It appears that the numbers generally appear for the first time in or near the right border of the triangle.

Theorem 1: the middle diagonal gives A000012 (the all 1's sequence).

Theorem 2: all 1's are in the middle diagonal.

For the proofs of the theorems 1 and 2 see the proofs of the theorems 1 and 2 of A274650 since both sequences are essentially the same.

From Bob Selcoe, Feb 15 2017: (Start)

The columns and diagonal are permutations of the natural numbers. The proofs are essentially the same as the proofs given for the columns and rows (respectively) in A269526.

All coefficients j <= 4 eventually populate in a repeating pattern toward the "middle diagonal" (i.e., relatively near the 1's); this is because we can build the triangle by j in ascending order; that is, we can start by placing all the 1's in the proper cells, then add the 2's, 3's, 4's, 5's, etc. So for i >= 0: since the 1's appear at T(1+2i, 1+i), the 2's appear at T(2+8i, 1+4i), T(3+8i, 3+4i), T(5+8i, 2+4i) and T(6+8i, 4+4i). Accordingly, after the first five 3's appear (at T(2,2), T(4,1), T(5,4), T(7,3) and T(8,6)), the remaining 3's appear at T(11+8i, 5+4i), T(12+8i, 7+4i), T(16+8i, 8+4i) and T(17+8i, 10+4i). Similarly for 4's, after the first 21 appearances, 4's appear at T(44+8i, 21+4i), T(45+8i, 24+4i), T(47+8i, 23+4i) and T(48+8i, 26+4i). So starting at T(41,21), this 16-coefficient pattern repeats at T(41+8i, 21+4i):

n/k 21 22 23 24 25 26

41 1 3

42 2

43 3 1 2

44 4 3

45 2 1 4

46 2

47 4 1

48 3 4

where the next 1 appears at T(49,25), and the pattern repeats at that point from the top left (so T(49,26) = 3, T(50,25) = 2, etc.).

Conjecture: as n gets sufficiently large, all coefficients j>4 will appear in a repeating pattern, populating all rows and diagonals around smaller j's near the "middle diagonal" (while I can offer no formal proof, it appears very likely that this is the case). (End)

From Hartmut F. W. Hoft, Jun 12 2017: (Start)

T(2k+1,k+1) = 1, for all k>=0, and T(n,{n/2,(n+3)/2,(n-1)/2,(n+2)/2}) = 2, for all n>=1 with mod(n,8) = {2,3,5,6} respectively, and no 1's or 2's occur in other positions.

Proof by (recursive) picture:

Positions in the triangle that are empty and those containing the dots of the guiding diagonals contain numbers larger than two.

n\k 1 2 3 4 5 6 7 8 10 12 14 16 18 20 22 24

1 |1

2 |2 .

3 | 1 2

4 | .

5 | 2 1 .

6 | 2 .

7 | 1 .

8 |____________.

9 | |1 .

10 | |2 . .

11 | | 1 2 .

12 | | . .

13 | | 2 1 . .

14 | | 2 . .

15 | | 1 . .

16 |_____|______________._____.

17 | | |1 . .

18 | | |2 . . .

19 | | | 1 2 . .

20 | | | . . .

21 | | | 2 1 . . .

22 | | | 2 . . .

23 | | | 1 . . .

24 |_____|_______|____._______._____._______.

1 2 3 4 5 6 7 8 12 16 20 24

Consider the center of the triangle. In each octave of rows the columns in the first central quatrain contain a 1 and a 2, and the diagonals in the second central quatrain contain a 1 and a 2. Therefore, no 1's or 2's can occur in the respective downward quatrains of leading columns and trailing diagonals.

The sequence of rows containing 2's is A047447 (n mod 8 = {2,3,5,6}), those containing only 2's is A016825 (n mod 8 = {2,6}), those containing both 1's and 2's is A047621 (n mod 8 = {3,5}), those containing only 1's is A047522 (n mod 8 = {1,7}), and those containing neither 1's nor 2's is A008586 (n mod 8 = {0,4}).

(End)

Examples

			Triangle begins:
   1;
   2,  3;
   4,  1,  2;
   3,  5,  4,  6;
   6,  2,  1,  3,  4;
   5,  4,  6,  2,  7,  8;
   7,  8,  3,  1,  6,  5,  9;
   9,  6, 10,  5,  8,  3, 11,  7;
   8, 11,  9,  4,  1,  7, 10,  6,  5;
  12,  7, 13,  8,  2,  9,  4, 11, 10, 14;
  10,  9,  5, 12,  3,  1,  2, 13,  7,  8, 11;
  11, 12,  8, 13,  5,  4,  3, 10,  9, 15, 14, 16;
  13, 10, 11,  7,  9,  2,  1, 12,  8,  5, 17, 15, 18;
  ...
From _Omar E. Pol_, Jun 07 2017: (Start)
The triangle may be reformatted as an isosceles triangle so that the all 1's sequence (A000012) appears in the central column (but note that this is NOT the way the triangle is constructed!):
.
.                  1;
.                2,  3;
.              4,  1,  2;
.            3,  5,  4,  6;
.          6,  2,  1,  3,  4;
.        5,  4,  6,  2,  7,  8;
.      7,  8,  3,  1,  6,  5,  9;
.    9,  6, 10,  5,  8,  3, 11,  7;
.  8, 11,  9,  4,  1,  7, 10,  6,  5;
...
(End)
		

Links

• Michel Marcus, Table of n, a(n) for n = 1..20100
• F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.
• N. J. A. Sloane, Notes on A274650 and Proof by Non-Attacking Queens

Crossrefs

Cf. A001844 (indices of the 1's).

Cf. A000012 (middle diagonal).

Every diagonal and every column of the right triangle is a permutation of A000027.

Cf. A274650 is the same triangle but with every entry minus 1.

Other sequences of the same family are A269526, A274528, A274820, A274821, A286297, A288530, A288531.

Sequences mentioned in N. J. A. Sloane's proof are A000170, A274616 and A287864.

Cf. A008586, A016825, A047447, A047522, A047621. - Hartmut F. W. Hoft, Jun 12 2017

Programs

Mathematica

f[1,1] = 1; (* for 1 < n and 1 <= k <= n *)
f[n_,k_] := f[n,k] = Module[{vals=Sort[Join[Map[f[n, #]&, Range[1, k-1]], Map[f[#, k]&, Range[k, n-1]], Map[f[n-k+#, #]&, Range[1, k-1]], Map[f[n-#, k+#]&, Range[1, Floor[(n-k)/2]]]]], c}, c=Complement[Range[1, Last[vals]], vals]; If[c=={}, Last[vals]+1, First[c]]]
(* computation of rows 1 ... n of triangle *)
a274651[n_] := Prepend[Table[f[i, j], {i, 2, n}, {j, 1, i}], {1}]
Flatten[a274651[13]] (* data *)
TableForm[a274651[13]] (* triangle *)
(* Hartmut F. W. Hoft, Jun 12 2017 *)

Formula

T(n,k) = A274650(n-1,k-1) + 1.