

A253409


The number of ways to write an nbit binary string and then define each run of ones as an element in an equivalence relation, and each run of zeros as an element in a second equivalence relation.


2



1, 2, 4, 10, 28, 86, 282, 984, 3630, 14138, 57904, 248854, 1118554, 5246980, 25619018, 129961850, 683561488, 3722029314, 20946195078, 121671375312, 728511702462, 4491224518274, 28475638336144, 185499720543262, 1240358846060122, 8505894459387628, 59771243719783410
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Included are the cases in which there are no zeros or no ones, producing an empty relation.


LINKS

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


FORMULA

a(n) = 2 * Sum_{k=1..ceiling(n/2)} C(n1,2k1)*Bell(k)^2 + C(n1,2k2)*Bell(k)*Bell(k1), where C(x,y) refers to binomial coefficients and Bell(x) refers to Bell numbers (A000110).


EXAMPLE

For n = 3, taking 3bit binary strings and replacing zeros with ABC... and ones with 123... to represent equivalence relations, we have a(3) = 10 labeledrun binary strings: AAA, AA1, A1A, A1B, 1AA, A11, 11A, 111, 1A1, 1A2.


MATHEMATICA

Table[2 * Sum[Binomial[n1, 2k1] * BellB[k]^2 + Binomial[n1, 2k2] * BellB[k] * BellB[k1], {k, 1, Ceiling[n/2]}], {n, 1, 30}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)


CROSSREFS

Cf. A000110, A247100.
Sequence in context: A149829 A149830 A272484 * A027412 A030277 A149831
Adjacent sequences: A253406 A253407 A253408 * A253410 A253411 A253412


KEYWORD

nonn


AUTHOR

Andrew Woods, Jan 01 2015


EXTENSIONS

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


STATUS

approved



