Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is a question related to Pascal's triangle. I need to find the number of entries not divisible by $n$ in the 100th row of Pascal's triangle.

share|improve this question
    
The $n$th row of Pascal's triangle constains the number $\binom{n}{0}$, $\binom{n}{1}$, $\binom{n}{2},\ldots,\binom{n}{n}$. One can determine when $\binom{n}{k}$ is divisible by 3 by considering the number of carries when adding $k$ and $n-k$ in base $3$: if there is at least one carry, then it is divisible by $3$; if there are no carries, then it is not divisible by $3$. –  Arturo Magidin Mar 8 '12 at 18:21
    
We need to do this??? –  The Chaz 2.0 Mar 8 '12 at 18:21
1  
@TheChaz: Not "we", "they": Mr Jay and his entourage. –  Arturo Magidin Mar 8 '12 at 18:22
    
A binomial entourage... :) –  The Chaz 2.0 Mar 8 '12 at 18:30

1 Answer 1

up vote 4 down vote accepted

You can use Kummer's theorem.

Kummer's theorem gives you a method to find the highest power of a prime $p$ which divided the binomial coefficient $\binom{a}{b}$. It says that the require exponent is the number of carries when you add $b$ and $a-b$ in base $p$.

Now if you want to check the divisibility of $\binom{a}{b}$ by a given number $n$, you first factorize $n$ into prime factors: $n = p_1^{e_1} \dots p_k^{e_k}$ and then for each $p_i$, try to find the highest power of $p_i$ which divides $\binom{a}{b}$ using Kummer's theorem. Say you find it to be $s_i$.

Now you just check for each $i$ whether $s_i \ge e_i$.

To give you an example, suppose you want to find out if $\binom{100}{77}$ is divisible by $20$.

$20 = 2^2 \times 5$.

Now write $77 = 64 + 8 + 4 + 1 = 1001101_2$

$100 - 77 = 23 = 16 + 4 + 2 + 1 = 0010111_2$.

Add the two and you see that there are $5$ carries. So $2^5$ divides $\binom{100}{77}$.

Now do the same in base $5$. $77 = 25*3 + 2*1 = 302_5$.

$23 = 5*4 + 3*1 = 43_5$

Add the two and you see there are $2$ carries. So $5^2$ divides $\binom{100}{77}$.

Thus $\binom{100}{77}$ is divisible by $20$.

Now do each in the 100th row, and you have your answer.

Another method is to use Legendre's theorem:

The highest power of $p$ which divides $n!$ is $\left[\frac{n}{p}\right] + \left[\frac{n}{p^2}\right] + \left[\frac{n}{p^3}\right] + \dots$

To use this, use the fact that $\binom{a}{b} = \frac{a!}{(a-b)!b!}$ and use the above to each factorial that is appearing, subtracting the answer you get for the factorials in the denominator.

This is probably a bit more tedious than using Kummer's method though.

(Note: there might be cleverer ways to just find the count you are interested in).

share|improve this answer
    
ok..well i wanted to know if i can calculate this manually.Can u explain how to work out this using the theorem you just stated. –  Jay Mar 8 '12 at 18:30
    
@Jay: I suggest you try it out yourself first! –  Aryabhata Mar 8 '12 at 18:32
    
i know i may sound silly but i am not good with maths , so can u please explain Kummer's Theorem.i tried but could understand it..the last part "the number of carries when adding m and n−m in base p" –  Jay Mar 8 '12 at 18:47
    
@Jay: Do you know how to change the base of a number? Do you know how to add two numbers written in a given base? Do you know how a carry happens during addition? –  Aryabhata Mar 8 '12 at 18:54
    
@Jay: I have elaborated a bit. I wanted you to try it for your own benefit (hands on experience and all that), but perhaps an example will help too. Good luck! –  Aryabhata Mar 8 '12 at 21:05

Your Answer

 
discard

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.