login
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, and each run of zeros as an element in a second equivalence relation.
2

%I #34 Jun 20 2017 22:37:08

%S 1,2,4,10,28,86,282,984,3630,14138,57904,248854,1118554,5246980,

%T 25619018,129961850,683561488,3722029314,20946195078,121671375312,

%U 728511702462,4491224518274,28475638336144,185499720543262,1240358846060122,8505894459387628,59771243719783410

%N 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, and each run of zeros as an element in a second equivalence relation.

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

%H Alois P. Heinz, <a href="/A253409/b253409.txt">Table of n, a(n) for n = 0..647</a>

%F 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).

%e 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.

%t 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_ *)

%Y Cf. A000110, A247100.

%K nonn

%O 0,2

%A _Andrew Woods_, Jan 01 2015

%E a(0)=1 prepended by _Alois P. Heinz_, Aug 08 2015