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, 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
Offset: 1
Examples
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).
Links
- Peter Bala, Deformations of the Hadamard product of power series
- M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
- IBM Ponder This, Jan 01 2001
- Helmut Prodinger, On Touchard's continued fraction and extensions: combinatorics-free, self-contained proofs , arXiv:1102.5186 [math.CO], 2011.
Programs
-
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 *)
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) = 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.
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
Comments