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

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, 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, 18089, 1, 135135, 1, 1, 1, 1, 1, 7, 15, 15400, 1, 398959, 1

Offset: 1

Author

William P. Orrick, Jan 25 2023

Keywords

• nonn
• tabl

Comments

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.

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)

Examples

			There are 3 ways to assign numbers to two 4-sided dice:
 {{0, 1, 2, 3}, {0, 4, 8, 12}},
 {{0, 1, 8, 9}, {0, 2, 4,  6}},
 {{0, 1, 4, 5}, {0, 2, 8, 10}}.
The northwest corner of T(n,k) begins:
  1   1    1    1       1          1             1 ...     (s(1)  = {})
  1   1    1    1       1          1             1 ...     (s(2)  = {1})
  1   1    1    1       1          1             1 ...     (s(3)  = {1})
  1   1    3   15     105        945         10395 ...     (s(4)  = {2})
  1   1    1    1       1          1             1 ...     (s(5)  = {1})
  1   1    7   71    1001      18089        398959 ...     (s(6)  = {1,1})
  1   1    1    1       1          1             1 ...     (s(7)  = {1})
  1   1   10  280   15400    1401400     190590400 ...     (s(8)  = {3})
  1   1    3   15     105        945         10395 ...     (s(9)  = {2})
  1   1    7   71    1001      18089        398959 ...     (s(10) = {1,1})
  1   1    1    1       1          1             1 ...     (s(11) = {1})
  1   1   42  3660 614040  169200360   69444920160 ...     (s(12) = {1,2})
  1   1    1    1       1          1             1 ...     (s(13) = {1})
  1   1    7   71    1001      18089        398959 ...     (s(14) = {1,1})
  1   1    7   71    1001      18089        398959 ...     (s(15) = {1,1})
  1   1   35 5775 2627625 2546168625 4509264634875 ...     (s(16) = {4})
  ...
		

Links

• M. Krasner and B. Ranulac, Sur une propriété des polynomes de la division du cercle, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
• Matthew C. Lettington and Karl Michael Schmidt, Divisor Functions and the Number of Sum Systems, arXiv:1910.02455 [math.NT], 2019.

Crossrefs

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.

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

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

Cf. A118914.

Programs

SageMath

@cached_function
def r(i,M):
    kminus1 = len(M)
    u = tuple([1 for j in range(kminus1)])
    if i > 1 and M == u:
        return(1)
    elif M != u:
        divList = divisors(i)[:-1]
        return(sum(r(M[j],tuple(sorted(M[:j]+tuple([d])+M[j+1:]))) for d in divList for j in range(kminus1)))
def T(n,k):
    if n == 1 or k == 0:
        return(1)
    else:
        return(r(n,tuple([n for j in range(k-1)]))) / factorial(k-1)

Formula

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

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

r(i,M) = Sum_{m in M} Sum_{d|i,d

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.