OFFSET
1,5
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
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.
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).
EXAMPLE
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)
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
PROG
(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
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.
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.
KEYWORD
AUTHOR
Stefano Spezia, May 19 2020
EXTENSIONS
Duplicate term removed by Stefano Spezia, Jun 03 2020
STATUS
approved