cp's OEIS Frontend

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

%I A300729 #21 Dec 02 2024 16:31:57
%S A300729 1,1,1,7,12,6,1,25,138,294,270,90,1,79,1056,5298,12780,16020,10080,
%T A300729 2520,1,241,7050,70350,334710,875970,1335600,1184400,567000,113400,1,
%U A300729 727,44472,817746,6849900,31500180,87348240,152643960,169533000,116235000,44906400,7484400
%N 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).
%C A300729 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.
%C A300729 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)
%C A300729 Most of the properties of the present table now follow from the properties of A122193.
%C A300729 Reading the table by antidiagonals produces A059515.
%H A300729 Peter Bala, <a href="/A131689/a131689.pdf">Deformations of the Hadamard product of power series</a>
%H A300729 M. Dukes and C. D. White, <a href="http://arxiv.org/abs/1603.01589">Web Matrices: Structural Properties and Generating Combinatorial Identities</a>, arXiv:1603.01589 [math.CO], 2016.
%H A300729 IBM Ponder This, <a href="https://research.ibm.com/haifa/ponderthis/challenges/January2001.html">Jan 01 2001</a>
%H A300729 Helmut Prodinger, <a href="https://arxiv.org/abs/1102.5186">On Touchard's continued fraction and extensions: combinatorics-free, self-contained proofs </a>, arXiv:1102.5186 [math.CO], 2011.
%F A300729 T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i) * (i*(i+1)/2)^n for 0 <= k <= 2*n.
%F A300729 T(n,k) = A122193(n,k) + A122193(n,k+1).
%F A300729 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.
%F A300729 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! + ....
%F A300729 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.
%F A300729 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.
%F A300729 R(n,x) = Sum_{i >= 1} (i*(i+1)/2)^n*x^i/(1 + x)^(i+1) for n >= 1.
%F A300729 x*R(n,x) = (1 + x)* the n-th row polynomial of A122193 for n >= 1.
%F A300729 (1 + x)*R(n,x) = x * the n-th row polynomial of A087127 for n >= 1.
%F A300729 Sum_{k = 1..2*n} T(n,k)*binomial(x,k) = (binomial(x+1,2))^n for n >= 1.
%F A300729 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.
%F A300729 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.
%F A300729 R(n+1,x) = 1/2*(x + x^2) * (d/dx)^2 ( (x + x^2)*R(n,x) ).
%F A300729 R(n,x) = R(n,-1 - x).
%F A300729 The zeros of R(n,x) belong to the interval [-1, 0].
%F A300729 For n >= 1, the alternating sum of the n-th row equals 0.
%F A300729 E.g.f. as a continued fraction: 1/(1 + (x + x^2)*(1 - exp(t))/(1 + (x + x^2)*(1 -exp(2*t))/(1 + (x + x^2)*(1 - exp(3*t))/(1 + ...)))) = 1 + (x + x^2)*t + (x + 7*x^2 + 12*x^3 + 6*x^4)*t^2/2! + ... (use Prodinger, equation 1.1). - _Peter Bala_, Jun 13 2019
%e A300729 Table begins
%e A300729       |k=0   1   2     3     4      5      6      7     8
%e A300729 ---------------------------------------------------------
%e A300729   n=0 |  1
%e A300729     1 |  0   1   1
%e A300729     2 |  0   1   7    12     6
%e A300729     3 |  0   1  25   138   294    270     90
%e A300729     4 |  0   1  79  1056  5298  12780  16020  10080  2520
%e A300729    ...
%e A300729 T(2,3) = 12: The 12 arrangements with 3 endpoints of two (possibly degenerate) intervals [a, A] and [b, B] are
%e A300729      aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB,
%e A300729      ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB.
%e A300729 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].
%e A300729 Row 2: (1, 7, 12, 6)
%e A300729 (x*(x + 1)/2)^2 = C(x,1) + 7*C(x,2) + 12*C(x,3) + 6*C(x,4).
%e A300729 Row 3: (1, 25, 138, 294, 270, 90)
%e A300729 (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).
%e A300729 Sums of powers of triangular numbers:
%e A300729 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);
%e A300729 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).
%p A300729 A300729 := proc (n, k)
%p A300729 add((-1)^(k-i)*binomial(k, i)*((1/2)*i*(i+1))^n, i = 0..k);
%p A300729 end proc:
%p A300729 for n from 0 to 8 do
%p A300729 seq(A300729(n, k), k = 0..2*n)
%p A300729 end do;
%t A300729 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 *)
%Y A300729 Cf. A059516 (row sums), A059515, A087127, A122193, A131689.
%K A300729 nonn,easy,tabf
%O A300729 1,4
%A A300729 _Peter Bala_, Mar 12 2018