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(n-1,2k-1)*Bell(k)^2 + C(n-1,2k-2)*Bell(k)*Bell(k-1), where C(x,y) refers to binomial coefficients and Bell(x) refers to Bell numbers (A000110).
EXAMPLE
For n = 3, taking 3-bit binary strings and replacing zeros with ABC... and ones with 123... to represent equivalence relations, we have a(3) = 10 labeled-run binary strings: AAA, AA1, A1A, A1B, 1AA, A11, 11A, 111, 1A1, 1A2.
MATHEMATICA
Table[2 * Sum[Binomial[n-1, 2k-1] * BellB[k]^2 + Binomial[n-1, 2k-2] * BellB[k] * BellB[k-1], {k, 1, Ceiling[n/2]}], {n, 1, 30}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Woods, Jan 01 2015
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Aug 08 2015
STATUS
approved