Prove that nCk is a natural number

  • Thread starter nietzsche
  • Start date
  • Tags
    Natural
In summary, to prove that \binom{n}{k} is a natural number, we can show that it represents the number of sets of exactly k integers chosen from 1, ..., n. This can be done by considering the number of different sequences of integers that can be chosen from the set {1,...,n}.
  • #1
nietzsche
186
0

Homework Statement



Prove that [tex]\binom{n}{k}[/tex] is a natural number by showing that [tex]\binom{n}{k}[/tex] is the number of sets of exactly [tex]k[/tex] integers each chosen from [tex]1, ..., n[/tex].

Homework Equations





The Attempt at a Solution



I posted a similar question before (https://www.physicsforums.com/showthread.php?t=339363) which asked for a proof by induction. This question is a bit different, and I'm not entirely sure how to get started. I'd appreciate some hints. Thanks.
 
Physics news on Phys.org
  • #2
Here's your hint. How many different sequences (ordered!) of integers can you pick from the set {1,...,n}? Count sequences. Mull over that for a bit.
 

FAQ: Prove that nCk is a natural number

What is nCk?

nCk, also known as "n choose k", represents the number of ways to choose k objects from a set of n objects. It is a mathematical notation used in combinatorics.

How do you prove that nCk is a natural number?

To prove that nCk is a natural number, we can use the formula nCk = n! / (k!(n-k)!). Since n, k, and n-k are all natural numbers, and the factorial function always results in a natural number, nCk must also be a natural number.

What is a natural number?

A natural number is a positive integer (whole number) that is greater than or equal to 0. It is a basic concept in mathematics and is often denoted by the symbol "N".

Can nCk ever be a negative number?

No, nCk cannot be a negative number. As mentioned before, nCk represents the number of ways to choose k objects from a set of n objects, which cannot be a negative value. Additionally, the formula for nCk only involves positive integers, so the result will always be a positive natural number.

What is the significance of proving that nCk is a natural number?

The significance of proving that nCk is a natural number is that it confirms the validity of the formula and allows us to use it in further calculations and mathematical proofs. It also helps us understand the properties and applications of combinations in combinatorics.

Similar threads

Proving natural numbers in Pascal's Triangle
Replies
21
Views
6K
Do Two Primes Divide All Binomial Coefficients for Any n?
Replies
33
Views
3K
Prove every subset of countable set is either finite or else countable
Replies
1
Views
1K
Combinatorics -- Counting Sets of Binary Strings
Replies
3
Views
2K
Function multiplied by nth derivative of another function
Replies
7
Views
1K
How many subsets of size three or less are in a n-object set
Replies
4
Views
1K
Proving the Existence of a Number with n Divisors
Replies
18
Views
2K
Proof of an inequality with natural numbers
Replies
3
Views
1K
Proving a formula with binomial coefficient when n=-1
Replies
2
Views
2K
Binomial Coefficient of a Prime Power
Replies
2
Views
2K

Hot Threads

Recent Insights

Back
Top