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
Examples
a(2) = 6 counts: (1#,1), (1,1#), (1#,2#), (2#,1#), (2#,2), (2,2#) where # denotes a mark.
Programs
-
PARI
a(n) = concat([0],Vec(n*x/(1-x*(1-x+n))+O('x^(n+1))))[n+1]
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).