Combination problem

[Lewis1245]

How to do?

[HallsofIvy]

The first part is easy- if each name as n letters and each letter has only two possible values then there are [tex]2^n[/tex] possible names so [tex]2^n[/tex] islands. There is a ferry route between two islands if and only if their names differ by one letter. In the example with 3 letters, the island Aaa has a ferry route to Baa, Aba, and Aab. Since there are 3 letters in the name, there are 3 letters that can change. If each name has n letters then each island has ferry routes to n other islands. Since there are [tex]2^n[/tex] islands there would be [tex]n(2^n)[/tex] routes except[b] that each route involves [b]2 islands. To correct for that, divide by 2. There are [tex]n(2^{n-1})[/tex] ferry routes.

[Guest]

A Big Example
Suppose we wish to arrange n=5 people {a,b,c,d,e}

Table 1 — Permutations of {a,b,c,d,e}

Table 2 — Permutations of {a,b,c,d,e}, taken 3 at a time

Table 3 — Combinations of {a,b,c,d,e}, taken 3 at a time

For more explanation, let's visit the post Find Difference Between Permutations and Combinations With The Best Summary