combination formula

[caledonia]

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.

[Strange]

Have you tried Google? There are hundreds of sites showing the derivation of this formula. For example: http://blogformathematics.blogspot.co.uk/2011/10/derivation-of-combinations-formula.html

[mathematic]

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.

[caledonia]

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.

[mathematic]

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.

[imatfaal]

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 r^th 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

 

[latex]\frac{n(n-1)(n-2)...(n-(r-1)}{r!}[/latex]

 

is equivalent to

 

[latex]\frac{n!/(n-r)!}{r!}[/latex]

 

rearrange to

 

[latex]\frac{n!}{r! \cdot (n-r)!}[/latex]

 

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

 

[latex]\frac{1.2.3.4.5.6.7.8.9.10}{(1.2.3.4)*(1.2.3.4.5.6)}[/latex]

 

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

 

 

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

 

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

 

cancel out the two by multiplying top and bottom by 2

 

[latex]\frac{1.2.3.4.5.6.7.8.9.(5)}{(1.2.3.4)*(5.6)}[/latex]

 

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

 

 

 

 

 

 

[caledonia]

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

[caledonia]

No, sorry - found error in proof viz.

 

 

 

 

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

[imatfaal]

No, sorry - found error in proof viz.

 

 

 

 

These are not equal : x² 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

[caledonia]

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

[caledonia]

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

[imatfaal]

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

[TakenItSeriously]

 

 

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 February 19, 2016 by TakenItSeriously