login
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.
20

%I #58 Mar 04 2023 19:50:17

%S 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,

%T 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,

%U 7,230,7,7,1,1158,1,7,42,462,7,115,1,42,7,115,1,3030

%N 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.

%C 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).

%C 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.

%C 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).

%C 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

%C a(n) is also the number of principal reversible squares of order n. - _S. Harry White_, May 19 2018

%C From _Gus Wiseman_, Oct 29 2021: (Start)

%C 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:

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

%C (242) (263) (284) (393)

%C (2222) (362) (482) (3333)

%C (2233) (2244)

%C (2332) (2442)

%C (3223) (4224)

%C (3322) (4422)

%C (22242)

%C (24222)

%C (222222)

%C The even-length case is A347464.

%C (End)

%H Alois P. Heinz, <a href="/A273013/b273013.txt">Table of n, a(n) for n = 1..10000</a>

%H Matthew C. Lettington and Karl Michael Schmidt, <a href="https://arxiv.org/abs/1910.02455">Divisor Functions and the Number of Sum Systems</a>, arXiv:1910.02455 [math.NT], 2019.

%H S. Harry White, <a href="http://budshaw.ca/Reversible.html">Reversible Squares</a>

%F 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).

%F 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

%e 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).

%e When n = 5, a(n) = 1; the sole arrangement is (0,1,2,3,4; 0,5,10,15,20).

%t facs[n_] := If[n <= 1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@# >= d&]], {d, Rest[Divisors[n]]}]];

%t altprod[q_] := Product[q[[i]]^(-1)^(i-1), {i, Length[q]}];

%t Table[Length[Select[Join@@Permutations/@facs[n^2], altprod[#] == 1&]],{n, 30}]

%t (* _Gus Wiseman_, Oct 29 2021 *)

%t (* or *)

%t ofc[n_,k_] := If[k > PrimeOmega[n], 0, If[k == 0 && n == 1, 1, Sum[ofc[n/d, k-1],{d, Rest[Divisors[n]]}]]];

%t Table[If[n == 1, 1, Sum[ofc[n, x]^2 + ofc[n, x]*ofc[n, x+1], {x, n}]],{n, 30}]

%t (* _Gus Wiseman_, Oct 29 2021, based on author's formula *)

%o (PARI)

%o 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));

%o A273013(n) = A273013aux(n^2); \\ _Antti Karttunen_, Oct 30 2021

%o (SageMath)

%o @cached_function

%o def r(m,n):

%o if n==1:

%o return(1)

%o divList = divisors(m)[:-1]

%o return(sum(r(n,d) for d in divList))

%o def A273013(n):

%o return(r(n,n)) # _William P. Orrick_, Feb 19 2023

%Y Cf. A111588, A131514, A360098.

%Y Positions of 1's are 1 and A000040.

%Y A000290 lists squares, complement A000037.

%Y A001055 counts factorizations, ordered A074206.

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

%Y A339846 counts even-length factorizations, ordered A174725.

%Y A339890 counts odd-length factorizations, ordered A174726.

%Y A347438 counts factorizations with alternating product 1.

%Y A347460 counts possible alternating products of factorizations.

%Y A347463 counts ordered factorizations with integer alternating product.

%Y A347466 counts factorizations of n^2.

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

%K nonn,easy

%O 1,4

%A _Elliott Line_, May 13 2016