30
$\begingroup$

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up to $n=50$). Are there any known special cases where the problem becomes easier? As a place to start I was thinking of using $e_p(n!)$ defined as:

$$e_p(n!) = \sum_{k=1}^{\infty}\left \lfloor\frac{n}{p^k}\right \rfloor$$

Which counts the exponent of $p$ in $n!$ (Legendre's theorem I believe?)

Then knowing the prime factorization of $n$ perhaps we can determine if these primes appear more times in the numerator of $\binom{n}{k}$ than the denominator.

Essentially I am looking to see if this method has any traction to it and what other types of research have been done on this problem (along with any proofs of results) before. Thanks!

$\endgroup$
  • 2
    $\begingroup$ Have you considered looking at Pascal's triangle under each modulus $p$? $\endgroup$ – abiessu Oct 30 '13 at 19:11
  • 1
    $\begingroup$ Have you looked into the case where $n$ is a prime power? $\endgroup$ – Jack M Oct 30 '13 at 19:29
  • $\begingroup$ @ abiessu: Could you expand on what you mean please? @ Jack M: I have not, will do so now. Thanks. $\endgroup$ – Patrick Oct 30 '13 at 20:37
29
$\begingroup$

Below is a picture of the situation. Red dots are the points of the first 256 rows of Pascal's triangle where $n\mid {n \choose k}$.

enter image description here

It appears that "most" values fit the bill.

One can prove the following:

Proposition: Whenever $(k, n)=1$, we have $n \mid {n\choose k}$.

This follows from the case where $n$ is a prime power (considering the various prime powers dividing $n$).

However, it happens quite often that $(k,n) \neq 1$ but $n \mid {n\choose k}$ still. For instance, $10 \mid {10\choose 4}=210$, but $(10,4) \neq 1$ (this is the smallest example). I do not think that there is a simple criterion.

In fact, it is interesting to consider separately the solutions $(n,k)$ into those which are relatively prime (which I'll call the trivial solutions) and those which are not. It appears that the non-trivial solutions are completely responsible for the Sierpinski pattern in the triangle above. Indeed, here are only the trivial solutions:

enter image description here

and here are the non-trivial solutions:

enter image description here

Let $f(n)$ be the number of $k$'s between $0$ and $n$ where $n \mid {n\choose k}$. By the proposition we have $\varphi(n)< f(n) < n$.

Question: is $$\text{lim sup } \frac{f(n)-\varphi(n)}{n}=1?$$

Here is a list plot of $\frac{f(n)-\varphi(n)}{n}$. The max value reached for $1<n<2000$ is about $0.64980544$. The blue dots at the bottom are the $n$'s such that $f(n) = \varphi(n)$.

enter image description here

$\endgroup$
  • 4
    $\begingroup$ It is nice to see Sierpinski's triangle appear. $\endgroup$ – Pedro Tamaroff Oct 31 '13 at 6:06
  • $\begingroup$ @PedroTamaroff Indeed! $\endgroup$ – Bruno Joyal Oct 31 '13 at 6:07
  • 1
    $\begingroup$ Very helpful stuff! I too got excited when I saw Sierpinski's triangle. One of my favorite things in math is seeing familiar structures when exploring new problems. Really cool. $\endgroup$ – Patrick Oct 31 '13 at 11:46
  • 1
    $\begingroup$ Thank you for adding those additional two triangle images...really paints an even clearer picture wow. What software did you use to generate these? $\endgroup$ – Patrick Nov 1 '13 at 12:52
  • 1
    $\begingroup$ @Patrick You are welcome, it was fun. I used SAGE. $\endgroup$ – Bruno Joyal Nov 1 '13 at 13:21
3
$\begingroup$

Well, $n = p^2$ when $k$ is not divisible by $p.$ Also $n=2p$ for $k$ not divisible by $2,p.$ Also $n=3p$ for $k$ not divisible by $3,p.$


enter image description here

$\endgroup$
  • $\begingroup$ But you're missing $10 \mid 210$! :) $\endgroup$ – Bruno Joyal Oct 31 '13 at 6:32
  • 1
    $\begingroup$ @Marie, life is hard. We all must learn to live with disappointment. $\endgroup$ – Will Jagy Oct 31 '13 at 6:39
  • $\begingroup$ @BrunoJoyal, so , who is Marie? $\endgroup$ – Will Jagy Oct 31 '13 at 18:08
  • $\begingroup$ It was a secret identity. Nobody could have guessed! ;) $\endgroup$ – Bruno Joyal Oct 31 '13 at 18:11

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.