The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 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). 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 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: combinatorics-free, self-contained proofs , arXiv:1102.5186 [math.CO], 2011. 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. 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      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 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

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.

Last modified September 30 21:27 EDT 2020. Contains 337440 sequences. (Running on oeis4.)