login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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):
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
Sequence in context: A168049 A001006 A086246 * A230556 A027057 A333105
KEYWORD
nonn
AUTHOR
Andrew Woods, Jan 01 2015
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Aug 08 2015
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)