21
$\begingroup$

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)?
Thanks in advance!
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)

$\endgroup$
  • 3
    $\begingroup$ Looks like the Bonferroni inequalities should give an asymptotic of $(\frac{1}{e}+o(1)) (p-1)!$. $\endgroup$ – Terry Tao Nov 26 '13 at 16:47
  • 3
    $\begingroup$ @TerryTao How?Could you be more specific? $\endgroup$ – Konstantinos Gaitanas Nov 26 '13 at 19:44
  • 2
    $\begingroup$ Have you tried computing it for the first few primes and then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$ – Gerry Myerson Nov 27 '13 at 2:23
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Max Alekseyev Nov 27 '13 at 19:57
  • 1
    $\begingroup$ I took a liberty to add my counts to OEIS as oeis.org/A232664 and oeis.org/A232663 respectively. $\endgroup$ – Max Alekseyev Nov 27 '13 at 21:21
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Konstantinos Gaitanas Nov 28 '13 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.