Combinatorics Progress
Completed0/11
0 completed0 in progress
Pascal's Triangle
Pascal's Triangle and its applications in combinatorics.
Author: Alexander Ren
Pascal's Triangle is an infinite triangle of numbers where each number is the sum of the two numbers directly above it. The top of the triangle starts with a single 1. Each subsequent row starts and ends with 1, and any other number in the row is the sum of the two numbers above it. The first few rows of Pascal's Triangle look like this:
Pascal's Triangle has a direct link to combinatorics through binomial coefficients, which are used in binomial expansions and combinaorial calculations such as permutations and combinations. Each number in Pascal's Triangle represents a binomial coefficient, denoted as
or
which calculates the number of ways to choose elements out of a set of elements, regardless of the order.
The formula for calculating a binomial coefficeint is:
Here are some basic examples.
Calculate using Pascal's Triangle.
To find look at the th row (remember, the row count stars from ) and the rd number in that row because indexing starts at This corresponds to the number in the row for and the position for which is
Therefore,
How many ways can you choose books from a shelf of books?
This problem is asking for the value of Using Pascal's Triangle, we find this in the th row, th position, which is
Therefore, there are ways to choose books out of
The Hockey Stick Pattern says that:
The name hockey stick comes from the shape of the numbers.
Here's an example.
As you can see, or
The Hockey Stick pattern can simplify calculations involving combinations. For example, if you want to find the sum of combinations instead of calculating each combination and then summing them, you can directly use the Hockey Stick theorem. The sum corresponds to according to the pattern.