A340885 Sum of subword complexity (number of nonempty distinct subwords) of all binary strings of length n.

0, 2, 10, 36, 114, 332, 916, 2428, 6242, 15652, 38460, 92916, 221256, 520332, 1210448, 2789100, 6372498, 14450420, 32547188, 72861376, 162211196, 359318644, 792287340, 1739623672, 3804904316, 8292351960, 18012452664, 39006099616, 84226667004, 181387693028, 389657293304

Offset

0,2

Comments

a(n)/(2^n) is the expected subword complexity of a random binary string of length n.

All terms are even.

Links

Shiyao Guo, Table of n, a(n) for n = 0..60

Shiyao Guo, C++ program used to compute values for n up to 60

Example

For n = 2 there are four possible binary strings: "aa", "ab", "ba", "bb", and their subword complexities are 2, 3, 3 and 2 respectively, and their sum = a(2) = 10.

Prog

(C++) // see link above

Crossrefs

Cf. A282949 (distinct complexity profiles), A094913 (maximum complexity), A134457 (numbers of strings achieving the maximum complexity).

Sequence in context: A244715 A212573 A100535 * A206622 A266942 A265844

Adjacent sequences: A340882 A340883 A340884 * A340886 A340887 A340888

Keyword

nonn

Author

Shiyao Guo, Jan 25 2021

Status

approved