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.

Your 4 tokens:ABCD
Or click a row.
Ordered arrangements12
Rows per group (r!)2
Groups, order ignored6

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.

ordered=n!(n−r)!groups=(nr)=n! / (n−r)!r!=n!(n−r)!  r!\begin{aligned}\text{ordered} &= \htmlClass{term-cntarr}{\frac{n!}{(n-r)!}} \\[10pt] \text{groups} &= \binom{n}{r} = \frac{\htmlClass{term-cntarr}{n!\,/\,(n-r)!}}{\htmlClass{term-cntrep}{r!}} \\[6pt] &= \frac{n!}{(n-r)!\;r!}\end{aligned}

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.

Number of patterns with this scoreScore k (items right out of 5)10511021035415
RightWrongEach strip is one pattern, item 1 on the left

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