

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


3



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
H. Prodinger, On Touchard's continued fraction and extensions: combinatoricsfree, selfcontained proofs , arXiv:1102.5186 [math.CO], 2011.


FORMULA

T(n,k) = Sum_{i = 0..k} (1)^(ki)*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(n1,k) + k^2*T(n1,k1) + k*(k1)/2*T(n1,k2) 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 nth 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.
nth 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 nth row polynomial of A122193 for n >= 1.
(1 + x)*R(n,x) = x * the nth 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..n1} (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 nth Fubini polynomial, the nth 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 nth row equals 0.
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


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
aAbB, baAB, bBaA, bBaA, abBA, aAbB,
abAB, abBA, abAB, baAB, abAB, baAB.
Here, for example, the notation aAbB 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..n1} (i*(i+1)/2)^2 = C(n,2) + 7*C(n,3) + 12*C(n,4) + 6*C(n,5);
Sum_{i = 1..n1} (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)^(ki)*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)^(ki)*Binomial[k, i]*((1/2)*i*(i+1))^n, {i, 0, k}]; Table[T[n, k], {n, 1, 6}, {k, 1, 2 n}] // Flatten (* JeanFrançois Alcover, Mar 16 2018 *)


CROSSREFS

Cf. A059516 (row sums), 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



