A002119 -id:A002119 - cp's OEIS frontend

A360439 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 (p^nq)-sided dice so that it is possible to roll every number from 0 to (p^nq)^k-1, where p and q are distinct primes.

1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 42, 71, 1, 1, 1, 230, 3660, 1001, 1, 1, 1, 1190, 160440, 614040, 18089, 1, 1, 1, 5922, 6387150, 299145000, 169200360, 398959, 1, 1, 1, 28644, 238504266, 127534407000, 1175153779800, 69444920160, 10391023, 1

Offset: 0

William P. Orrick, Feb 18 2023

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

			For two ten-sided dice we have k = 2 and n = 1 since 10 = 2^1*5. The seven configurations are
  {{0,1,2,3,4,5,6,7,8,9}, {0,10,20,30,40,50,60,70,80,90}},
  {{0,1,2,3,4,50,51,52,53,54}, {0,5,10,15,20,25,30,35,40,45}},
  {{0,1,2,3,4,25,26,27,28,29}, {0,5,10,15,20,50,55,60,65,70}},
  {{0,1,10,11,20,21,30,31,40,41}, {0,2,4,6,8,50,52,54,56,58}},
  {{0,1,20,21,40,41,60,61,80,81}, {0,2,4,6,8,10,12,14,16,18}},
  {{0,1,2,3,4,10,11,12,13,14}, {0,5,20,25,40,45,60,65,80,85}},
  {{0,1,4,5,8,9,12,13,16,17}, {0,2,20,22,40,42,60,62,80,82}}.
Array begins:
  1  1      1           1                  1                         1  ...
  1  1      7          71               1001                     18089  ...
  1  1     42        3660             614040                 169200360  ...
  1  1    230      160440          299145000             1175153779800  ...
  1  1   1190     6387150       127534407000          6888547183518000  ...
  1  1   5922   238504266     49829456981304      36179571823974699120  ...
  1  1  28644  8507955456  18306027156441024  175934152220744900062080  ...
  ...

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.

For a table with the number of sides not restricted to the form p^n*q see A360098.
T(n,2) = A349427(n+1).
T(1,k) = |A002119(k)|.
Cf. A131514, A273013.

def T(n,k):
    return(factorial(k*n)/factorial(n)^k/factorial(k)\
     * sum((-n)^(k-j)*binomial(n*k+j,j)*falling_factorial(k,j)\
     for j in range(k+1)))

T(n,k) = (n*k)!/((n!)^k*k!) * Sum_{j=0}^k (-n)^(k-j)*binomial(n*k+j,j)*k!/(k-j)!.

T(n,k) = A060540(k,n) * Sum_{j=0}^k (-n)^(k-j)*binomial(n*k+j,j)*k!/(k-j)! for n>=1, k>=1.

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.

Original entry on oeis.org

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

William P. Orrick, Feb 19 2023

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)

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

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.

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.

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

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

A360441 Triangle read by rows: T(n,k) is the number of pairs (c,m), where c is a covering of the 1 X (2n) grid with 1 X 2 rectangles and equal numbers of red and blue 1 X 1 squares and m is a matching between red squares and blue squares, such that exactly k matched pairs are adjacent.

Original entry on oeis.org

1, 1, 2, 7, 8, 4, 71, 78, 36, 8, 1001, 1072, 504, 128, 16, 18089, 19090, 9080, 2480, 400, 32, 398959, 417048, 199980, 56960, 10320, 1152, 64, 10391023, 10789982, 5204556, 1523480, 295120, 38304, 3136, 128, 312129649, 322520672, 156264304, 46629632, 9436000, 1336832, 130816, 8192, 256

Offset: 0

William P. Orrick, Mar 08 2023

If row elements are divided by row sums, one obtains a probability distribution that approaches a Poisson distribution with expected value 1 as n approaches infinity.

			Triangle begins:
         1
         1        2
         7        8       4
        71       78      36       8
      1001     1072     504     128     16
     18089    19090    9080    2480    400    32
    398959   417048  199980   56960  10320  1152   64
  10391023 10789982 5204556 1523480 295120 38304 3136 128

Column 1 is |A002119|.
T(n,k) equals 2^k times the corresponding element of the triangle of A168422.
Sum of row n is A001517(n).
Cf. A253667.

def T(n,k):
    return(2^k*sum((-1)^(j-k)*binomial(2*n-j,n)*binomial(n,j)\
     *binomial(j,k)*factorial(n-j) for j in range(k,n+1)))

T(n,k) equals 2^k times the corresponding element of the triangle of A168422.
T(n,k) = 2^k * Sum_{j=k..n} (-1)^(j-k) * C(2*n-j,n) * C(n,j) * C(j,k) * (n-j)!.
Recurrence: T(n,k) = (1/k!) * Sum_{j=0..k} T(n-j,0) * (-1)^j * C(k,j) * Sum_{t=0..min(j,k-j)} (-1)^(j-t) * C(j,t) * (k-j)! / (k-j-t)!
  = (1/k!) * Sum_{j=0..k} T(n-j,0) * (-1)^j * C(k,j) * R(k,j) where R(k,j) is an element of the triangle of A253667.

cp's OEIS Frontend

A360439 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 (p^nq)-sided dice so that it is possible to roll every number from 0 to (p^nq)^k-1, where p and q are distinct primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

A360441 Triangle read by rows: T(n,k) is the number of pairs (c,m), where c is a covering of the 1 X (2n) grid with 1 X 2 rectangles and equal numbers of red and blue 1 X 1 squares and m is a matching between red squares and blue squares, such that exactly k matched pairs are adjacent.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath

Formula

cp's OEIS Frontend

A360439 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 (p^n*q)-sided dice so that it is possible to roll every number from 0 to (p^n*q)^k-1, where p and q are distinct primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

A360441 Triangle read by rows: T(n,k) is the number of pairs (c,m), where c is a covering of the 1 X (2n) grid with 1 X 2 rectangles and equal numbers of red and blue 1 X 1 squares and m is a matching between red squares and blue squares, such that exactly k matched pairs are adjacent.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath

Formula

A360439 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 (p^nq)-sided dice so that it is possible to roll every number from 0 to (p^nq)^k-1, where p and q are distinct primes.