A269656 T(n,k) = number of length-n 0..k arrays with no adjacent pair x,x+1 repeated: infinite square array read by falling antidiagonals.

2, 3, 4, 4, 9, 8, 5, 16, 27, 15, 6, 25, 64, 79, 26, 7, 36, 125, 253, 225, 42, 8, 49, 216, 621, 988, 626, 64, 9, 64, 343, 1291, 3065, 3816, 1710, 93, 10, 81, 512, 2395, 7686, 15036, 14596, 4605, 130, 11, 100, 729, 4089, 16681, 45590, 73348, 55344, 12259, 176, 12, 121

Offset: 1

Author

R. H. Hardin, Mar 02 2016

Keywords

• nonn
• tabl

Comments

The table could be extended to T(0,k) = T(n,0) = 1, since there is exactly one length-0 array {()} and exactly one length-n array with coefficients in 0..0, {(0,...,0)}, each of which satisfies the requirement. The "empirical" formulas for n = 1, ..., 5 are easily proved, cf., e.g., A269657. - M. F. Hasler, Feb 29 2020

Examples

			Table starts
    2     3      4       5        6         7          8          9         10
    4     9     16      25       36        49         64         81        100
    8    27     64     125      216       343        512        729       1000
   15    79    253     621     1291      2395       4089       6553       9991
   26   225    988    3065     7686     16681      32600      58833      99730
   42   626   3816   15036    45590    115902     259476     527576     994626
   64  1710  14596   73348   269472    803434    2061940    4725456    9911008
   93  4605  55344  355921  1587450   5556909   16359580   42277329   98674806
  130 12259 208196 1718569  9321628  38350583  129599404  377821501  981592964
  176 32320 777582 8259567 54569340 264117327 1025145474 3372803487 9756620832
Some solutions for n=6, k=4:
  1  2  2  3  1  0  3  3  3  3  1  2  3  4  3  3
  3  2  4  3  3  1  4  3  4  0  4  2  2  3  0  3
  2  3  1  3  2  2  4  2  0  1  0  3  2  3  0  2
  0  2  4  4  1  4  2  3  0  4  0  3  2  3  0  3
  4  2  0  1  4  4  2  1  1  2  4  0  0  3  2  1
  0  1  1  0  0  4  4  2  4  3  3  3  1  0  3  0
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..759

Crossrefs

Column 1 is A000125.

Row 1 is A000027(n+1).

Row 2 is A000290(n+1).

Row 3 is A000578(n+1).

Rows 4, ..., 7: A269657, A269658, A269659 and A269660 (see there for formulas).

Formula

Empirical for column k, apparently a recurrence of order (k+1)^2:

k=1: a(n) = (1/6)*n^3 + (5/6)*n + 1

k=2: [linear recurrence of order 9]

k=3: [order 16]

k=4: [order 25]

k=5: [order 36]

k=6: [order 49]

k=7: [order 64]

Empirical for row n:

n=1: a(n) = n + 1 = #{ v = (m); 0 <= m <= n }.

n=2: a(n) = n^2 + 2*n + 1 = (n+1)^2 = #{ v in {0..n}^2 }.

n=3: a(n) = n^3 + 3*n^2 + 3*n + 1 = (n+1)^3 = #{ v in {0..n}^3 }.

n=4: a(n) = n^4 + 4*n^3 + 6*n^2 + 3*n + 1 = (n+1)^4 - n, cf. A269657.

n=5: a(n) = n^5 + 5*n^4 + 10*n^3 + 7*n^2 + 2*n + 1 = (n+1)^5 - 3*n*(n+1).

n=6: a(n) = n^6 + 6*n^5 + 15*n^4 + 14*n^3 + 3*n^2 + 3*n.

n=7: a(n) = n^7 + 7*n^6 + 21*n^5 + 25*n^4 + 5*n^3 + 2*n^2 + 11*n - 8.

Extensions

Edited by M. F. Hasler, Feb 29 2020