cp's OEIS Frontend

A253409 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.

%I A253409 #34 Jun 20 2017 22:37:08
%S A253409 1,2,4,10,28,86,282,984,3630,14138,57904,248854,1118554,5246980,
%T A253409 25619018,129961850,683561488,3722029314,20946195078,121671375312,
%U A253409 728511702462,4491224518274,28475638336144,185499720543262,1240358846060122,8505894459387628,59771243719783410
%N A253409 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 A253409 Included are the cases in which there are no zeros or no ones, producing an empty relation.
%H A253409 Alois P. Heinz, <a href="/A253409/b253409.txt">Table of n, a(n) for n = 0..647</a>
%F A253409 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 A253409 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 A253409 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 A253409 Cf. A000110, A247100.
%K A253409 nonn
%O A253409 0,2
%A A253409 _Andrew Woods_, Jan 01 2015
%E A253409 a(0)=1 prepended by _Alois P. Heinz_, Aug 08 2015