A351642 Number of length n word structures with all distinct runs using an infinite alphabet.

1, 1, 2, 4, 10, 26, 74, 218, 668, 2116, 6928, 23254, 79998, 281694, 1011956, 3704900, 13815692, 52386978, 201787950, 789178950, 3130824160, 12589367840, 51287685476, 211557376938, 883067740514, 3728494418330, 15916998678040, 68672820917088, 299331260431104

Offset: 0

Author

Andrew Howroyd, Feb 15 2022

Keywords

• nonn

Comments

Permuting the symbols will not change the structure.

Equivalently, a(n) is the number of restricted growth strings [s(0), s(1), ..., s(n-1)] where s(0)=0 and s(i) <= 1 + max(prefix) for i >= 1 and all runs are distinct.

Examples

			The a(4) = 10 words are 1111, 1112, 1121, 1122, 1211, 1222, 1123, 1223, 1233, 1234.
		

Links

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

Crossrefs

Row sums of A351641.

The initial terms are similar to A206464.

Cf. A351200, A351638.

Programs

PARI

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