A351145 Triangle T(n,m) read by rows: Sum_{k=1..m} binomial(2*n, n+k)*d(k), m<=n, with d(k)=A000005(k).

1, 4, 6, 15, 27, 29, 56, 112, 128, 131, 210, 450, 540, 570, 572, 792, 1782, 2222, 2420, 2444, 2448, 3003, 7007, 9009, 10101, 10283, 10339, 10341, 11440, 27456, 36192, 41652, 42772, 43252, 43284, 43288, 43758, 107406, 144534, 170238, 176358, 179622, 179928, 180000, 180003

Offset

1,2

Comments

Exercise 52 in chapter 5.2.2 of Knuth's TAOCP 3 asks: "What is the asymptotic behavior of the sum S_n = Sum_{t>=1} binomial(2n,n+t)*d(t)?" and mentions "This question arises in connection with the analysis of a tree traversal algorithm, exercise 2.3.1-11."

References

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.2 Sorting by Exchanging, pages 138, 637 (answer to exercise 52). Addison-Wesley, Reading, MA, 1998.

Links

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

Example

The triangle begins:
      1;
      4,     6;
     15,    27,    29;
     56,   112,   128,   131;
    210,   450,   540,   570,   572;
    792,  1782,  2222,  2420,  2444,  2448;
   3003,  7007,  9009, 10101, 10283, 10339, 10341;
  11440, 27456, 36192, 41652, 42772, 43252, 43284, 43288;

Mathematica

T[n_, m_] := Sum[Binomial[2*n, n + k] * DivisorSigma[0, k], {k, 1, m}]; Table[T[n, m], {n, 1, 9}, {m, 1, n}] // Flatten (* Amiram Eldar, Feb 02 2022 *)

Prog

(PARI) for(n=1, 10, for(m=1, n, my(s=sum(t=1, m, binomial(2*n, n+t)*numdiv(t))); print1(s, ", ")))

Crossrefs

Cf. A000005, A001791 (first column), A351146 (diagonal).

Sequence in context: A358438 A045907 A254325 * A034299 A007135 A294070

Adjacent sequences: A351142 A351143 A351144 * A351146 A351147 A351148

Keyword

nonn,tabl

Author

Hugo Pfoertner, Feb 02 2022

Status

approved