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

Author

Shiyao Guo, Jan 25 2021

Keywords

• nonn

Comments

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

All terms are even.

Examples

			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.
		

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

Crossrefs

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