
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Binomial Coefficients in Discrete Mathematics
Binomial coefficients are used not only in combinatorics, but also in probability and algebra. They are useful in counting, especially when we are choosing elements from a set without considering the order. Binomial coefficients are nothing but the expansion of binomials. They are expressions of the form $\mathrm{(x + y)^n}$. Every time we multiply out a binomial like this, the binomial coefficients are useful in figure out the size of the terms in the expansion.
Read this chapter to learn what binomial coefficients are and how to calculate them.
What are Binomial Coefficients?
As we know, a binomial coefficient is written using a notation that looks like this −
$$\mathrm{\binom{n}{k}}$$
This is read as "n choose k" and represents the number of ways to choose k elements from a set of n elements. Here we do not have to care about the order. For instance, if we want to know how many ways there are to choose 2 items out of 5 (like we are picking 2 apples from a basket of 5 different apples), we would use the binomial coefficient .
$$\mathrm{\binom{5}{2}}$$
The formula for calculating binomial coefficients is −
$$\mathrm{\binom{n}{k} \:=\: \frac{n!}{k!(n\:-\:k)!}}$$
The n! means "n factorial," which is the product of all positive integers from 1 up to n. For example,
$$\mathrm{5! \:=\: 5\: \times\: 4\: \times\: 3\: \times\: 2\: \times\: 1 \:=\: 120}$$
Example of Calculating a Binomial Coefficient
Let us work through an example. If we wanted to know how many ways we can select 3 objects out of 5, we would calculate $\mathrm{\binom{5}{3}}$.
$$\mathrm{\binom{5}{3} \:=\: \frac{5!}{3!(5\:-\:3)!} \:=\: \frac{5 \:\times\: 4 \:\times\: 3!}{3!2!} \:=\: \frac{5 \:\times\: 4}{2!} \:=\: 10}$$
So, there are 10 ways to choose 3 objects from a group of 5.
Binomial Expansions
Now that we understood how to calculate binomial coefficients, let us go through how they fit into the expansion of binomials. Suppose we want to expand the expression $\mathrm{(x \:+\: y)^n}$. The binomial coefficients will tell us the coefficients of the terms in the expanded version of this expression.
For example, when we expand $\mathrm{(x \:+\: y)^3}$, we get −
$$\mathrm{(x \:+\: y)^3 \:=\: x^3 \:+\: 3x^2y \:+\: 3xy^2 \:+\: y^3}$$
See, the numbers in front of the terms: 1, 3, 3, and 1. These are binomial coefficients! They tell us how many times each combination of x and y appears in the expansion. In this case, the coefficients come from $\mathrm{\binom{3}{0},\: \binom{3}{1},\: \binom{3}{2}}$ and $\mathrm{\binom{3}{3}}$.
Expanding Larger Binomials
Let us expand $\mathrm{(x \:+\: y)^5}$. Using the binomial coefficients, we can expand it like −
$$\mathrm{(x \:+ \:y)^5 \:=\: x^5 \:+\: 5x^4y \:+\: 10x^3y^2 \:+\: 10x^2y^3 \:+\: 5xy^4 \:+\: y^5}$$
Again, the binomial coefficients here are $\mathrm{\binom{5}{0} \:=\: 1,\: \binom{5}{1} \:=\: 5,\: \binom{5}{2} \:=\: 10,\: \binom{5}{3} \:=\: 10,\: \binom{5}{4} \:=\: 5}$ and $\mathrm{\binom{5}{5} \:=\: 1}$ These coefficients help us to expand the binomial quickly and correctly.
Binomial Coefficients and Counting Problems
Binomial coefficients are also useful in counting problems. When we find out how to choose things from a group, we are likely using binomial coefficients, even if we do not realize it. Let us see this claim through examples.
Example 1: Choosing a Subset
Consider we have a set of five elements, say {1, 2, 3, 4, 5} and we want to know how many ways we can select three elements from that set. This is exactly the same problem as asking for $\mathrm{\binom{5}{3}} $, which, as we calculated earlier, is 10. So, there are 10 ways to pick a subset of three elements from a set of five.
Example 2: Forming Committees
Here is another example where we are organizing a committee and need to pick 2 members from a group of 6 people. The number of ways we can do this is $\mathrm{\binom{6}{2}}$, which is calculated as −
$$\mathrm{\binom{6}{2} \:=\: \frac{6!}{2!(6\:-\:2)!} \:=\: \frac{6 \:\times\: 5 \:\times\: 4!}{2!4!} \:=\: \frac{30}{2!} \:=\: 15} $$
So, there are 15 different ways to form this 2-person committee from the 6 people.
Recurrence Relation for Binomial Coefficients
Other aspect for binomial coefficients are they follow a recurrence relation. This means that we can calculate any binomial coefficient based on smaller binomial coefficients. Specifically, the relation is −
$$\mathrm{\binom{n}{k} \:=\: \binom{n\:-\:1}{k\:-\:1} \:+\: \binom{n\:-\:1}{k}}$$
What this says is that to calculate $\mathrm{\binom{n}{k}}$, we can add up two smaller coefficients: $\mathrm{\binom{n\:-\:1}{k\:-\:1}}$ and $\mathrm{\binom{n\:-\:1}{k}}$. This relationship is useful because it lets us build up larger binomial coefficients from smaller ones.
Example of Recurrence Relation
Let us see some example. Say we want to calculate $\mathrm{\binom{5}{3}}$, but we do not want to use the factorial formula. Instead, we can break it down using the recurrence relation −
$$\mathrm{\binom{5}{3} \:=\: \binom{4}{2} \:+\: \binom{4}{3}}$$
We know from earlier that $\mathrm{\binom{4}{2}}$ is 6 and $\mathrm{\binom{4}{3}}$ is 4, so
$$\mathrm{\binom{5}{3} \:=\: 6 \:+ \:4 \:=\: 10}$$
We get the same result as before, but by using smaller pieces to build up the solution.
Pascals Triangle
Another way to visualize binomial coefficients is through the Pascals Triangle. The Pascals Triangle is a triangular arrangement of binomial coefficients, where each number is the sum of the two numbers directly above it.
Here is a small version of Pascals Triangle −

Each row corresponds to the binomial coefficients for a particular power of a binomial expansion. The top row (1) corresponds to $\mathrm{(x \:+\: y)^0}$, the next row (1, 1) corresponds to $\mathrm{(x \:+\: y)^1}$, and so on.
We can use Pascals Triangle to quickly find binomial coefficients. For example, to find $\mathrm{\binom{5}{3}}$, just look in the sixth row (because it corresponds to $\mathrm{(x \:+\: y)^5}$ and find the fourth number, which is 10.
Conclusion
In this chapter, we explored what binomial coefficients are and how they are used in discrete mathematics. We explained their role in expanding binomials and how to calculate them using both factorials and Pascals Triangle. We also understood the recurrence relation that binomial coefficients follow, which makes them easy to calculate step by step.
In the next chapter, we will discuss the Pascals triangle in more detail with its applications and where we could use them.