|
|
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.
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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):
|
|
MATHEMATICA
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|