A384162 Number of length n words over an n-ary alphabet such that a single letter in every run of letters is marked.

1, 6, 45, 460, 5945, 92736, 1694329, 35487432, 838341009, 22054058290, 639434542021, 20260243575936, 696512594466793, 25822887652517970, 1027054229302256625, 43622499402922710256, 1970666970910292873249, 94353519890358073478880, 4772755056209685781141981

Offset

1,2

Links

Table of n, a(n) for n=1..19.

Formula

a(n) = [x^n] n*x/(1 - x*(1 - x + n)).

a(n) = Sum_{s} Product_{i=1..k} c_i * (n - 1 + [i,1]) where the sum is over all compositions of n, [c_1, c_2, ..., c_k].

Conjecture: a(n) = n * A342168(n-1).

Example

a(2) = 6 counts: (1#,1), (1,1#), (1#,2#), (2#,1#), (2#,2), (2,2#) where # denotes a mark.

Prog

(PARI)
a(n) = concat([0], Vec(n*x/(1-x*(1-x+n))+O('x^(n+1))))[n+1]

Crossrefs

Cf. A000312, A011782, A342168, A351016, A351638.

Sequence in context: A186925 A368793 A294642 * A346682 A109516 A245493

Adjacent sequences: A384159 A384160 A384161 * A384163 A384164 A384165

Keyword

nonn,easy

Author

John Tyler Rascoe, May 21 2025

Status

approved