How to explain that n choose k is equal to n choose (n-k)?

• Eclair_de_XII
In summary: So if you have ##k## elements in a subset, you automatically have ##n-k## elements in the complement. This is why the number of ways to choose ##k## elements from ##n## elements is the same as the number of ways to choose ##n-k## elements from ##n## elements.
Eclair_de_XII

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

How many elements were not chosen when you picked out ##k## elements from ##n## elements?

Also, it is clearly a mathematical fact, since
$${n \choose n-k} = \frac{n!}{(n-k)!(n-(n-k))!} = \frac{n!}{(n-k)!k!} = {n \choose k}.$$

Eclair_de_XII said:

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

Think concretely. You have a group of ##n## people and you have two tables, one with ##k## seats and one with ##n-k## seats. There are two different ways to think about assigning people to tables: (1) You can pick ##k## people for the first table. There are ##\left( \begin{array} \\ n \\ k \end{array} \right)## ways to do this. Anyone who isn't assigned to the first table is automatically assigned to the second table. (2) You can pick ##n-k## people to assign to the second table. There are ##\left( \begin{array} \\ n \\ n-k \end{array} \right)## ways to do this. Anyone not assigned to the second table is assigned to the first table.

Obviously, these are equivalent, so the number of ways should be the same.

Eclair_de_XII said:

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

Every subset has a complement (which is another subset). The number of subsets equals the number of complements.

Eclair_de_XII

1. What is the formula for n choose k?

The formula for n choose k is n! / (k!(n-k)!), where n is the total number of objects and k is the number of objects chosen.

2. How do you prove that n choose k is equal to n choose (n-k)?

To prove that n choose k is equal to n choose (n-k), we can use the definition of n choose k and the properties of factorials. By substituting (n-k) for k in the formula, we get n! / ((n-k)!((n-n+k)!)). Simplifying this expression gives us n! / (k!(n-k)!), which is the same as the formula for n choose k. Therefore, n choose k is equal to n choose (n-k).

3. Can you provide an example of n choose k being equal to n choose (n-k)?

Yes, for example, if we have a group of 6 people and we want to choose 3 of them to form a team, we can calculate this as 6 choose 3, which is equal to 6! / (3!(6-3)!) = 20. Alternatively, we can choose the remaining 3 people to not be on the team, which can be calculated as 6 choose (6-3) = 6! / (3!(6-3)!) = 20. Therefore, 6 choose 3 is equal to 6 choose (6-3).

4. Why is it important to understand the relationship between n choose k and n choose (n-k)?

Understanding the relationship between n choose k and n choose (n-k) can help us to simplify and solve problems involving combinations more easily. It also allows us to see that the number of combinations for choosing k objects from a group of n objects is the same as choosing n-k objects from the same group, which can be helpful in certain situations.

5. Are there any real-world applications of n choose k being equal to n choose (n-k)?

Yes, the concept of n choose k being equal to n choose (n-k) is used in various fields such as statistics, probability, and computer science. For example, in statistics, this relationship is used to calculate the probability of certain outcomes in a sample space. In computer science, it is used in algorithms for generating combinations. Understanding this relationship can also be useful in solving problems related to combinations in everyday life, such as choosing a team from a group of people or selecting items from a menu.

• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
17
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
2K