I'm trying to do this combinatorics problems out of KHEE-MENG KOH's "Principles and Techniques of Combinatorics" and am getting overwhelmed.
We want to find the number of distinct 2-letter strings that can be formed from the word ALGEBRA.
My approach:
We have 6 distinct letters from the seven letters in ALGEBRA.
So, I choose 2 of those those 6 letters and we can permute those 2 letters (i.e. AL and LA are two different strings) and then add the one string "AA"
$$ (2!){6 \choose 2} + 1 = 30 + 1 = 31$$
So we can make 31 distinct strings from the word ALGEBRA.
According to the solutions:
Of the 7 letters, we choose 2 to make a string. We then subtract the duplicates. There are 5 strings that begin with A and 5 strings that end with A that are counted twice. As a result
$$(2!) {7 \choose 2} – 10 = 32$$
We have 32 strings that can be formed from the word ALGEBRA.
Aren't they forgetting that "A_1 A_2" and "A_2 A_1" are the same string (i.e. "AA" = "AA"), so shouldn't they subtract by eleven for a total of 31 distinct strings?
Best Answer
You are correct. Another approach:
Consider the six distinct letters: $A,L,G,E,B,R$.
For the first element of the string we can choose a letter in $6$ ways, and for the second element we can choose from any of the remaining $5$ letters, yielding a total of $6 \times 5 = 30$ choices for the two letter string. Now, add another letter 'A' into the possible choices for letters. Notice combinations of the letter 'A' and any other letter were already considered before, and the only combination missing is 'AA'.
So, in total there are $31$ ways to choose the string.