Concept map / Counting
Share
Permutations and combinations
Count selections of distinct tokens with and without regard to order, then count response patterns that yield a given test score.
1Pick 2 of 4 tokens, with and without order
Pick two of the tokens A, B, C and D, without using any token twice. If AB and BA count as different, there are 12 ways. If they are the same pair, there are 6. The second kind of count is the one behind test scores: how many ways a student can get exactly 5 of 10 items right.
Change n, the number of tokens, and r, the number you pick. Then switch views and watch the different orders of the same tokens gather into one group.
Choosing 2 of 4 tokens with the order kept gives 12 arrangements: 4 choices for the first place, then 3 for the second, so 4 × 3 = 12. Rows such as AB and BA count separately here.
2How many ways to score 5 out of 10?
A quiz has 10 items, each marked right or wrong. A response pattern records which items were right, so there are 2 × 2 × … × 2 = 1,024 patterns. Scores run from 0 to 10. How many of the 1,024 patterns give a score of exactly 5?
3Why you divide by r!
An ordered choice is a permutation. A choice that ignores order is a combination, written "n choose r". The exclamation mark is a factorial: n! = n × (n − 1) × … × 1, the number of ways to line up n different things, with 0! = 1. Each group of r tokens shows up r! times in the ordered list, so dividing by r! counts it once.
Point at a colored part of the formula to see what it counts.
With your numbers (n = 4, r = 2): ordered = 4!/2! = 4 × 3 = 12. Each group repeats 2! = 2 × 1 = 2 times, so groups = 12 ÷ 2 = 6.
Show the two steps with your tokens
Step 1. Fill the 2 places one at a time. Each token you use is no longer available for the next place.
Step 2. Take any one group, here A, B. It appears in the ordered list 2 times, once for each order its 2 tokens can be put in.
4Score patterns on a right-or-wrong test
A score of k out of n depends on which k items are right, not on any order, so it can happen in "n choose k" ways. Each item is right or wrong, so an n-item test has 2n response patterns in all. The bars sort them by score. Click a bar, or use k, to pick a score.
A test of 5 right/wrong items has 32 possible response patterns. 10 of them give a score of exactly 2, because there are 10 ways to choose which 2 of the 5 items are right. That is 31.3% of all patterns, and no score has more. A score of 3 has the same count, since choosing the 2 right items is the same as choosing the 3 wrong ones.
5Check yourself
The tasks use the tokens in section 1 and the test chart in section 4, and tick themselves when you meet them.
- Find a choice with 120 ordered arrangements but only one group, and collapse it with "Order does not matter".Now: 12 ordered arrangements, 6 groups, view: order matters
- In the test chart, set a 10-item test and find a score that can be reached in exactly 120 ways.Now: 5 items, score 2: 10 ways
- Find the shortest test whose most common score can be reached in more than 1,000 ways, and select that score.Now: 5 items: most common score has 10 ways, selected score 2 has 10
6Count them in R
Base R has factorial(), choose() and combn() for these counts. The snippet uses the lab’s starting setup, two of four tokens and a five-item test, so it prints 12 ordered selections, 6 groups and 10 patterns with a score of two.
Count permutations, combinations and response patternsShow the code
# Four tokens, choose two, as on the page
n <- 4
r <- 2
# Ordered selections: n! / (n - r)!
factorial(n) / factorial(n - r)
# Unordered selections: divide by the r! orders of each group
choose(n, r)
# The groups themselves
apply(combn(LETTERS[1:n], r), 2, paste, collapse = "")
# A five-item test: patterns in all, then patterns per score
items <- 5
2^items
setNames(choose(items, 0:items), 0:items)
# Ten items: 1,024 patterns, 252 of them with a score of five
c(2^10, choose(10, 5))Uses base R only.
What the counts show
- Picking r of n distinct tokens in order gives n!/(n − r)! arrangements, because each pick leaves one fewer token.
- Each set of r tokens appears in r! orders, so dividing by r! counts every set once.
- Choosing which r tokens to take also decides which n − r are left, so “n choose r” equals “n choose n − r”.
- Each right-or-wrong item doubles the number of response patterns. Ten items give 1,024 patterns, and 252 of them have exactly five right.
- When items are answered independently with the same chance of being right, these counts give the binomial distribution of test scores.
Recommended reading
- Contemporary MathematicsOpenStaxChapter 7, counting, permutations, and combinations