A342239 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that are bifix free; n >= 1, k >= 1.

1, 2, 0, 3, 2, 0, 4, 6, 4, 0, 5, 12, 18, 6, 0, 6, 20, 48, 48, 12, 0, 7, 30, 100, 180, 144, 20, 0, 8, 42, 180, 480, 720, 414, 40, 0, 9, 56, 294, 1050, 2400, 2832, 1242, 74, 0, 10, 72, 448, 2016, 6300, 11900, 11328, 3678, 148, 0, 11, 90, 648, 3528, 14112, 37620, 59500, 45132, 11034, 284, 0

Offset

1,2

Links

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

Formula

T(n,0) = n.

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

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

Example

Table begins:
n\k | 1  2   3    4     5      6       7        8         9
----+------------------------------------------------------
  1 | 1  0   0    0     0      0       0        0         0
  2 | 2  2   4    6    12     20      40       74       148
  3 | 3  6  18   48   144    414    1242     3678     11034
  4 | 4 12  48  180   720   2832   11328    45132    180528
  5 | 5 20 100  480  2400  11900   59500   297020   1485100
  6 | 6 30 180 1050  6300  37620  225720  1353270   8119620
  7 | 7 42 294 2016 14112  98490  689430  4823994  33767958
  8 | 8 56 448 3528 28224 225344 1802752 14418488 115347904

Crossrefs

Rows: A003000 (n=2), A019308 (n=3), A019309 (n=4).

Columns: A002378 (k=1), A045991 (k=2), A047927 (k=3).

Sequence in context: A115241 A342238 A154559 * A269133 A143324 A287416

Adjacent sequences: A342236 A342237 A342238 * A342240 A342241 A342242

Keyword

nonn,tabl

Author

Peter Kagey, Mar 06 2021

Status

approved