Why is a combination always an integer?

Question

I realize what a combination represents ( no. of ways to arrange objects in an unordered way), but I can't find the mathematical proof as to why n choose r is always an integer. Any help?

Thank you

Answer 1

Click
http://lmgtfy.com/?q=why+n+choose+r+is+i…

Choose the first entry

(Awms'answer is better)

vinnie's proof is wrong

Sign in to vote!

Answer 2

Okay, n choose r is an integer because it by definition is, like you said, the number of ways to choose objects without the order of selection mattering. This must be an integer.

I have a feeling you're asking about the formula
n! / (r! * (n-r)!).

The easiest way is to actually prove that n choose r equals that expression.

---------

Choose (unordered) r elements from a set of n elements: n choose r ways
Then order them: r! ways

We can uniquely construct every permutation of r elements in this way, so that we have
n P r = (n choose r) * r!

Note that
n P r = n! / (n-r)!
= n * (n-1) * ... * (n-r+1)
(this isn't hard to show, if you wanted to prove it)

so that we have
n! / (n-r)! = (n choose r) * r!
n! / (r! * (n-r)!) = (n choose r) is an integer..

Sign in to vote!

Answer 3

it is two part.
first let's consider any natural number n. By definition of multiplication the multiples of n are present every n numbers, e.g. multiples of 3 (3,6,9,12) appear at every three natural numbers. So within any n consecutive numbers there is one multiple of n. e.g. withing every 3 consecutive numbers (say 101,102,103) there is one multiple of 3 (102). Also withing any n consecutive numbers there should be at least one multiple of n-1, n-2, or any natural number less than n. Thus a set of n consecutive numbers contain multiples of first n natural numbers

now coming to combinations, let's consider only n!/(n-r)!. It can be expanded to n*(n-1)*(n-2)*...*(n-r+1). This is product of r consecutive numbers.
r! is 1*2*...*r, i.e. this is product of first r natural numbers. Each of these numbers should have at least one multiple in any set of r consecutive numbers. And together all these mush have a multiple in product of r consecutive numbers. hence n!/(n-r)! is a multiple of r!. So (n!/(n-r)!)/r! is integer, hence n!/((n-r)!*r!) is always integer

Sign in to vote!