This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A379636 #49 Mar 15 2025 12:28:53 %S A379636 1,2,2,2,4,5,3,4,7,8,4,6,9,11,14,4,6,10,12,16,18,5,8,12,15,19,22,26,6, %T A379636 8,14,16,22,24,30,32,6,10,15,19,24,28,33,38,42,7,10,17,20,27,30,37,40, %U A379636 47,50,8,12,19,23,30,34,41,46,52,57,63,8,12,20,24,32 %N A379636 Triangle read by rows: T(n,k) (n >= k) is the maximum number of black cells in a n X k grid such that no black cell is edge-adjacent to more than one black cell. %C A379636 Two cells are edge-adjacent if they have a common edge. %C A379636 T(n,1) and the upper bound are shown by blackening the left two cells in each three consecutive cells (refer to T(8,1) example). %C A379636 If both n and k are even, T(n,k) is reached by checkerboard coloring. The upper bound follows from T(2,2) = 2. %C A379636 Suppose that k is odd. T(n,k) can be constructed by applying the T(n,1) construction on each odd-numbered row, and the coloring of even-numbered rows opposite to odd-numbered ones (refer to T(7,7) example). If n is even, the upper bound follows from T(n,k) <= T(n,k-1) + T(n,1). %C A379636 If n is odd, we choose an up-and-right path visiting cells a_1, a_2, ..., a_(n+k-1) in that order. Set a_1 as the lower-left corner and a_(n+k-1) as the upper-right corner. The edge a_(2i) - a_(2i+1) continues the previous direction. If a_(2i+1) is not on the upper edge or on the right edge, choose a_(2i+2) such that a_(2i+1) and a_(2i+2) are not both black; Suppose the contrary, and then a_(2i+1) and its upper and right neighbors are all black, a contradiction. %C A379636 Therefore we divide the grid into the upper-left and lower-right parts, each of which can be divided into 2 X 2 grids, so there are at most (n-1)*(k-1)/2 black cells. As for the path, the part not on the upper edge or on the right edge has no more than half black cells, while the edge part contains at most n cells, hence T(n,k) <= (n-1)*(k-1)/2 + (k-1)/2 + T(n,1) = n*(k-1)/2 + ceiling(2*n/3). %C A379636 The following example illustrates the colored grid and the corresponding path: %C A379636 XX_XX_XX_ ......XX_ %C A379636 __X__X__X ......_.. %C A379636 _X_XX_XX_ ....X_X.. %C A379636 X_X__X__X ...._.... %C A379636 X_X_X_XX_ X_X_X.... %C A379636 ___X_X__X _........ %C A379636 XX_X_X_X_ X........ %H A379636 Yifan Xie, <a href="/A379636/b379636.txt">Rows 1..100 of triangle, flattened</a> %F A379636 If n and k are both even, T(n,k) = n*k/2; %F A379636 If n is even and k is odd, T(n,k) = n*(k-1)/2 + ceiling(2*n/3); %F A379636 If n is odd and k is even, T(n,k) = k*(n-1)/2 + ceil(2*k/3); %F A379636 If n and k are both odd, T(n,k) = n*(k-1)/2 + ceiling(2*n/3). %e A379636 The triangle begins: %e A379636 n\k [1] [2] [3] [4] [5] [6] [7] %e A379636 [1] 1; %e A379636 [2] 2, 2; %e A379636 [3] 2, 4, 5; %e A379636 [4] 3, 4, 7, 8; %e A379636 [5] 4, 6, 9, 11, 14; %e A379636 [6] 4, 6, 10, 12, 16, 18; %e A379636 [7] 5, 8, 12, 15, 19, 22, 26; %e A379636 ... %e A379636 T(8,1) = 6: %e A379636 XX_XX_XX %e A379636 T(7,7) = 26: %e A379636 XX_X_XX %e A379636 __X_X__ %e A379636 XX_X_XX %e A379636 --X_X__ %e A379636 XX_X_XX %e A379636 __X_X__ %e A379636 XX_X_XX %o A379636 (PARI) T(n,k)=if(n%2==0 && k%2==0, n*k/2, if(n%2==0, n*(k-1)/2+ceil(2*n/3), if(k%2==0, k*(n-1)/2+ceil(2*k/3), n*(k-1)/2+ceil(2*n/3)))); %Y A379636 Cf. A260090 (where adjacency is defined by having a common vertex) %K A379636 nonn,tabl,easy %O A379636 1,2 %A A379636 _Yifan Xie_, Mar 12 2025