combination formula

Recommended Posts

The formula for 'n choose r' implies that r! divides n(n-1)(n-2)...(n-r+1).

I seek a direct, arithmetical proof of this.

Tbhank you.

Share on other sites

The formula for 'n choose r' implies that r! divides n(n-1)(n-2)...(n-r+1).

I seek a direct, arithmetical proof of this.

Tbhank you.

The numerator has r consecutive numbers. Therefore one of them has to be divisible by r. Similar reasoning for all numbers less than r.

Share on other sites

It's more complicated than that. Certainly r divides one of n, n-1, n-2,... But it is not true that r-1, r-2 etc. divide different members of n, ,n-1, n-2,... Each of the prime constituents of a member of r-1, r-2 etc. cancels with prime components of multiple members of n-1, n-2,... Moreover, prime factors belonging to different members of r-1, r-2 etc. may need to cancel prime components of a single member of n-1, n-2,...

So it is not a 1-1 mapping, rather a many-to-many.

If my exposition is unclear, I will follow up with a numerical example.

Share on other sites

It's more complicated than that. Certainly r divides one of n, n-1, n-2,... But it is not true that r-1, r-2 etc. divide different members of n, ,n-1, n-2,... Each of the prime constituents of a member of r-1, r-2 etc. cancels with prime components of multiple members of n-1, n-2,... Moreover, prime factors belonging to different members of r-1, r-2 etc. may need to cancel prime components of a single member of n-1, n-2,...

So it is not a 1-1 mapping, rather a many-to-many.

If my exposition is unclear, I will follow up with a numerical example.

I understand your point, but with a little work I believe my approach will work.

Share on other sites

It's more complicated than that. Certainly r divides one of n, n-1, n-2,... But it is not true that r-1, r-2 etc. divide different members of n, ,n-1, n-2,... Each of the prime constituents of a member of r-1, r-2 etc. cancels with prime components of multiple members of n-1, n-2,... Moreover, prime factors belonging to different members of r-1, r-2 etc. may need to cancel prime components of a single member of n-1, n-2,...

So it is not a 1-1 mapping, rather a many-to-many.

If my exposition is unclear, I will follow up with a numerical example.

The easiest way to prove it to yourself is to remember that n choose r is the rth binomial coefficient of (1+x)^n. And there is no way expansion of brackets and gathering of like terms by simple addition can turn the coefficient 1 into something that might be a fraction

To see how this must work with the factorial representation of it

