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,13

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)

Links

Table of n, a(n) for n=0..54.

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.

Formula

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

Example

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

Prog

(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)

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.

Sequence in context: A334549 A333901 A054724 * A349350 A061494 A360161

Adjacent sequences: A360437 A360438 A360439 * A360441 A360442 A360443

Keyword

nonn,tabl

Author

William P. Orrick, Feb 19 2023

Status

approved