This site is supported by donations to The OEIS Foundation.

 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 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 A148071 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

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

Last modified October 19 00:36 EDT 2018. Contains 316327 sequences. (Running on oeis4.)