# Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$

In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$
only when we sum the last summand?

For example let $p=7$ .
Clearly, $1+2+3+4+5+6$ is such a sum (In fact there exist $408$ such sums)
but $2+3+5+4+1+6$ is not, because already $2+3+5+4=2\cdot7$.

We can see after a little investigation that if the total number of sums is $f(p)$,then

$\frac{(p-1)!}{p-2}\leq f(p)\leq (p-1)!$ (equality holds iff $p=3$)

Is it possible to improve this (to find asymptotic bounds or -even better- something precise)?
EDIT : It is possible to prove in an elementary way that for every $n\in \mathbb{N}$, $\phi(n)\mid f(n)$
($\phi(n)$ is Euler's function)

• Looks like the Bonferroni inequalities should give an asymptotic of $(\frac{1}{e}+o(1)) (p-1)!$. Nov 26 '13 at 16:47
• @TerryTao How?Could you be more specific? Nov 26 '13 at 19:44
• Have you tried computing it for the first few primes and then consulting the Online Encyclopedia of Integer Sequences? Nov 27 '13 at 2:23
• Here are my counts of such permutations for $p=1,2,\dots, 12$ (ignoring the requirement of p being prime): 1, 1, 2, 4, 16, 56, 408, 2376, 19920, 156096, 1711680, 16851072. Also, if we include element $p$ into permutations, the counts become: 1, 1, 2, 12, 48, 280, 2040, 16632, 139440, 1404864, 15405120 which for prime $p$ are just the previous counts times $(p-2)$. Nov 27 '13 at 19:57
• I took a liberty to add my counts to OEIS as oeis.org/A232664 and oeis.org/A232663 respectively. Nov 27 '13 at 21:21

As I mentioned in the comments above, the number of permutations of elements $1,2,\dots,p$ (i.e., including $p$) is just by factor of $p-2$ larger than the amount in question (in fact, this is true for any odd $p$). Such permutations are now counted in http://oeis.org/A232663

Here is an explicit formula for the number of such permutations for a prime $p$, which I got by playing with inclusion-exclusion:

$$\sum_{A\in M_p} (-1)^{m+n}\cdot \frac{1}{n!} \cdot p^{n-\mathrm{rank}(A)} \cdot \prod_{j=1}^n (c_j-1)! \cdot \prod_{i=1}^m \binom{r_i}{a_{i1}, \dots, a_{in}},$$

where:

• $M_p$ is the set of matrices with nonnegative integer entries that sum up to $p$, with no zero rows or columns. Size of $M_p$ is given by http://oeis.org/A120733

• $A=(a_{ij})$ is a matrix of size $m\times n$ (i.e., $m$ and $n$ are respectively the number of rows and columns in $A$);

• $c_j = \sum_{i=1}^m a_{ij}$ is the sum of $j$-th column of matrix $A$;

• $r_i = \sum_{j=1}^n a_{ij}$ is the sum of $i$-th row of matrix $A$;

• matrix rank is computed over $\mathrm{GF}(p)$.

The formula may not be so useful due to its complexity but it's still a nice one. But the same reason I do not post here its derivation as it would take at least a couple of pages.

The formula has been numerically tested for $p=5$ and $p=7$.

• We call a sum to be primitive of size $k$ (denote this by $S_k=a_1+a_2+⋯+a_k$) if: $S_k=0modp$ and $a_1+⋯+a_i≠0modp$ where $i<k$ (all the $a_k$ are different and $\leq p−1$).Then the number we want is $N(S_{p−1})=(p−1)!−N(S_2)⋅(p−3)!−⋯−N(S_{p−2})\cdot 1$ where $N(S_i)$ denotes the number of primitive sums of sike $i$ .But this is far away from giving some information also. But, thank for the support anyway Nov 28 '13 at 13:15