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

1, 2, 26, 818, 47834, 4488722, 617364026, 117029670578, 29247820616474, 9318336983422802, 3686400233750527226, 1772940711343815069938, 1018732890334074636017114, 689260602916515788253448082, 542377407779814380777057527226, 491141384755777675851883392430898

Offset: 0

Author

Henry Bottomley, Jan 19 2001

Keywords

• nonn
• easy

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..224
• IBM Ponder This, Jan 01 2001

Crossrefs

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

Programs

Maple

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> add(b(n+k)*binomial(n, k), k=0..n)/2^n:
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 10 2018

Mathematica

T[0, 0] = 1; T[n_, k_] := Sum[(-1)^(k-i) Binomial[k, i] (i(i+1)/2)^n, {i, 0, k}];
a[n_] := Sum[T[n, k], {k, 1, 2n}]; a[0] = 1;
a /@ Range[0, 20] (* Jean-François Alcover, Oct 27 2020, from A300729 *)

Formula

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

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

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