Is there any criteria for $k,m,n \in N$ such that ${n \choose k}$ diviides ${m \choose k}$.

  • $\begingroup$ Do you have any examples, other than the trivial ones for $k=1?$ $\endgroup$ – Igor Rivin Oct 5 '16 at 9:31
  • $\begingroup$ @IgorRivin: for instance, if $n$ is odd then ${n\choose n-1}=n$ divides ${n+1\choose n-1}=n(n+1)/2$. $\endgroup$ – Laurent Moret-Bailly Oct 5 '16 at 11:06
  • $\begingroup$ Aside from $k=1, n-1$, etc, it seems to me that for general $k$, it becomes lots of case study. $\endgroup$ – T. Amdeberhan Oct 5 '16 at 11:45

Let $P(n,k)=n(n-1)\cdots(n-k+1).$ We can ask the equivalent question of when $P(n,k)$ divides $P(m,k).$ This is completely determined by the value of $m \bmod {P(n,k)}.$

A sufficient condition is that $m\bmod q \in \{{0,1,2,\cdots,k-1\}}$ for each prime power divisor $q=p^i$ of $P(n,k).$ This is also necessary except for $q=p^i$ with $i \gt 1$ and $p+1 \le k.$ For example $5^3$ divides $m(m-1)(m-2)(m-3)(m-4)$ exactly if $m \bmod 5^3 \in \{{0,1,2,3,4\}}$ but $5^3$ divides $m(m-1)(m-2)(m-3)(m-4)(m-5)$ exactly if $m \bmod 5^3 \in \{{1,2,3,4,0,5,25,30,50,55,75,80,100,105\}}.$

Some examples:

For $n=101$ and $k=3$ we need $101\cdot102\cdot103=2\cdot3\cdot17\cdot101\cdot103$ to divide $m(m-1)(m-2).$ For the primes $p=2,3$ this is automatic so we need $m(m-1)(m-2) \bmod p \in \{{0,1,2\}}$ for $p=17,101,103.$ This permits $27$ of the congruence classes mod $17\cdot101\cdot103=176851$ which is about $0.0025 \%.$

For $n=106$ and $k=3$ we need $104\cdot105\cdot106=2^43\cdot5\cdot7\cdot13\cdot53$ to divide $m(m-1)(m-2).$ So we need $m \bmod p \in \{{0,1,2\}}$ for $p=3,5,7,13,53$ as well as $m \bmod 16 \in \{{0,1,2,8,10\}}.$ This allows for $3^55=1215$ of the congruence classes mod $104\cdot105\cdot106 =1157520$ which is about $0.105 \%.$

It will be quite a bit more likely to have $\binom{m}{5}$ be a multiple of $\binom{n}{5}$ for $n=128$ than for $n=124$ or $n=133$ because $124\cdot125\cdot126\cdot127\cdot128$ is divisible by $2^{10},3^2$ and $5^3.$

  • $\begingroup$ For your n=98 example you need more care. m can be odd and 1 mod 8 and the product then be a multiple of 8, but m being 3,5, or 7 mod 8 means the product is not divisible 8. I missed your characterization and thought examples would be more rare. Also the percentage values seem off. Could you be more explicit about the percentage values you present for your examples? Gerhard "Or Maybe Even Less Common" Paseman, 2016.10.05. $\endgroup$ – Gerhard Paseman Oct 5 '16 at 19:03
  • $\begingroup$ You are right. I took out that example and put in a better one. $\endgroup$ – Aaron Meyerowitz Oct 5 '16 at 20:49

I don't know of any criteria. I have a suggestion that might point you to work of Erdos, Selfridge, and others on products of consecutive integers, but I have no specific references for you.

Let c(m,k) be the numerator of a common form of the binomial coefficient, namely $\prod^{k-1}_{i=0} m-i$. Your condition implies c(n,k) divides c(m,k) as well as that n choose k divides a product of a subset of k consecutive integers. Now any two integers greater than k that are less than k apart are "mostly coprime", meaning that any factors they have in common are smaller than k. If you have a somewhat smooth number like n choose k being a factor of the product of a subset of mostly coprime numbers, it seems much more likely that it is a factor of just one of the numbers of the subset than not. Otherwise you have to break up n choose k into two or more mostly coprime factors f_i and arrange all the f_i to have multiples that fall into the same small interval. While this division may be possible, I suspect it will be hard to arrange for three or more factors of n choose k. I would start by characterizing those m,n,k,l in which n choose k divides m(m-l) with l less than k. You may find that a criterion will be that n choose k has such a mostly coprime decomposition that "projects" into a small interval.

Gerhard "Takes Smooth With The Rough" Paseman, 2016.10.05.


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.