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

Author

Andrew Woods, Jan 01 2015

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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 *)

Formula

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

Extensions

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