CHAPTER 1 - Combinatorics - Basic Counting Principle and Combinatorics

Oct 13, 2026

Chapter 1 introduces core ideas in combinatorics: the basic counting principle, permutations, and combinations. It starts with counting strategies for sequential choices using multiplication, illustrated with examples on outfits and license plate numbers. It then explains permutations via factorials, covering arrangements with distinct items and repeats, including general formulas. Finally, it derives combination formulas (binomial coefficients), shows how to select committees, and extends to related identities and multinomial counting for partitioning sets.

LanguageEnglish

CategoryPaper Templates

FormatPDF

Pages18

Reading Time6 min

AccessFree to download

CHAPTER 1

Basic counting principle and combinatorics

Permutations

Combinations (binomial coefficients)

Combinations (multinomial coefficients)

CHAPTER 1 Combinatorics 1.1. Basic counting principle and combinatorics 1.1.1. Basic counting principle. The ✜rst basic counting principle is to multiply. Namely, if there are n possible outcomes of doing something and m outcomes of doing another thing, then there are m 􀀁 n possible outcomes of performing both actions. Basic counting principle Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes, and if for each outcome of experiment 1 there aren possible outcomes of experiment 2, then there are m 􀀁 n possible outcomes of the two experiments together. Example 1.1 . Suppose we have 4 shirts of 4 di✛erent colors and 3 pants of di✛erent colors. How many di✛erent out✜ts are there? For each shirt there are 3 di✛erent colors of pants, so altogether there are 4 􀀂 3 = 12 possibilities. Example 1.2 . How many di✛erent license plate numbers with 3 letters followed by 3 numbers are possible? Solution: (26)3 (10)3 . Indeed, the English alphabet has 26 di✛erent letters, therefore there are 26 possibilities for the ✜rst place, 26 for the second, 26 for the third, 10 for the fourth, 10 for the ✜fth, and 10 for the sixth. We multiply. 1.1.2. Permutations. How many ways can one arrange letters a; b; c? We can list all possibilities, namely, abc acb bac bca cab cba: There are 3 possibilities for the ✜rst position. Once we have chosen the letter in the ✜rst position, there are 2 possibilities for the second position, and once we have chosen the ✜rst two letters, there is only 1 choice left for the third. So there are 3 􀀂 2 􀀂 1 = 6 = 3! arrangements. In general, if there are n distinct letters, there are n! di✛erent arrangements of these letters. Example 1.3 . What is the number of possible batting orders (in baseball) with 9 players? ➞ Copyright 2013 Richard F. Bass, 2020 Masha Gordina Typesetting date: March 31, 2020 4 1. COMBINATORICS Solution: 9! = 362880 . Example 1.4 . How many ways can one arrange 4 math books, 3 chemistry books, 2 physics books, and 1 biology book on a bookshelf so that all the math books are together, all the chemistry books are together, and all the physics books are together? Solution: 4! 􀀁 (4! 􀀁 3! 􀀁 2! 􀀁 1!) = 6912 . We can arrange the math books in 4! ways, the chemistry books in 3! ways, the physics books in 2! ways, and the biology book in 1! = 1 way. But we also have to decide which set of books go on the left, which next, and so on. That is the same as the number of ways of arranging of four objects (such as the letters M; C; P; B), and there are 4! ways of doing that. In permutations the order does matter as is illustrated by the next example. Example 1.5 . How many ways can one arrange the letters a; a; b; c? Let us label them ✜rst as A; a; b; c. There are 4! = 24 ways to arrange these letters. But we have repeats: we could have Aa or aA which are the same. So we have a repeat for each possibility, and so the answer should be 4!=2! = 12 . If there were 3 as, 4 bs, and 2 cs, we would have 3!94!!2! = 1260 : What we just did is called ✜nding the number of permutations. These are permutations of a given set of objects (elements) unlike the example with the licence plate numbers where we could choose the same letter as many times as we wished. Permutations The number of permutations of n objects is equal to n! := 1 􀀁 ::: 􀀁 n; with the usual convention 0! = 1 . 1.1.3. Combinations. Now let us look at what are known as combinations. Example 1.6 . How many ways can we choose 3 letters out of 5? If the letters are a; b; c; d; e and order matters, then there would be 5 choices for the ✜rst position, 4 for the second, and 3 for the third, for a total of 5 􀀂 4 􀀂 3. Suppose now the letters selected were a; b; c. If order does not matter, in our counting we will have the letters a; b; c six times, because there are 3! ways of arranging three letters. The same is true for any choice of three letters. So we sho

FAQs

What does the basic counting principle say in this chapter?

When one task has n possible outcomes and another task has m possible outcomes, the total number of outcomes for performing both actions is m × n.

How are permutations counted?

For n distinct objects, the number of permutations is n!, based on arranging choices position by position.

How are combinations (binomial coefficients) counted when order does not matter?

The number of ways to choose k objects from n is given by C(n, k) = n! / (k!(n-k)!), since orderings of the chosen set are disregarded.

Oct 13, 2026

Upload by Taylor Morgan