5
$\begingroup$

We're only considering lowercase letters, repetition is allowed.

Number of strings of length $4 = 26^4$
Number of strings of length $4$ other than $x = 25^4$
$26^4-25^4 = 66,351$ strings.

This is one solution. But i was thinking of this problem as...

We have $4$ possible positions for $x$. After $x$ is placed, there are $3$ places left. And we have $26^3$ possibilities for those positions.
So, strings that have letter $x = 4\cdot (26^3) = 70304$ strings.

What is wrong with this approach?

$\endgroup$
5
$\begingroup$

You will have to make $4$ cases:-

  1. Only one 'x' : you can place it at any one of the four available places and fill remaining three places with remaining $25$ letters in $4\choose1$$\cdot25^3$ ways.
  2. Two 'x'es : choose two places and then fill remaining two places with any of remaining $25$ letters in $4\choose2$$\cdot25^2$ ways.
  3. Three 'x'es : choose three places and fill remaining one place with any of remaining 25 letters in $4\choose3$$\cdot25^1$ ways.
  4. Four 'x'es : There is only one possible case i.e. xxxx.

So, total number of combinations combinations are, $4\cdot25^3+$$4\choose2$$\cdot25^2+$$4\choose3$$\cdot25^1+1=66351$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well explained. Thanks. $\endgroup$ – user3834119 Dec 28 '14 at 9:48
3
$\begingroup$

What is wrong is overcounting, as JimmyK4542 pointed out. You can try to remedy that by inclusion-exclusion, and it works fairly well here.

You've got sets $A_1,A_2,A_3,A_4$ of strings with $x$ in position $1,2,3,4$, respectively, each with $26^3$ elements, and you need to count the elements of their union $A_1\cup A_2\cup A_3\cup A_4$. A first approximation is $|A_1|+|A_2|+|A_3|+|A_4|$, but this counts every string as often as the number of letters $x$ it contains. Strings that contain at least two copies of $x$ lie in some intersection $A_i\cap A_j$ with $i<j$, so one can get the count straight for words with two copies of $x$ by subtracting $|A_i\cap A_j|$ for every such pair $(i,j)$ (there are $\binom42=6$ such pairs). One easily sees that $|A_i\cap A_j|=26^2$ for any such pair. But now the count is off for strings that contain three letters $x$: they have been counted $3$ times initially, but then counted negatively $3$ times (once for each of the $\binom32=3$ pairs $(i,j)$ for which it contributed. A remedy is adding back $|A_i\cap A_j\cap A_k|=26$ for every $i<j<k$. Now the count is right for every string except $xxxx$, which has been counted $\binom41-\binom42+\binom43=2$ times, so we must subtract $1$ to get its count right. It is a general fact that intersections of $m$ distinct sets $A_i$ should contribute with sign $(-1)^{m-1}$. $$\begin{align} |A_1\cup A_2\cup A_3\cup A_4| &=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_j|-|A_1\cap A_2\cap A_3\cap A_4|\\ &=\sum_{m=1}^4(-1)^{m-1}\binom4m26^m\\ &=4\times17576-6\times767+4\times26-1\times1 = 66351. \end{align} $$ You can recognise the second line as the binomial formula for $(26-1)^4$, except that the sign is opposite and the initial term $1\times 26^4$ is missing; so your result should be equal to $26^4-(26-1)^4=26^4-25^4$, which indeed it is by the argument initially given in your question.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Your approach double counts strings like "xxyy", "xyax", "bcxx", etc. which have an x in more than one position. Hence, you end up with a larger result than the actual answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Alright. Then how can we use this approach to get the correct answer? $\endgroup$ – user3834119 Dec 28 '14 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.