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,3

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.

Links

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

Example

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

Prog

(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!) )); }

Crossrefs

Row sums of A351641.

The initial terms are similar to A206464.

Cf. A351200, A351638.

Sequence in context: A279544 A245898 A230662 * A206464 A089429 A049143

Adjacent sequences: A351639 A351640 A351641 * A351643 A351644 A351645

Keyword

nonn

Author

Andrew Howroyd, Feb 15 2022

Status

approved