A334997 Array T read by ascending antidiagonals: T(n, k) = Sum_{d divides n} T(d, k-1) with T(n, 0) = 1.

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 3, 3, 4, 1, 1, 2, 6, 4, 5, 1, 1, 4, 3, 10, 5, 6, 1, 1, 2, 9, 4, 15, 6, 7, 1, 1, 4, 3, 16, 5, 21, 7, 8, 1, 1, 3, 10, 4, 25, 6, 28, 8, 9, 1, 1, 4, 6, 20, 5, 36, 7, 36, 9, 10, 1, 1, 2, 9, 10, 35, 6, 49, 8, 45, 10, 11, 1, 1, 6, 3, 16, 15, 56, 7, 64, 9, 55, 11, 12, 1

Offset: 1

Author

Stefano Spezia, May 19 2020

Keywords

• nonn
• tabl
• mult

Comments

T(n, k) is called the generalized divisor function (see Beekman).

As an array with offset n=1, k=0, T(n,k) is the number of length-k chains of divisors of n. For example, the T(4,3) = 10 chains are: 111, 211, 221, 222, 411, 421, 422, 441, 442, 444. - Gus Wiseman, Aug 04 2022

Examples

			From _Gus Wiseman_, Aug 04 2022: (Start)
Array begins:
       k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8
  n=1:  1   1   1   1   1   1   1   1   1
  n=2:  1   2   3   4   5   6   7   8   9
  n=3:  1   2   3   4   5   6   7   8   9
  n=4:  1   3   6  10  15  21  28  36  45
  n=5:  1   2   3   4   5   6   7   8   9
  n=6:  1   4   9  16  25  36  49  64  81
  n=7:  1   2   3   4   5   6   7   8   9
  n=8:  1   4  10  20  35  56  84 120 165
The T(4,5) = 21 chains:
  (1,1,1,1,1)  (4,2,1,1,1)  (4,4,2,2,2)
  (2,1,1,1,1)  (4,2,2,1,1)  (4,4,4,1,1)
  (2,2,1,1,1)  (4,2,2,2,1)  (4,4,4,2,1)
  (2,2,2,1,1)  (4,2,2,2,2)  (4,4,4,2,2)
  (2,2,2,2,1)  (4,4,1,1,1)  (4,4,4,4,1)
  (2,2,2,2,2)  (4,4,2,1,1)  (4,4,4,4,2)
  (4,1,1,1,1)  (4,4,2,2,1)  (4,4,4,4,4)
The T(6,3) = 16 chains:
  (1,1,1)  (3,1,1)  (6,2,1)  (6,6,1)
  (2,1,1)  (3,3,1)  (6,2,2)  (6,6,2)
  (2,2,1)  (3,3,3)  (6,3,1)  (6,6,3)
  (2,2,2)  (6,1,1)  (6,3,3)  (6,6,6)
The triangular form T(n-k,k) gives the number of length k chains of divisors of n - k. It begins:
  1
  1  1
  1  2  1
  1  2  3  1
  1  3  3  4  1
  1  2  6  4  5  1
  1  4  3 10  5  6  1
  1  2  9  4 15  6  7  1
  1  4  3 16  5 21  7  8  1
  1  3 10  4 25  6 28  8  9  1
  1  4  6 20  5 36  7 36  9 10  1
  1  2  9 10 35  6 49  8 45 10 11  1
(End)
		

References

• Richard Beekman, An Introduction to Number-Theoretic Combinatorics, Lulu Press 2017.

Links

• Stefano Spezia, First 150 antidiagonals of the array, flattened
• Richard Beekman, A General Solution of the Ferris Wheel Problem.

Crossrefs

Cf. A000217 (4th row), A000290 (6th row), A000292 (8th row), A000332 (16th row), A000389 (32nd row), A000537 (36th row), A000578 (30th row), A002411 (12th row), A002417 (24th row), A007318, A027800 (48th row), A335078, A335079.

Column k = 2 of the array is A007425.

Column k = 3 of the array is A007426.

Column k = 4 of the array is A061200.

The transpose of the array is A077592.

The subdiagonal n = k + 1 of the array is A163767.

The version counting all multisets of divisors (not just chains) is A343658.

The strict case is A343662 (row sums: A337256).

Diagonal n = k of the array is A343939.

Antidiagonal sums of the array (or row sums of the triangle) are A343940.

A067824(n) counts strict chains of divisors starting with n.

A074206(n) counts strict chains of divisors from n to 1.

A146291 counts divisors by Omega.

A251683(n,k) counts strict length k + 1 chains of divisors from n to 1.

A253249(n) counts nonempty chains of divisors of n.

A334996(n,k) counts strict length k chains of divisors from n to 1.

A337255(n,k) counts strict length k chains of divisors starting with n.

Cf. A000005, A018892, A051026, A062319, A066959, A176029, A327527, A343652, A343656.

Programs

Mathematica

T[n_,k_]:=If[n==1,1,Product[Binomial[Extract[Extract[FactorInteger[n],i],2]+k,k],{i,1,Length[FactorInteger[n]]}]]; Table[T[n-k,k],{n,1,13},{k,0,n-1}]//Flatten

PARI

T(n, k) = if (k==0, 1, sumdiv(n, d, T(d, k-1)));
matrix(10, 10, n, k, T(n, k-1)) \\ to see the array for n>=1, k >=0; \\ Michel Marcus, May 20 2020

Formula

T(n, k) = Sum_{d divides n} T(d, k-1) with T(n, 0) = 1 (see Theorem 3 in Beekman's article).

T(i*j, k) = T(i, k)*T(j, k) if i and j are coprime positive integers (see Lemma 1 in Beekman's article).

T(p^m, k) = binomial(m+k, k) for every prime p (see Lemma 2 in Beekman's article).

Extensions

Duplicate term removed by Stefano Spezia, Jun 03 2020