A300729 -id:A300729 - cp's OEIS frontend

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

Henry Bottomley, Jan 19 2001

			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.

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

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

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

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 *)

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

A059515 Square array T(k,n) by antidiagonals, where T(k,n) is number of ways of placing n identifiable nonnegative intervals with a total of exactly k starting and/or finishing points.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 7, 1, 0, 0, 0, 12, 25, 1, 0, 0, 0, 6, 138, 79, 1, 0, 0, 0, 0, 294, 1056, 241, 1, 0, 0, 0, 0, 270, 5298, 7050, 727, 1, 0, 0, 0, 0, 90, 12780, 70350, 44472, 2185, 1, 0, 0, 0, 0, 0, 16020, 334710, 817746, 273378, 6559, 1, 0, 0, 0, 0, 0

Offset: 0

Henry Bottomley, Jan 19 2001

See A300729 for a triangular version of this array. - Peter Bala, Jun 13 2019

			Rows are: 1,0,0,0,0,..., 0,1,1,0,0,..., 0,1,7,12,6,..., 0,1,25,138,294,..., etc. T(1,1)=1 since if a is starting point of interval and A is end point then only possibility is aA (zero length). T(2,1)=1 since possibility is a-A (positive length). T(3,2)=12 since possibilities are: 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.

IBM Ponder This, Jan 01 2001

Sum of rows gives A059516. Columns include A000007, A057427, A058481, A059117. Final positive number in each row is A000680.

Cf. A300729.

T(k, n) = T(k - 2, n - 1) * k * (k - 1)/2 + T(k - 1, n - 1) * k^2 + T(k, n - 1) * k * (k + 1)/2 with T(0, 0) = 1 = lambda(k, n) + lambda(k + 1, n) where lambda is A059117(k, n).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula