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

Author

Hugo Pfoertner, Feb 02 2022

Keywords

• nonn
• tabl

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

Examples

			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;
		

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.

Crossrefs

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

Programs

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

PARI

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