caledonia 1 Posted September 16, 2015 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. 0 Share this post Link to post Share on other sites

Strange 4194 Posted September 16, 2015 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 0 Share this post Link to post Share on other sites

mathematic 95 Posted September 16, 2015 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. 0 Share this post Link to post Share on other sites

caledonia 1 Posted September 17, 2015 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. 1 Share this post Link to post Share on other sites

mathematic 95 Posted September 18, 2015 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. 0 Share this post Link to post Share on other sites

imatfaal 2480 Posted September 18, 2015 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 0 Share this post Link to post Share on other sites

caledonia 1 Posted September 19, 2015 Thank you mudslinger - an ingenious proof. Was this previously known or did you devise it in response to my query ? 0 Share this post Link to post Share on other sites

caledonia 1 Posted September 19, 2015 No, sorry - found error in proof viz. These are not equal : x^{2} is not the same as 2x 0 Share this post Link to post Share on other sites

imatfaal 2480 Posted September 19, 2015 No, sorry - found error in proof viz. These are not equal : x^{2} 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 0 Share this post Link to post Share on other sites

caledonia 1 Posted September 21, 2015 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 altogetherand 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 altogetherThe 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 0 Share this post Link to post Share on other sites

caledonia 1 Posted September 22, 2015 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 altogetherand 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 altogetherThe 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 1 Share this post Link to post Share on other sites

imatfaal 2480 Posted September 22, 2015 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 0 Share this post Link to post Share on other sites

TakenItSeriously 8 Posted February 19, 2016 (edited) 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 0 Share this post Link to post Share on other sites