A355881 Table read by descending antidiagonals: T(k,n) (k >= 0, n>= 1) is number of ways to (k+2)-color a 3 X n grid ignoring the variations of two colors.

1, 1, 2, 1, 9, 3, 1, 41, 49, 4, 1, 187, 801, 169, 5, 1, 853, 13095, 7141, 441, 6, 1, 3891, 214083, 301741, 38897, 961, 7, 1, 17749, 3499929, 12749989, 3430789, 153921, 1849, 8, 1, 80963, 57218481, 538747549, 302602093, 24653151, 488401, 3249, 9

Offset: 0

Author

Gerhard Kirchner, Jul 24 2022

Keywords

• nonn
• tabl

Comments

With variations, the number of ways to color a 3 X 1 grid is (k+2)*(k+1)^2. The number of variations of two colors is (k+2)*(k+1). Therefore, T(k,1) = k+1. Only for k=1, the number of variations of two colors equals the number of permutations of all colors, see A020698.

T(0,n) = A000012(n) = constant 1

T(1,n) = A020698(n-1)

T(2,n) = A355882(n)

T(3,n) = A355883(n)

Examples

			Table begins:
k\n_1____2______3_________4___________5_____________6________________7
0:  1    1      1         1           1             1                1
1:  2    9     41       187         853          3891            17749
2:  3   49    801     13095      214083       3499929         57218481
3:  4  169   7141    301741    12749989     538747549      22764640981
4:  5  441  38897   3430789   302602093   26690078241    2354115497017
5:  6  961 153921  24653151  3948635061  632443246191  101296892084301
6:  7 1849 488401 129007867 34076567743 9001098120361 2377580042199049
		

Links

• Gerhard Kirchner, Derivation of the recurrence

Crossrefs

Cf. A000012, A020698, A355882, A355883.

Formula

T(k,n) = k*(k^2 + k + 3) * T(k,n-1) - (k^4 + k^3 + k^2-1) * T(k,n-2)

with T(k,1) = k+1, T(k,2) = (k^2+k+1)^2.

G.f.: x*(k + 1 - (k^2 + k - 1)*x) / (1 - k*(k^2 + k + 3)*x + (k^4 + k^3 + k^2 - 1)*x^2).