login
Square array read by antidiagonals upwards: T(n,k) is the number of ways of choosing nonnegative numbers for k n-sided dice, k >= 0, n >= 1, so that summing the faces can give any integer from 0 to n^k - 1.
3

%I #24 Feb 18 2023 15:28:51

%S 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,15,1,1,1,1,1,7,1,105,

%T 1,1,1,1,1,1,71,1,945,1,1,1,1,1,10,1,1001,1,10395,1,1,1,1,1,3,280,1,

%U 18089,1,135135,1,1,1,1,1,7,15,15400,1,398959,1

%N Square array read by antidiagonals upwards: T(n,k) is the number of ways of choosing nonnegative numbers for k n-sided dice, k >= 0, n >= 1, so that summing the faces can give any integer from 0 to n^k - 1.

%C T(n,k) depends on n only through its prime signature. (See A118914.) For example, for fixed k, T(p*q^2,k) will be the same for any pair of distinct primes p and q. Hence we may define T(n,k) = R(s(n),k), where s(n) is the prime signature of n.

%C Also the number of Krasner factorizations of (x^(n^k)-1) / (x-1) into k polynomials each having n nonzero terms all with coefficient +1. (Krasner and Ranulac, 1937)

%H M. Krasner and B. Ranulac, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k31562/f397.item">Sur une propriété des polynomes de la division du cercle</a>, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.

%H Matthew C. Lettington and Karl Michael Schmidt, <a href="https://arxiv.org/abs/1910.02455">Divisor Functions and the Number of Sum Systems</a>, arXiv:1910.02455 [math.NT], 2019.

%F Use M to denote a (k-1)-element multiset of positive integers. Let U denote the (k-1)-element multiset whose elements all equal 1 and let N denote the (k-1)-element multiset whose elements all equal n. For i in M, let M_{i,j} denote the result of replacing i with j in M. Then T(1,k) = T(n,0) = 1, while for n > 1 and k > 0 we have T(n,k) = r(n,N) / (k-1)! where r(i,M) is given by the recurrence

%F r(i,U) = 1 for i > 1,

%F r(i,M) = Sum_{m in M} Sum_{d|i,d<i} r(m,M_{m,d}) for M != U.

%e There are 3 ways to assign numbers to two 4-sided dice:

%e {{0, 1, 2, 3}, {0, 4, 8, 12}},

%e {{0, 1, 8, 9}, {0, 2, 4, 6}},

%e {{0, 1, 4, 5}, {0, 2, 8, 10}}.

%e The northwest corner of T(n,k) begins:

%e 1 1 1 1 1 1 1 ... (s(1) = {})

%e 1 1 1 1 1 1 1 ... (s(2) = {1})

%e 1 1 1 1 1 1 1 ... (s(3) = {1})

%e 1 1 3 15 105 945 10395 ... (s(4) = {2})

%e 1 1 1 1 1 1 1 ... (s(5) = {1})

%e 1 1 7 71 1001 18089 398959 ... (s(6) = {1,1})

%e 1 1 1 1 1 1 1 ... (s(7) = {1})

%e 1 1 10 280 15400 1401400 190590400 ... (s(8) = {3})

%e 1 1 3 15 105 945 10395 ... (s(9) = {2})

%e 1 1 7 71 1001 18089 398959 ... (s(10) = {1,1})

%e 1 1 1 1 1 1 1 ... (s(11) = {1})

%e 1 1 42 3660 614040 169200360 69444920160 ... (s(12) = {1,2})

%e 1 1 1 1 1 1 1 ... (s(13) = {1})

%e 1 1 7 71 1001 18089 398959 ... (s(14) = {1,1})

%e 1 1 7 71 1001 18089 398959 ... (s(15) = {1,1})

%e 1 1 35 5775 2627625 2546168625 4509264634875 ... (s(16) = {4})

%e ...

%o (SageMath)

%o @cached_function

%o def r(i,M):

%o kminus1 = len(M)

%o u = tuple([1 for j in range(kminus1)])

%o if i > 1 and M == u:

%o return(1)

%o elif M != u:

%o divList = divisors(i)[:-1]

%o return(sum(r(M[j],tuple(sorted(M[:j]+tuple([d])+M[j+1:]))) for d in divList for j in range(kminus1)))

%o def T(n,k):

%o if n == 1 or k == 0:

%o return(1)

%o else:

%o return(r(n,tuple([n for j in range(k-1)]))) / factorial(k-1)

%Y For rows of index n = p^j, p prime, or equivalently, for rows of signature {j} we have T(p^2,k) = R({2},k) = A001147(k), T(p^3,k) = R({3},k) = A025035(k), T(p^4,k) = R({4},k) = A025036(k), and, generally, T(p^j,k) = R({j},k) = the k-th element of the j-th column of the square array A060540.

%Y For n = p * q, p and q distinct primes, we have T(p*q,k) = R({1,1},k) = |A002119(k)|.

%Y Column correspondences are T(n,2) = A273013(n) and T(n,3) = A131514(n).

%Y Cf. A118914.

%K nonn,tabl

%O 1,18

%A _William P. Orrick_, Jan 25 2023