A247100 - OEIS

%I #71 Oct 11 2017 05:11:46

%S 1,2,4,9,21,51,127,324,844,2243,6073,16737,46905,133556,386062,

%T 1132107,3365627,10137559,30920943,95457178,298128278,941574417,

%U 3006040523,9697677885,31602993021,104001763258,345524136076,1158570129917,3919771027105,13377907523151

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

%C 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 Alois P. Heinz, <a href="/A247100/b247100.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = 1 + Sum_{k=1..ceiling(n/2)} binomial(n+1, 2k)*Bell(k), where Bell(x) refers to Bell numbers (A000110).

%e The labeled-run binary strings can be written as follows.

%e For n=1: 0, 1.

%e For n=2: 00, 01, 10, 11.

%e For n=3: 000, 001, 010, 100, 011, 110, 111, 101, 102.

%e 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 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 with(combinat):

%p a:= n-> (t-> add(binomial(t, 2*j)*bell(j), j=0..t/2))(n+1):

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Aug 10 2015

%t 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 Cf. A000110, A243634, A253409, A255706, A261041, A261134, A261489, A261492.

%K nonn

%O 0,2

%A _Andrew Woods_, Jan 01 2015

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