A360440 Square array read by antidiagonals upwards: T(n,k), n>=0, k>=0, is the number of ways of choosing nonnegative numbers for k indistinguishable A063008(n)-sided dice so that it is possible to roll every number from 0 to (A063008(n))^k-1.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 15, 1, 1, 1, 1, 10, 71, 105, 1, 1, 1, 1, 42, 280, 1001, 945, 1, 1, 1, 1, 115, 3660, 15400, 18089, 10395, 1, 1, 1, 1, 35, 20365, 614040, 1401400, 398959, 135135, 1, 1

Offset: 0

Author

William P. Orrick, Feb 19 2023

Keywords

• nonn
• tabl

Comments

The number of configurations depends on the number of sides on the dice only through its prime signature. A063008 provides a canonical representative of each prime signature.

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

Examples

			A063008(2) = 4. 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 table begins:
  1  1    1       1          1              1                 1  ...
  1  1    1       1          1              1                 1  ...
  1  1    3      15        105            945             10395  ...
  1  1    7      71       1001          18089            398959  ...
  1  1   10     280      15400        1401400         190590400  ...
  1  1   42    3660     614040      169200360       69444920160  ...
  1  1  115   20365    6891361     3815893741     3141782433931  ...
  1  1   35    5775    2627625     2546168625     4509264634875  ...
  1  1  230  160440  299145000  1175153779800  8396156461492800  ...
  ...
The rows shown enumerate configurations for dice of 1, 2, 4, 6, 8, 12, 30, 16, and 24 sides, which represent the prime signatures {}, {1}, {2}, {1,1}, {3}, {2,1}, {1,1,1}, {4}, and {3,1}.
		

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

The concatenation of all prime signatures, listed in the order that corresponds to the rows of T(n,k), is A080577.

T(3,k) is |A002119(k)|. Starting with k = 1, T(1,k), T(2,k), T(4,k), and T(7,k) are given by columns 1-4 of A060540.

Row n is row A063008(n) of A360098.

Cf. A273013, A131514.

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 f(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)
# The following function produces the top left corner of the table:
def TArray(maxn,maxk):
    retArray = []
    primesList = []
    ptnSum = 0
    ptnItr = Partitions(ptnSum)
    ptn = ptnItr.first()
    n = 0
    while n <= maxn:
        if ptn == None:
            primesList.append(Primes()[ptnSum])
            ptnSum = ptnSum + 1
            ptnItr = Partitions(ptnSum)
            ptn = ptnItr.first()
        prdct = prod(primesList[j]^ptn[j] for j in range(len(ptn)))
        retArray.append([f(prdct,k) for k in range(maxk+1)])
        n = n + 1
        ptn = ptnItr.next(ptn)
    return(retArray)

Formula

T(n,k) = f(A063008(n),k), where f(n,k) is the table given by A360098.