A351644 Number of length n word structures with all distinct runs using at most 3 symbols.

1, 1, 2, 4, 9, 21, 46, 108, 223, 487, 1028, 2060, 4327, 8591, 16818, 33562, 64441, 122983, 232378, 443446, 816371, 1503517, 2775372, 5052186, 9116047, 16231929, 29182198, 51503788, 91032821, 158301653, 275776810, 479642780, 824964483, 1414293391, 2403093256, 4095230980

Offset: 0

Author

Andrew Howroyd, Feb 16 2022

Keywords

• nonn

Comments

Permuting the symbols will not change the structure.

Examples

			The a(1) = 1 word is 1.
The a(2) = 2 words are 11, 12.
The a(3) = 4 words are 111, 112, 122, 123.
The a(4) = 9 words are 1111, 1112, 1121, 1122, 1211, 1222, 1123, 1223, 1233.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A351018, A351641, A351643.

Programs

PARI

\\ See A351641 for R, S.
seq(n)={my(q=S(n), c=3); concat([1], sum(k=1, c, R(q^k-1)*sum(r=k, c, binomial(r, k)*(-1)^(r-k)/r!) )); }

Formula

a(n) = A351018(n) + A351643(n).

a(n) = Sum_{k=0..3} A351641(n,k).