Proof Problem

[steve_bank]

I have been coding permutations and combinations.

P(n,r) = n!/(n-r)!
C(n,r) = n!/(r!* (n!-r!)

n! = 1*2*3...
0! = 1

For P it is obvious (n-r)! can never be greater than n!

For C I will test for the bounds. I have no idea how to start a proof that shows analytically if and when r!(n!-r!) is equal or greater than n!.

For the function I m writing max n is 33 for the size of n! and r <= n.

Any deas?

 

[steve_bank]

Writing the post led me to the solution. Simpler than I thought.

Spoiler

n!/(r!*(n-r)!

when n = r it is n!/r!
when r = 0 it is n!/n! = 1
so (r!*(n-r)! is never greater than n!
S0 the values for n!/(r!*(n-r)! are >= 1.

 

[Swammerdami]

Because of cancellations between numerator and denominator, there is a "simpler" way to write C(n,r):
C(11,4) = (11/4)*(10/3)*(9/2)*(8/1)
which is obviously positive and at least 1.

(I wrote a specific example rather than the general case, because it shows the same story, but is easier to write and easier to read.)

More challenging is to prove that C(n,r) is always an integer when r,n are integers with 0 ≤ r ≤ n

 

[Swammerdami]

More challenging is to prove that C(n,r) is always an integer when r,n are integers with 0 ≤ r ≤ n

Inside a spoiler I outline one proof. Some will see this proof as sublimely elegant! Others will growl and call it invalid or cheating!

Spoiler

Two-step proof:
(1) C(n,r) is the correct solution to a counting problem.
(2) All counting numbers are non-negative integers.
QED