$\frac{n(n-1)(n-2)...(n-(r-1)}{r!}$

is equivalent to

$\frac{n!/(n-r)!}{r!}$

rearrange to

$\frac{n!}{r! \cdot (n-r)!}$

Remembering that n>r and that n>(n-r).

When r=n-1 you end up with n!/r! which is clearly wholly divisible

It then helps to visualise with numbers say 10 chose 4

10!=1.2.3.4.5.6.7.8.9.10

4!= 1.2.3.4

(10-4)!=1.2.3.4.5.6

$\frac{1.2.3.4.5.6.7.8.9.10}{(1.2.3.4)*(1.2.3.4.5.6)}$

rearrange (and you can always do this once you think about it

$\frac{1.2.3.4.5.6.7.8.9*[10]}{(1.2.3.4)*(1.2.3.4)*(5.6)}$

$\frac{1.2.3.4.5.6.7.8.9.[5*2]}{[2*(1.2.3.4)]*(5.6)}$

cancel out the two by multiplying top and bottom by 2

$\frac{1.2.3.4.5.6.7.8.9.(5)}{(1.2.3.4)*(5.6)}$

Every number on the bottom row is duplicated on the top row - must be a whole number.

Whatever size r is you get two smaller than n factorials on the bottom row.

This bottom row can be thought of as two multiplied by the common section of the factorial in turn multiplied by the higher singular parts.

The top row (because n>r and we dealt with n=r-1 above) will always have a even digit multiplier greater than r.

This allows a cancellation of the 2 in the bottom row - and after that you only have one instance of each digit in the bottom row and at least one instance in the top row; that must be a whole number

Share on other sites

Thank you mudslinger - an ingenious proof. Was this previously known or did you devise it in response to my query ?

Share on other sites

No, sorry - found error in proof viz.

These are not equal : x2 is not the same as 2x

Share on other sites

No, sorry - found error in proof viz.

These are not equal : x2 is not the same as 2x

Of course it isn't. Doh!

I am comforted that you didn't see it straight away - makes me feel less bad about it. The fact that it was rubbish kind of makes it clear it was devised for your query - just badly devised

Was just gonna hit the sack and now I am gonna have to think a bit.

You saw the top lines I guess about binomial coefficients of (1+x)^n? Unless I am having another brain fart then that bit is sound - just less easy to formalise

Share on other sites

I think I have a direct arithmetical proof :

To take a numerical example : to prove that 1.2.3...30 divides any 'block' of 30 bigger numbers e.g. 53.54.55...82. We think of 'cancelling' primes from 'top and bottom'. Consider the occurence of the prime 3 in the bottom - here is the distribution :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 1 2 1 1 2 1 1 3 1 14 altogether

and for the top :

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
3 1 1 2 1 1 2 1 1 4 17 altogether

The highest power of 3 present in the bottom is 3, viz 3 cubed = 27 occuring once. There must be at least one multiple of 27 in top (in fact there are two), so we can divide it by 27 and cancel 27 from the bottom. Next, there remain 2 occurences of 3 squared among the bottom numbers, at 9 and 18. Similarily there must be multiples of these numbers on the top - we see them at 63 and 72. Divide 63 and 72 by 9 and 18 to cancel these 3s. Continuing in this way with remaining single powers of 3, we can cancel them all from the bottom (three will be left on top).

The position and number of other primes present in the bottom are unaffected so far. Hence we can pick any other prime and repeat the process. Eventually all numbers will be gone from the bottom ! QED

Share on other sites

Bad spacing in above post, better now with monospaced font :

I think I have a direct arithmetical proof :

To take a numerical example : to prove that 1.2.3...30 divides any 'block' of 30 bigger numbers e.g. 53.54.55...82. We think of 'cancelling' primes from 'top and bottom'. Consider the occurence of the prime 3 in the bottom - here is the distribution :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 1 2 1 1 2 1 1 3 1 14 altogether

and for the top :

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
3 1 1 2 1 1 2 1 1 4 17 altogether

The highest power of 3 present in the bottom is 3, viz 3 cubed = 27 occuring once. There must be at least one multiple of 27 in top (in fact there are two), so we can divide it by 27 and cancel 27 from the bottom. Next, there remain 2 occurences of 3 squared among the bottom numbers, at 9 and 18. Similarily there must be multiples of these numbers on the top - we see them at 63 and 72. Divide 63 and 72 by 9 and 18 to cancel these 3s. Continuing in this way with remaining single powers of 3, we can cancel them all from the bottom (three will be left on top).

The position and number of other primes present in the bottom are unaffected so far. Hence we can pick any other prime and repeat the process. Eventually all numbers will be gone from the bottom ! QED

Share on other sites

Bad spacing in above post, better now with monospaced font :

I think I have a direct arithmetical proof :

To take a numerical example : to prove that 1.2.3...30 divides any 'block' of 30 bigger numbers e.g. 53.54.55...82. We think of 'cancelling' primes from 'top and bottom'. Consider the occurence of the prime 3 in the bottom - here is the distribution :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1 1 2 1 1 2 1 1 3 1 14 altogether

and for the top :

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

3 1 1 2 1 1 2 1 1 4 17 altogether

The highest power of 3 present in the bottom is 3, viz 3 cubed = 27 occuring once. There must be at least one multiple of 27 in top (in fact there are two), so we can divide it by 27 and cancel 27 from the bottom. Next, there remain 2 occurences of 3 squared among the bottom numbers, at 9 and 18. Similarily there must be multiples of these numbers on the top - we see them at 63 and 72. Divide 63 and 72 by 9 and 18 to cancel these 3s. Continuing in this way with remaining single powers of 3, we can cancel them all from the bottom (three will be left on top).

The position and number of other primes present in the bottom are unaffected so far. Hence we can pick any other prime and repeat the process. Eventually all numbers will be gone from the bottom ! QED

You beat me to it. I was just trying to actually rationalise/formalise this - after rushing to post last time I wanted to be sure - when I noticed you had posted. Nice One. It is the notion that you can cancel prime factors without worrying that this stops you cancelling other factors that I needed to get my head around

Share on other sites

If you divide each factor in the numerator by n you get

(-1/n)(-2/n)(-3/n)... (-(1+r)/n)

Therefore you can see the r! Term in the top forcing it to be true..

Edited by TakenItSeriously

Create an account

Register a new account