|
%I #41 Mar 31 2024 17:26:28
%S 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,
%T 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,
%U 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
%N Array T read by ascending antidiagonals: T(n, k) = Sum_{d divides n} T(d, k-1) with T(n, 0) = 1.
%C T(n, k) is called the generalized divisor function (see Beekman).
%C 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
%D Richard Beekman, An Introduction to Number-Theoretic Combinatorics, Lulu Press 2017.
%H Stefano Spezia, <a href="/A334997/b334997.txt">First 150 antidiagonals of the array, flattened</a>
%H Richard Beekman, <a href="https://www.researchgate.net/publication/341090354_A_General_Solution_of_the_Ferris_Wheel_Problem">A General Solution of the Ferris Wheel Problem</a>.
%F T(n, k) = Sum_{d divides n} T(d, k-1) with T(n, 0) = 1 (see Theorem 3 in Beekman's article).
%F 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).
%F T(p^m, k) = binomial(m+k, k) for every prime p (see Lemma 2 in Beekman's article).
%e From _Gus Wiseman_, Aug 04 2022: (Start)
%e Array begins:
%e k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8
%e n=1: 1 1 1 1 1 1 1 1 1
%e n=2: 1 2 3 4 5 6 7 8 9
%e n=3: 1 2 3 4 5 6 7 8 9
%e n=4: 1 3 6 10 15 21 28 36 45
%e n=5: 1 2 3 4 5 6 7 8 9
%e n=6: 1 4 9 16 25 36 49 64 81
%e n=7: 1 2 3 4 5 6 7 8 9
%e n=8: 1 4 10 20 35 56 84 120 165
%e The T(4,5) = 21 chains:
%e (1,1,1,1,1) (4,2,1,1,1) (4,4,2,2,2)
%e (2,1,1,1,1) (4,2,2,1,1) (4,4,4,1,1)
%e (2,2,1,1,1) (4,2,2,2,1) (4,4,4,2,1)
%e (2,2,2,1,1) (4,2,2,2,2) (4,4,4,2,2)
%e (2,2,2,2,1) (4,4,1,1,1) (4,4,4,4,1)
%e (2,2,2,2,2) (4,4,2,1,1) (4,4,4,4,2)
%e (4,1,1,1,1) (4,4,2,2,1) (4,4,4,4,4)
%e The T(6,3) = 16 chains:
%e (1,1,1) (3,1,1) (6,2,1) (6,6,1)
%e (2,1,1) (3,3,1) (6,2,2) (6,6,2)
%e (2,2,1) (3,3,3) (6,3,1) (6,6,3)
%e (2,2,2) (6,1,1) (6,3,3) (6,6,6)
%e The triangular form T(n-k,k) gives the number of length k chains of divisors of n - k. It begins:
%e 1
%e 1 1
%e 1 2 1
%e 1 2 3 1
%e 1 3 3 4 1
%e 1 2 6 4 5 1
%e 1 4 3 10 5 6 1
%e 1 2 9 4 15 6 7 1
%e 1 4 3 16 5 21 7 8 1
%e 1 3 10 4 25 6 28 8 9 1
%e 1 4 6 20 5 36 7 36 9 10 1
%e 1 2 9 10 35 6 49 8 45 10 11 1
%e (End)
%t 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
%o (PARI) T(n, k) = if (k==0, 1, sumdiv(n, d, T(d, k-1)));
%o matrix(10, 10, n, k, T(n, k-1)) \\ to see the array for n>=1, k >=0; \\ _Michel Marcus_, May 20 2020
%Y 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.
%Y Column k = 2 of the array is A007425.
%Y Column k = 3 of the array is A007426.
%Y Column k = 4 of the array is A061200.
%Y The transpose of the array is A077592.
%Y The subdiagonal n = k + 1 of the array is A163767.
%Y The version counting all multisets of divisors (not just chains) is A343658.
%Y The strict case is A343662 (row sums: A337256).
%Y Diagonal n = k of the array is A343939.
%Y Antidiagonal sums of the array (or row sums of the triangle) are A343940.
%Y A067824(n) counts strict chains of divisors starting with n.
%Y A074206(n) counts strict chains of divisors from n to 1.
%Y A146291 counts divisors by Omega.
%Y A251683(n,k) counts strict length k + 1 chains of divisors from n to 1.
%Y A253249(n) counts nonempty chains of divisors of n.
%Y A334996(n,k) counts strict length k chains of divisors from n to 1.
%Y A337255(n,k) counts strict length k chains of divisors starting with n.
%Y Cf. A000005, A018892, A051026, A062319, A066959, A176029, A327527, A343652, A343656.
%K nonn,tabl,mult
%O 1,5
%A _Stefano Spezia_, May 19 2020
%E Duplicate term removed by _Stefano Spezia_, Jun 03 2020
|
