Find the number of functions $f : \{ 1,2,...,n \} \rightarrow \{p_1,p_2,p_3 \} $ for which the number $f(1)f(2)...f(n)$ is a perfect square.

Question

Let $p_1,p_2,p_3$ be distinct prime numbers and consider $n \in \mathbb N$ . Find the number of functions $f : \{ 1,2,...,n \} \rightarrow \{p_1,p_2,p_3 \} $ for which the number $f(1)f(2)...f(n)$ is a perfect square.

My attempt : If $n$ is an odd number, it is obvious that there are no functions, because it is essential that the exponents of the prime numbers in the product are even numbers , otherwise we would not have a perfect square. Next we consider $n = 2k , k \in \mathbb N$. Let's look at a set $\mathrm M_{2k}$ with $2k$ elements and see in how many ways we can write it with $a$ and $b$ ($a \ne b$) so that the number of appearances of a and b is even.We have $\binom{2k}{0}$ when all the elements are $a$ , $\binom{2k}{2}$ when 2 elements are $b$ and the rest are $a$ , $\binom{2k}{4}$ when 4 elements are $b$ and the rest are $a$ ... $\binom{2k}{2k}$ when we only use $b$.So we can write the set in $\binom{2k}{0}$ + $\binom{2k}{2}$ + ... + $\binom{2k}{2k}$ $= 2^{2k-1} $ ways.

Now, using this if we fix $p_1$ and we subtract from the even number of appearances of $p_1$, the even number of occurrences of $p_2$ and $p_3$ we have:

$\binom{2k}{0}$ when it's only $p_1$

$\binom{2k}{2} * 2^{1}$ when we have a $\mathrm M_{2}$ with $p_2,p_3$ and the rest $p_1$

$\binom{2k}{4} * 2^{3}$ when we have a $\mathrm M_{4}$ with $p_2,p_3$ and the rest $p_1$

$\binom{2k}{6} * 2^{5}$ when we have a $\mathrm M_{6}$ with $p_2,p_3$ and the rest $p_1$

.

.

.

$\binom{2k}{2k} * 2^{2k-1}$ when we have a $\mathrm M_{2k}$ with $p_2,p_3$ and no $p_1$(practically we reached the case addressed above).

So the numbers of functions would be : 1 + $\binom{2k}{2} * 2^{1}$ + $\binom{2k}{4} * 2^{3}$ + ... + $\binom{2k}{2k} * 2^{2k-1}$ = ?

Can you tell me if so far my approach is correct and at least the last part is the correct result(the sum). It's quite difficult for me to calculate it , but if what I've done so far is correct, can you please help me to calculate it? Thank you !

Answer 1

You have made good progress thus far. Note that the first term does not quite fit \begin{eqnarray*} S= 1+\sum_{i=1}^{k} \binom{2k}{2i}2^{2i-1}. \end{eqnarray*} To complete rearrange, do the odd even trick & binomial ... \begin{eqnarray*} 4S-2 &=& 2\sum_{i=0}^{k} \binom{2k}{2i}2^{2i} \\ &=& \sum_{j=0}^{2k} \binom{2k}{j}2^{j}+ \sum_{j=0}^{2k} \binom{2k}{j}(-2)^{j}\\ &=& 3^{2k}+1. \end{eqnarray*} We have $\frac{3^{2k}+3}{4}$. See also https://oeis.org/A054879

Answer 2

Your work so far is all correct. All that remains is to evaluate your sum at the end.

First, let me show you how to evaluate the sum $$ S:=\binom{2k}02^0+\binom{2k}22^2+\binom{2k}42^4+\dots+\binom{2k}{2k}2^{2k} $$ Note that your summation is equal to $(S+1)/2$.

We can write $S=\sum_{i=0}^{k}\binom{2k}{2i}2^{2i}$. This is just like the summation $T:=\sum_{j=0}^{2k} \binom{2k}j2^j$, but $S$ only contains the even-index terms of $T$. Fortunately, there is a standard way to filter out the odd terms of a summation. Define $T'$ to be the result of resplacing each instance of $2^{2k}$ in $T$ with $(-2)^{2k}$. Writing $$ T=\binom{2k}02^0+\binom{2k}12^1\dots +\binom{2k}{j}2^j\dots+\binom{2k}{2k}2^{2k},\\ T'=\binom{2k}0(-2)^0+\binom{2k}1(-2)^1\dots +\binom{2k}{j}(-2)^j\dots+\binom{2k}{2k}(-2)^{2k}, $$ then you can see that $(T+T')/2$ is exactly equal to $S$. This is because the odd-index terms cancel out, as they have opposite signs, but the even index terms are just averages of two equal numbers, so they are unchanged.

Furthermore, using the binomial theorem, we can simplify both $T$ and $T'$ as follows: $T=(1+2)^{2k}=3^{2k}$, while $T'=(1-2)^{2k}=(-1)^{2k}=1$. Therefore, $$ S=\frac{3^{2k}+1}{2}, $$ which implies that the number of functions is $(S+1)/2=\boxed{(3^{2k}+3)/4}$.