login
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.
12
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,1
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
LINKS
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.
EXAMPLE
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
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).
Sequence in context: A269776 A269619 A269435 * A223949 A224133 A228740
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Mar 02 2016
EXTENSIONS
Edited by M. F. Hasler, Feb 29 2020
STATUS
approved