Assume that $a_1,a_2,\cdots,a_n$ is a completely random permutations of numbers $1$ to $n$. What is the probability that none of the $n$ partial sums $A_1 = a_1$, $A_2 = a_1 + a_2, \dots$, and $A_n = a_1 + a_2 + \cdots + a_n$ are divisible by three?
Here are my attempts: Since $1+\dots+n = n(n+1)/2$, we have that $n = 1 \mod 3$. Let $n = 3k + 1$ and let $N(i)$ be the number of numbers in $\{1,\dots,n\}$ that are $i\mod 3$, then
$$N(1) = N(2) + 1 = N(0) + 1 = k+1.$$
Here is one way I found to avoid divisibility by three:
- Permutations of $1,1,2,1,2, \cdots$ ($0$s can be calculated separately)
I would appreciate it if someone could help me to move forward and finish my solution.
Thank you!
Indeed you are correct that the probability is $0$ unless $n \equiv 1 \mod 3$. So let $n=3k+1$.
Consider modulo $3$. The permutation cannot start with a $0$, so the admissible fraction is $\frac{2k+1}{3k+1}$.
Given that there is one more $1$ than $2$s and $0$s, you found the only way (ignoring $0$s for now) of success: $$1,1,2,1,2,\dots, 1, 2.$$
Let $X$ be a multiset of $k+1$ copies of $1$ and $k$ copies of $2$. Then, there are $\binom{2k+1}{k}$ ways to arrange set $X$, but only one way is successful, so the probability is
$$\frac{2k+1}{3k+1}\binom{2k+1}{k}^{-1}.$$