Computer Science I / Counting and Combinatorics
Practice question · Multiple choice

Choosing 2 items from 5 gives 10 combinations and 20 permutations. Why is the permutation count exactly twice the combination count here, and what would the factor be for choosing 3?

Hints
  1. Take the pair {A, B}. How many ordered arrangements does it correspond to?
  2. Now take {A, B, C}. How many orderings?
Show the answer

C. Because each combination can be ordered in 2! ways, counted separately.

Why

The pair {A, B} corresponds to AB and BA, so permutations count it twice; for a set of three there are 3! = 6 arrangements. Read P(n,k) = C(n,k)·k! as a combination being a permutation with the ordering forgotten. Both are defined without repetition, deciding whether order matters and whether repetition is allowed is most of the difficulty in elementary counting.

Read the lesson: Counting and Combinatorics →

Practise Counting and Combinatorics

The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.

More questions on Counting and Combinatorics