A360412 Number of binary words of length 2n with an even number of 1's which are not shuffle squares.

0, 0, 2, 10, 46, 192, 780, 3090, 12136, 47100, 181820, 697856, 2667642, 10157814, 38563342, 146002012, 551483230, 2078722874, 7821121318, 29378487188

Offset

0,3

Comments

A shuffle square is a word obtained by self-shuffling, e.g., the French word "tuteurer" is a shuffle square as it can be obtained by self-shuffling the word "tuer".

Words with an odd number of 1's obviously are not shuffle squares.

Links

Table of n, a(n) for n=0..19.

Formula

a(n) = 2^(2n-1) - A191755(n), since the number of binary words of length 2n with an even number of 1's is 2^(2n-1).

Example

a(3)=10, since the binary words of length 6 with an even number of 1's which are not shuffle squares are 000110, 010001, 011000, 011101, 011110, 100001, 100010, 100111, 101110 and 111001.

Crossrefs

Cf. A191755.

Sequence in context: A373913 A212387 A191813 * A181294 A080643 A032389

Adjacent sequences: A360409 A360410 A360411 * A360413 A360414 A360415

Keyword

nonn,more

Author

Bartlomiej Pawlik, Feb 07 2023

Status

approved