A059516 - OEIS

%I #20 Oct 27 2020 09:08:53

%S 1,2,26,818,47834,4488722,617364026,117029670578,29247820616474,

%T 9318336983422802,3686400233750527226,1772940711343815069938,

%U 1018732890334074636017114,689260602916515788253448082,542377407779814380777057527226,491141384755777675851883392430898

%N Number of different relations between n intervals (possibly of zero length) on a line.

%H Alois P. Heinz, <a href="/A059516/b059516.txt">Table of n, a(n) for n = 0..224</a>

%H IBM Ponder This, <a href="https://www.research.ibm.com/haifa/ponderthis/challenges/January2001.html">Jan 01 2001</a>

%F a(n) = 2*A055203(n)-0^n = Sum_k A059515(k, n).

%F a(n) = Sum_{m>=0} binomial(m+1,2)^n/2^(m+1). a(n) = (1/2^n)*Sum_{k=0..n} binomial(n,k)*A000670(n+k). - _Vladeta Jovovic_, Aug 17 2006

%F E.g.f. as a continued fraction: 1/(1 + 2*(1 - exp(t))/(1 + 2*(1 - exp(2*t))/(1 + 2*(1 - exp(3*t))/(1 + ...)))) = 1 + 2*t + 26*t^2/2! + .... See A300729. - _Peter Bala_, Jun 13 2019

%e a(1)=2 since if a is starting point of interval and A is end point then possibilities are aA (zero length) or a-A (positive length). a(2)=26 since possibilities are: aAbB, aAb-B, b-aAB, abB-A, a-AbB, ab-AB, aA-bB, bB-aA, aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB, ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB, a-A-b-B, a-b-A-B, a-b-B-A, b-B-a-A, b-a-B-A, b-a-A-B.

%p b:= proc(n) option remember; `if`(n=0, 1,

%p       add(b(n-j)*binomial(n, j), j=1..n))

%p     end:

%p a:= n-> add(b(n+k)*binomial(n, k), k=0..n)/2^n:

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Jul 10 2018

%t T[0, 0] = 1; T[n_, k_] := Sum[(-1)^(k-i) Binomial[k, i] (i(i+1)/2)^n, {i, 0, k}];

%t a[n_] := Sum[T[n, k], {k, 1, 2n}]; a[0] = 1;

%t a /@ Range[0, 20] (* _Jean-François Alcover_, Oct 27 2020, from A300729 *)

%Y Row n=2 of A316674. Row sums of A300729.

%K nonn,easy

%O 0,2

%A _Henry Bottomley_, Jan 19 2001