cp's OEIS Frontend

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

%I A247100 #71 Oct 11 2017 05:11:46
%S A247100 1,2,4,9,21,51,127,324,844,2243,6073,16737,46905,133556,386062,
%T A247100 1132107,3365627,10137559,30920943,95457178,298128278,941574417,
%U A247100 3006040523,9697677885,31602993021,104001763258,345524136076,1158570129917,3919771027105,13377907523151
%N A247100 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.
%C A247100 Also the number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part. Example: For n=3 the a(3)=9 partitions are {}, 1, 2, 3, 12, 23, 13, 1|3, 123. - _Don Knuth_, Aug 07 2015
%H A247100 Alois P. Heinz, <a href="/A247100/b247100.txt">Table of n, a(n) for n = 0..1000</a>
%F A247100 a(n) = 1 + Sum_{k=1..ceiling(n/2)} binomial(n+1, 2k)*Bell(k), where Bell(x) refers to Bell numbers (A000110).
%e A247100 The labeled-run binary strings can be written as follows.
%e A247100 For n=1: 0, 1.
%e A247100 For n=2: 00, 01, 10, 11.
%e A247100 For n=3: 000, 001, 010, 100, 011, 110, 111, 101, 102.
%e A247100 For n=4: 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 0111, 1110, 1111, 0101, 0102, 1001, 1002, 1010, 1020, 1011, 1022, 1101, 1102.
%e A247100 For n=5, the original binary string 10101 can be written as 10101, 10102, 10201, 10202, or 10203 because there are 3 runs of ones and Bell(3)=5.
%p A247100 with(combinat):
%p A247100 a:= n-> (t-> add(binomial(t, 2*j)*bell(j), j=0..t/2))(n+1):
%p A247100 seq(a(n), n=0..30);  # _Alois P. Heinz_, Aug 10 2015
%t A247100 Table[1 + Sum[Binomial[n+1,2*k] * BellB[k],{k,1,Ceiling[n/2]}],{n,1,40}] (* _Vaclav Kotesovec_, Jan 08 2015 after _Andrew Woods_ *)
%Y A247100 Cf. A000110, A243634, A253409, A255706, A261041, A261134, A261489, A261492.
%K A247100 nonn
%O A247100 0,2
%A A247100 _Andrew Woods_, Jan 01 2015
%E A247100 a(0)=1 prepended by _Alois P. Heinz_, Aug 08 2015