Sets with the same sum and product as the first $n$ positive integers

Question

Suppose $a_1, a_2, \ldots, a_n $ are integers in the set $\{1,2, \ldots, n\}$, such that $$ \sum_{i=1}^n a_i = \frac{n(n+1)}{2}$$ and such that $$\prod_{i=1}^n a_i = n!.$$ (So the sum of the $a_i$ equals the sum of the first $n$ positive integers and the product of the $a_i$ equals the product of the first $n$ positive integers.)

Must $\{a_1, a_2, \ldots , a_n \} = \{1,2, \ldots , n\}$? In other words, is the sequence $(a_i)$ just equal to the first n positive integers in some order?

For small values of $n$ it is true, but I can only check it by a brute-force argument. It was reading an article about the mathematics of Sudoku that inspired this question, but it seemed like a natural one without any such motivation.

Answer 1

We can view $\{a_1, a_2, \ldots, a_n\}$ as a multiset with multiple element instances allowed. Then, we can denote number of occurences of $i$ to be $k_i \geq 0$ and rewrite the conditions slightly:

$$ \sum_{i=1}^n i k_i = \frac{n(n+1)}{2},\, \, \, \prod_{i=1}^n i^{k_i} = n!,\, \, \, \sum_{i=1}^n k_i=n. $$

For fixed $n$, the second condition and fundamental theorem of arithmetic allow us to write both sides in terms of primes $p_j \leq n$, and turn it into a system of linear diophantine equations by comparing the prime exponents. For example, for $n=9$ we have $$ n!=9!=2^7\cdot3^4\cdot5\cdot 7\\ \prod_{i=1}^n i^{k_i}=2^{k_2}3^{k_3}4^{k_4}5^{k_5}6^{k_6}7^{k_7}8^{k_8}9^{k_9}=2^{k_2+2k_4+k_6+3k_8}\cdot 3^{k_3+k_6+2k_9}\cdot 5^{k_5}\cdot 7^{k_7} $$ and hence $k_2+2k_4+k_6+3k_8=7$, $k_3+k_6+2k_9=4$, $k_5=k_7=1$. We can see that this system can be solved (together with the remaining conditions) with $$ (k_1,k_2,k_3,k_4,k_5,k_6,k_7,k_8,k_9)=(1,1,0,3,1,0,1,0,2), $$ and thus we have found a solution $\{1,2,4,4,4,5,7,9,9\}$, which we can easily verify.

Solving the equations for $n<9$, we find that only solutions are the trivial ones $k_i=1$ corresponding to $\{a_1, a_2, \ldots, a_n\}=\{1, 2, \ldots, n\}$. So this also shows that $n=9$ yields a minimal example.

EDIT: Based on BarryCipra's comment, I've checked number of solutions for few additional $n$'s and found that this is the sequence oeis.org/A119551: $$ 1, 1, 1, 1, 1, 1, 1, 1, 2, 6, 6, 22, 22, 60, 159, 377, \dots $$

Answer 2

From Here we have:

$$118=14+50+54 =15+40+63$$ $$14\times 50\times 54=15\times 40\times 63=37800$$

and thus one such solution for $n=63$ can be generated:

$1,2,...,13,15,15,16,...,39,41,...,49,50,50,51,52,53,55,...,63,63$

where $14,50,54$ are replaced by $15,40,63$.

There should be smaller examples, but nothing is coming to mind right now.

EDIT: I found $(2,8,9)$ and $(3,4,12)$. Hence:

$$12!=1\times2\times2\times5\times6\times7\times8\times8\times9\times9\times10\times11$$

$$78=1+2+2+5+6+7+8+8+9+9+10+11$$

since

$$2\times 8\times 9=3\times 4\times 12=144$$

$$2+8+9=3+4+12=19$$