|
| |
|
|
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.
|
|
3
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,18
|
|
|
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)
|
|
|
LINKS
|
|
|
|
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<i} r(m,M_{m,d}) for M != U.
|
|
|
EXAMPLE
|
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})
...
|
|
|
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 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)
|
|
|
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).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
