A273013 Number of different arrangements of nonnegative integers on a pair of n-sided dice such that the dice can add to any integer from 0 to n^2-1.

1, 1, 1, 3, 1, 7, 1, 10, 3, 7, 1, 42, 1, 7, 7, 35, 1, 42, 1, 42, 7, 7, 1, 230, 3, 7, 10, 42, 1, 115, 1, 126, 7, 7, 7, 393, 1, 7, 7, 230, 1, 115, 1, 42, 42, 7, 1, 1190, 3, 42, 7, 42, 1, 230, 7, 230, 7, 7, 1, 1158, 1, 7, 42, 462, 7, 115, 1, 42, 7, 115, 1, 3030

Offset

1,4

Comments

The set of b values (see formula), and therefore also a(n), depends only on the prime signature of n. So, for example, a(24) will be identical to a(n) of any other n which is also of the form p_1^3*p_2, (e.g., 40, 54, 56).

The value of b_1 will always be 1. When n is prime, the only nonzero b will be b_1, so therefore a(n) will be 1.

In any arrangement, both dice will have a 0, and one will have a 1 (here called the lead die). To determine any one of the actual arrangements to numbers on the dice, select one of the permutations of divisors (for the lead die), then select another permutation that is either the same length as that of the lead die, or one less. For example, if n = 12, we might select 2*3*2 for the lead die, and 3*4 for the second die. These numbers effectively tell you when to "switch track" when numbering the dice, and will uniquely result in the numbering: (0,1,6,7,12,13,72,73,78,79,84,85; 0,2,4,18,20,22,36,38,40,54,56,58).

a(n) is the number of (unordered) pairs of polynomials c(x) = x^c_1 + x^c_2 + ... + x^c_n, d(x) = x^d_1 + x^d_2 + ... + x^d_n with nonnegative integer exponents such that c(x)*d(x) = (x^(n^2)-1)/(x-1). - Alois P. Heinz, May 13 2016

a(n) is also the number of principal reversible squares of order n. - S. Harry White, May 19 2018

From Gus Wiseman, Oct 29 2021: (Start)

Also the number of ordered factorizations of n^2 with alternating product 1. This follows from the author's formula. Taking n instead of n^2 gives a(sqrt(n)) if n is a perfect square, otherwise 0. Here, an ordered factorization of n is a sequence of positive integers > 1 with product n, and the alternating product of a sequence (y_1,...,y_k) is Product_i y_i^((-1)^(i-1)). For example, the a(1) = 1 through a(9) = 3 factorizations are:

() (22) (33) (44) (55) (66) (77) (88) (99)

(242) (263) (284) (393)

(2222) (362) (482) (3333)

(2233) (2244)

(2332) (2442)

(3223) (4224)

(3322) (4422)

(22242)

(24222)

(222222)

The even-length case is A347464.

(End)

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Matthew C. Lettington and Karl Michael Schmidt, Divisor Functions and the Number of Sum Systems, arXiv:1910.02455 [math.NT], 2019.

S. Harry White, Reversible Squares

Formula

a(n) = b_1^2 + b_2^2 + b_3^2 + ... + b_1*b_2 + b_2*b_3 + b_3*b_4 + ..., where b_k is the number of different permutations of k divisors of n to achieve a product of n. For example, for n=24, b_3 = 9 (6 permutations of 2*3*4 and 3 permutations of 2*2*6).

a(n) = r(n,n) where r(m,1) = 1 and r(m,n) = Sum_{d|m,d<m} r(n,d) if n != 1. - William P. Orrick, Feb 19 2023

Example

When n = 4, a(n) = 3; the three arrangements are (0,1,2,3; 0,4,8,12), (0,1,4,5; 0,2,8,10), (0,1,8,9; 0,2,4,6).
When n = 5, a(n) = 1; the sole arrangement is (0,1,2,3,4; 0,5,10,15,20).

Mathematica

facs[n_] := If[n <= 1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@# >= d&]], {d, Rest[Divisors[n]]}]];
altprod[q_] := Product[q[[i]]^(-1)^(i-1), {i, Length[q]}];
Table[Length[Select[Join@@Permutations/@facs[n^2], altprod[#] == 1&]], {n, 30}]
(* Gus Wiseman, Oct 29 2021 *)
(* or *)
ofc[n_, k_] := If[k > PrimeOmega[n], 0, If[k == 0 && n == 1, 1, Sum[ofc[n/d, k-1], {d, Rest[Divisors[n]]}]]];
Table[If[n == 1, 1, Sum[ofc[n, x]^2 + ofc[n, x]*ofc[n, x+1], {x, n}]], {n, 30}]
(* Gus Wiseman, Oct 29 2021, based on author's formula *)

Prog

(PARI)
A273013aux(n, k=0, t=1) = if(1==n, (1==t), my(s=0); fordiv(n, d, if((d>1), s += A273013aux(n/d, 1-k, t*(d^((-1)^k))))); (s));
A273013(n) = A273013aux(n^2); \\ Antti Karttunen, Oct 30 2021
(SageMath)
@cached_function
def r(m, n):
    if n==1:
        return(1)
    divList = divisors(m)[:-1]
    return(sum(r(n, d) for d in divList))
def A273013(n):
    return(r(n, n)) # William P. Orrick, Feb 19 2023

Crossrefs

Cf. A111588, A131514, A360098.

Positions of 1's are 1 and A000040.

A000290 lists squares, complement A000037.

A001055 counts factorizations, ordered A074206.

A119620 counts partitions with alternating product 1, ranked by A028982.

A339846 counts even-length factorizations, ordered A174725.

A339890 counts odd-length factorizations, ordered A174726.

A347438 counts factorizations with alternating product 1.

A347460 counts possible alternating products of factorizations.

A347463 counts ordered factorizations with integer alternating product.

A347466 counts factorizations of n^2.

Cf. A062312, A347437, A347439, A347440, A347442, A347456, A347459, A347464.

Sequence in context: A210442 A077202 A086665 * A050521 A266724 A247146

Adjacent sequences: A273010 A273011 A273012 * A273014 A273015 A273016

Keyword

nonn,easy

Author

Elliott Line, May 13 2016

Status

approved