login
This site is supported by donations 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

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 17 09:45 EST 2018. Contains 297815 sequences.