A390670 Triangle read by rows: T(n,k) is the number of irreducible words covering the alphabet [n] such that the maximal cardinality of C is k, where C is a subset of the alphabet such that all letters in C appear in weakly increasing order within the word.

1, 0, 1, 0, 1, 1, 0, 2, 4, 1, 0, 9, 15, 9, 1, 0, 80, 79, 64, 16, 1, 0, 1226, 705, 471, 185, 25, 1, 0, 29215, 10533, 4286, 1991, 426, 36, 1, 0, 1004864, 244406, 56173, 22446, 6389, 847, 49, 1, 0, 47241632, 8257368, 1134186, 294934, 93452, 16903, 1520, 64, 1

Offset

0,8

Comments

Here a word is irreducible if no letters can be removed without changing the maximal cardinality of C. The lengths of these words range from n to (n-1)*2.

Links

Table of n, a(n) for n=0..54.

Sean A. Irvine, Java program (github)

John Tyler Rascoe, Python code.

Christian Sievers, clingo program

Example

Triangle begins:
   k=0     1    2    3    4   5  6
 n=0 1;
 n=1 0,    1;
 n=2 0,    1,   1;
 n=3 0,    2,   4,   1;
 n=4 0,    9,  15,   9,   1;
 n=5 0,   80,  79,  64,  16,  1;
 n=6 0, 1226, 705, 471, 185, 25, 1;
...
The word (3,2,4,1,3,2) has subset C of largest size 1 and removing any of the repeated letters will change that, so this word is counted under T(4,1) = 9.
T(3,1) = 2: (2,3,1,2), (3,2,1).
T(3,2) = 4: (1,3,2), (2,1,3), (2,3,1), (3,1,2).
T(3,3) = 1: (1,2,3).

Prog

(Python) # see links
(clingo) % see links

Crossrefs

Cf. A000290 (empirical 2nd diagonal).

Cf. A386891, A387336.

Sequence in context: A378394 A094344 A211183 * A137391 A276207 A248672

Adjacent sequences: A390667 A390668 A390669 * A390671 A390672 A390673

Keyword

nonn,tabl,more

Author

John Tyler Rascoe, Nov 14 2025

Extensions

a(28)-a(44) from Sean A. Irvine, Nov 28 2025

a(45)-a(54) (row n=9) from Christian Sievers, Nov 30 2025

Status

approved