login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A300729 Number of arrangements on a line of n finite closed intervals (possibly of zero length) with k distinct endpoints (n >= 1, 1 <= k <= 2*n). 1
1, 1, 1, 7, 12, 6, 1, 25, 138, 294, 270, 90, 1, 79, 1056, 5298, 12780, 16020, 10080, 2520, 1, 241, 7050, 70350, 334710, 875970, 1335600, 1184400, 567000, 113400, 1, 727, 44472, 817746, 6849900, 31500180, 87348240, 152643960, 169533000, 116235000, 44906400, 7484400 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

A122193(n,k) equals the number of arrangements on a line of n (nondegenerate) finite closed intervals having k distinct endpoints. The entries T(n,k) of the present table satisfy T(n,k) = A122193(n,k) + A122193(n,k+1). Proof. In an arrangement contributing to T(n,k) either the intervals are all nondegenerate, and there are A122193(n,k) arrangements of this type, or at least one of the intervals in the arrangement is degenerate. The following argument to show there are A122193(n,k+1) arrangements of the latter type is taken from the solution to the problem posed in the 'IBM Ponder This' link.

In an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints, the rightmost point is the right endpoint of one or more intervals. If we move each of these right endpoints to coincide with their corresponding left endpoint then we obtain an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length. The reverse mapping is clear: given an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length, take each interval of zero length and move all the right endpoints of these degenerate intervals to a single new rightmost point. This produces an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints. (End proof)

Most of the properties of the present table now follow from the properties of A122193.

Reading the table by antidiagonals produces A059515.

LINKS

Table of n, a(n) for n=1..42.

P. Bala, Deformations of the Hadamard product of power series

M. Dukes, C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.

IBM Ponder This, Jan 01 2001

FORMULA

T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i) * (i*(i+1)/2)^n for 0 <= k <= 2*n.

T(n,k) = A122193(n,k) + A122193(n,k+1).

T(n,k) = k*(k+1)/2*T(n-1,k) + k^2*T(n-1,k-1) + k*(k-1)/2*T(n-1,k-2) for 1 < k <= 2*n with boundary conditions T(0,0) = 1, T(0,n) = 0 for n >= 1; T(n,1) = 1 for n >= 1 and T(n,k) = 0 if k > 2*n.

Double e.g.f.: exp(-x)*Sum_{n>=0} exp( binomial(n+1,2)*y )* x^n/n! = 1 + (x + x^2/2!)*y + (x + 7*x^2/2! + 12*x^3/3! + 6*x^4/4!)*y^2/2! + ....

The n-th row of the table is given by the matrix product P^(-1)*v_n, where P denotes Pascal's triangle A007318 and v_n is the sequence (0, 1, 3^n, 6^n, 10^n, ...) regarded as an infinite column vector, where 1, 3, 6, 10, ... is the sequence of triangular numbers A000217. Cf. A087127 and A122193.

n-th row polynomial R(n,x) = (x + x^2) o ... o (x + x^2) (n factors) where o denotes the black diamond product of power series as defined by Dukes and White.

R(n,x) = Sum_{i >= 1} (i*(i+1)/2)^n*x^i/(1 + x)^(i+1) for n >= 1.

x*R(n,x) = (1 + x)* the n-th row polynomial of A122193 for n >= 1.

(1 + x)*R(n,x) = x * the n-th row polynomial of A087127 for n >= 1.

Sum_{k = 1..2*n} T(n,k)*binomial(x,k) = (binomial(x+1,2))^n for n >= 1.

Sum_{i = 1..n-1} (i*(i+1)/2)^m = Sum_{k = 1..2*m} T(m,k)*binomial(n,k+1) for m >= 1. See Example section below.

R(n,x) = 1/2^n*Sum_{k = 0..n} binomial(n,k)*F(n+k,x), where F(n,x) = Sum_{k = 0..n} k!*Stirling2(n,k)*x^k is the n-th Fubini polynomial, the n-th row polynomial of A131689.

R(n+1,x) = 1/2*(x + x^2) * (d/dx)^2 ( (x + x^2)*R(n,x) ).

R(n,x) = R(n,-1 - x).

The zeros of R(n,x) belong to the interval [-1, 0].

For n >= 1, the alternating sum of the n-th row equals 0.

EXAMPLE

Table begins

      |k=0   1   2     3     4      5      6      7     8

---------------------------------------------------------

  n=0 |  1

    1 |  0   1   1

    2 |  0   1   7    12     6

    3 |  0   1  25   138   294    270     90

    4 |  0   1  79  1056  5298  12780  16020  10080  2520

   ...

T(2,3) = 12: The 12 arrangements with 3 endpoints of two (possibly degenerate) intervals [a, A] and [b, B] 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.

Here, for example, the notation aA-b-B indicates a = A < b < B, so the interval [a, A] is degenerate and lies to the left of the nondegenerate interval [b, B].

Row 2: (1, 7, 12, 6)

(x*(x + 1)/2)^2 = C(x,1) + 7*C(x,2) + 12*C(x,3) + 6*C(x,4).

Row 3: (1, 25, 138, 294, 270, 90)

(x*(x + 1)/2)^3 = C(x,1) + 25*C(x,2) + 138*C(x,3) + 294*C(x,4) + 270*C(x,5) + 90*C(x,6).

Sums of powers of triangular numbers:

Sum_{i = 1..n-1} (i*(i+1)/2)^2 = C(n,2) + 7*C(n,3) + 12*C(n,4) + 6*C(n,5);

Sum_{i = 1..n-1} (i*(i+1)/2)^3 = C(n,2) + 25*C(n,3) + 138*C(n,4) + 294*C(n,5) + 270*C(n,6) + 90*C(n,7).

MAPLE

A300729 := proc (n, k)

add((-1)^(k-i)*binomial(k, i)*((1/2)*i*(i+1))^n, i = 0..k);

end proc:

for n from 0 to 8 do

seq(A300729(n, k), k = 0..2*n)

end do;

MATHEMATICA

T[0, 0] = 1; T[n_, k_] := Sum[(-1)^(k-i)*Binomial[k, i]*((1/2)*i*(i+1))^n, {i, 0, k}]; Table[T[n, k], {n, 1, 6}, {k, 1, 2 n}] // Flatten (* Jean-François Alcover, Mar 16 2018 *)

CROSSREFS

A059516 (row sums). Cf. A059515, A087127, A122193, A131689.

Sequence in context: A177999 A293220 A126710 * A152199 A293926 A180570

Adjacent sequences:  A300726 A300727 A300728 * A300730 A300731 A300732

KEYWORD

nonn,easy,tabf

AUTHOR

Peter Bala, Mar 12 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 03:14 EDT 2019. Contains 323539 sequences. (Running on oeis4.)