Combinations
Binomial Coefficient
The binomial coefficient, denoted as C[n][k]
represents the number of ways to choose k elements from a set of n elements without regard to the order
.
It is used in combinatorics to solve problems where you need to select subsets from larger sets.
Problems
- Counting Combinations. A class has 12 students, and the teacher needs to form a committee of 5 students. How many different ways can the committee be selected? This is a simple combination problem where order does not matter. The answer is the number of ways to choose 5 students from 12, which is
C(12,5)
. - Handshakes in a Group. In a group of 10 people, each person shakes hands with every other person exactly once. How many handshakes occur? Each handshake involves 2 people, so this is equivalent to choosing 2 people from a group of 10. The number of handshakes is
C(10,2)
. - Paths in a Grid. You are at the top-left corner of a 5x5 grid, and you want to reach the bottom-right corner. You can only move right or down. How many distinct paths can you take?
- Lottery Problem. In a lottery, you pick 6 numbers from a set of 49 numbers. How many different sets of 6 numbers can you choose?
- Forming Teams. There are 8 girls and 7 boys in a club. You need to form a team of 4 people, where at least 2 members are girls. How many different teams can be formed?
- Binary Strings with a Fixed Number of 1’s. How many binary strings of length 8 have exactly 3 ones?