Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Dear All,

I am considering maximal subgroups of odd index in Alternating and Symmetric groups, and this leeds me to some questions on binomial coefficients that I presently do not know and that I need some hints and suggestions :

  1. Assume that $ab=2^t$ with $a>1, b>1,t\geq 3$. Which values of $a$ and $b$ such that $$\frac{(2^t)!}{(a!)^b.b!}$$ is odd and smallest.

  2. Let $n\geq 9$ be an odd integer (not prime) and $p$ the largest prime less than $n$. Is there always an integer $r\geq 1$ such that $\binom{n}{r}$ is odd and divisible by $p$. Note that this is not true for the case $n=9$. Is it also true for $n$ even?

Thanks you very much in advance for comments and advice.

share|improve this question
Use Lucas's theorem: http://en.wikipedia.org/wiki/Lucas'_theorem –  Chris Godsil Jun 23 '12 at 15:23
For (1), the quotients are all odd, and I think the smallest occur when $b=2$. I think this can be proved with Stirling's formula, but perhaps there is a nice inductive argument. –  Douglas Zare Jun 23 '12 at 17:12
@Chris Godsil : Thanks for your indicating me to use Lucas's theorem that I did not know before. @Douglas Zare : Thanks. I also think that the smallest occurs when $b=2$ but I am still on the way to prove that. –  Dung Duong Jun 25 '12 at 7:24
add comment

2 Answers

up vote 1 down vote accepted

Hi! I have a proposed answer for 2).

You can construct an infinite series of counter examples. Erdos proved that there are primes between $n$ and $2n$. Now consider $2n=2^k$ for some $k>2$.

We can observe that the binomial number $\binom{2n+1}{r}, 1< r < n+1$ is always even. The upper product have powers of 2 as the following sequence: $\lbrace k,1,2,1,3,\dots,s \rbrace$
while the bottom product have powers of 2 of the form: $\lbrace 1,2,1,3,\dots,s,k-1\rbrace$.
This can be reflected for cases $\binom {2n+1}{r}, n < r < 2n$.

The difference of the sum of these 2 sequences is at least 1. As a result, the binomial number may be divisible by $p$ but it will not be even.

(Edit) Exception: When the binomial number is $\binom{2n+1}{1}$ or $\binom{2n+1}{2n}$ you have either no powers of 2 or same powers of 2. But in this case it will not be divisible by $p$.

share|improve this answer
More generally, using Lucas' Theorem, take q to be the smallest prime greater than 2^t with q not a Mersenne prime, then any number m between 2^t and q should serve: When n is large enough for m choose n to be divisible by the preceding prime p, the binary expansion of n will start with 1 in a place where m's expansion has a 0. One can also do this starting with b times 2^t for small odd numbers b, providing b2^t+1 is not prime. Gerhard "Ask Me About Systtem Design" Paseman, 2012.06.23 –  Gerhard Paseman Jun 23 '12 at 18:26
Oops. For b=3 it will not work. This may lead to characterizing which m ha e the desired property. Gerhard "Ask Me About System Design" Paseman, 2012.06.23 –  Gerhard Paseman Jun 23 '12 at 20:06
Thanks for your answer and comments. In fact, Nagura proved that for $n\geq 25$, there exists a prime between $n$ and $\frac{6}{5}n$. And if we take any $n$ in the interval $[2^t+[2^t/6]+1,2^{t+1}-1]$ and $r=n-2^t$ then $\binom{n}{r}$ should do the job. –  Dung Duong Jun 26 '12 at 20:27
add comment

About the question (1), I quoted here the result from this paper of Attila Maróti

First, We may assume that $a\geq b$ since if $b>a$ then $$b!^{a-1}=a!^{a-1}(a+1)^{a-1}\cdots b^{a-1}>a!^{a-1}a^{(b-a)(a-1)}$$ In addition, we have that $a^{a-1}>1.2.\cdots.a=a!$ and so $$b!^{a-1}>a!^{a-1}a!^{b-a}=a!^{b-1}$$ which implies that $$b!^a.a!>a!^b.b!\Rightarrow \frac{m!}{a!^b.b!} > \frac{m!}{b!^a.a!}$$

Assume now that $m=a_1b_1=a_2b_2$ with $b_1\leq a_1, b_2\leq a_2$. If $b_1\leq b_2$ and $a_1\geq a_2$ then

$$a_1!^{b_1}.b_1! \geq a_2!^{b_1}(a_2+1)^{b_1}\cdots a_1^{b_1}b_1! \geq a_2!^{b_1}a_2^{(a_1-a_2)b_1}b_1! \quad (\rm{since ~ a_1\geq a_2})$$

$$ = a_2!^{b_1}b_1! (a_2^{a_2})^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2^{a_2-1}a_2)^{\frac{b_1}{a_2}(a_1-a_2)} $$

$$\geq a_2!^{b_1}b_1! (a_2!b_2)^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2!b_2)^{b_2-b_1} \quad (\rm{since ~ a_2\geq b_2 ~ and ~ a_1b_1=a_2b_2})$$

$$ \geq a_2!^{b_2}b_1!(b_1+1)\cdots b_2 = a_2!^{b_2}b_2! \quad (\rm{since ~ b_2\geq b_1})$$ and hence $$\frac{m!}{a_1!^{b_1}.b_1!}\leq \frac{m!}{a_2!^{b_2}.b_2!}$$

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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