A342237 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that begin with a palindrome of two or more letters; n, k >= 1.

0, 0, 1, 0, 2, 1, 0, 3, 6, 1, 0, 4, 15, 14, 1, 0, 5, 28, 51, 30, 1, 0, 6, 45, 124, 165, 62, 1, 0, 7, 66, 245, 532, 507, 126, 1, 0, 8, 91, 426, 1305, 2164, 1551, 254, 1, 0, 9, 120, 679, 2706, 6605, 8788, 4683, 510, 1, 0, 10, 153, 1016, 5005, 16386, 33405, 35284, 14127, 1022, 1

Offset: 1

Author

Peter Kagey, Mar 06 2021

Keywords

• nonn
• tabl

Examples

			Table begins:
n\k | 1  2   3    4      5       6        7         8
----+------------------------------------------------
  1 | 0  1   1    1      1       1        1         1
  2 | 0  2   6   14     30      62      126       254
  3 | 0  3  15   51    165     507     1551      4683
  4 | 0  4  28  124    532    2164     8788     35284
  5 | 0  5  45  245   1305    6605    33405    167405
  6 | 0  6  66  426   2706   16386    99186    595986
  7 | 0  7  91  679   5005   35287   248731   1742839
  8 | 0  8 120 1016   8520   68552   551496   4415048
		

Links

• Peter Kagey, Antidiagonals n = 1..100, flattened

Crossrefs

Rows: A000918 (n=2), A248122 (n=3), A249629 (n=4), A249638 (n=5), A249639 (n=6), A249640 (n=7), A249641 (n=8), A249642 (n=9), A249643 (n=10).

Columns: A000384 (k=3), A007588 (k=4).

Formula

T(n,1) = 0.

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

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