A247100 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation.

1, 2, 4, 9, 21, 51, 127, 324, 844, 2243, 6073, 16737, 46905, 133556, 386062, 1132107, 3365627, 10137559, 30920943, 95457178, 298128278, 941574417, 3006040523, 9697677885, 31602993021, 104001763258, 345524136076, 1158570129917, 3919771027105, 13377907523151

Offset

0,2

Comments

Also the number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part. Example: For n=3 the a(3)=9 partitions are {}, 1, 2, 3, 12, 23, 13, 1|3, 123. - Don Knuth, Aug 07 2015

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) = 1 + Sum_{k=1..ceiling(n/2)} binomial(n+1, 2k)*Bell(k), where Bell(x) refers to Bell numbers (A000110).

Example

The labeled-run binary strings can be written as follows.
For n=1: 0, 1.
For n=2: 00, 01, 10, 11.
For n=3: 000, 001, 010, 100, 011, 110, 111, 101, 102.
For n=4: 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 0111, 1110, 1111, 0101, 0102, 1001, 1002, 1010, 1020, 1011, 1022, 1101, 1102.
For n=5, the original binary string 10101 can be written as 10101, 10102, 10201, 10202, or 10203 because there are 3 runs of ones and Bell(3)=5.

Maple

with(combinat):
a:= n-> (t-> add(binomial(t, 2*j)*bell(j), j=0..t/2))(n+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 10 2015

Mathematica

Table[1 + Sum[Binomial[n+1, 2*k] * BellB[k], {k, 1, Ceiling[n/2]}], {n, 1, 40}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)

Crossrefs

Cf. A000110, A243634, A253409, A255706, A261041, A261134, A261489, A261492.

Sequence in context: A168049 A001006 A086246 * A230556 A027057 A333105

Adjacent sequences: A247097 A247098 A247099 * A247101 A247102 A247103

Keyword

nonn

Author

Andrew Woods, Jan 01 2015

Extensions

a(0)=1 prepended by Alois P. Heinz, Aug 08 2015

Status

approved