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.
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
Offset: 0
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..647
Programs
-
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 *)
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).
Extensions
a(0)=1 prepended by Alois P. Heinz, Aug 08 2015
Comments