I can find the answers to similar questions online, but what I'm trying to do is develop my own intuition so I can find the answers. I am quite sure I am wrong, so could you look over my reasoning?

If $X = (1,2,3,4,5,6,7,8)$,

  1. How many strings over X of length 5?

Reasoning: Each character of the string is a choice of a selection from the string, so $8^5$.

  1. How many strings over X with length 5 don't contain $1$?

Reasoning: This is equivalent to strings of length 5 of an alphabet not containing $1$, so $7^5$.

  1. How many strings over X with length 5 contain $1$?

Reasoning: First get the strings for length 4 ($8^4$). Then select a position to insert a 1 ($5$). Compounded: $5\times 8^4$.

At this point I saw $8^5 \ne 7^4 + 5 \times 8^4$ and lost motivation. I am more sure 1 and 2 are correct than 3 so perhaps the simplest solution would be just $8^5-7^5$, but my logic for 3 "feels" sound. I am frustrated because I have never had these kinds of difficulties before. I look at solutions and though they too "feel" correct, I'd not have come up with them.

I apologize for the irregular question form, and understand if this isn't the site for this.

  • 2
    $\begingroup$ Your reasoning for $3$ is not correct. You might have more than a single $1$. Hint: what do you get if you subtract the answer to $2$ from the answer to $1$? $\endgroup$ – lulu Mar 29 '18 at 15:27
  • $\begingroup$ @lulu I tried to consider that. 8^4 accounts for even all of the other letters being 1, does it not? I am afraid I do not see how it is wrong. $\endgroup$ – Ryan Cedar Mar 29 '18 at 15:30
  • 1
    $\begingroup$ the answer to $\#1$ counts all the strings with no restriction. The answer to $\# 2$ counts all those with no $1's$. So the difference must be those strings that have at least one $1$. $\endgroup$ – lulu Mar 29 '18 at 15:31
  • $\begingroup$ But @lulu, you aren't explaining the flaw in the reasoning for 3. The problem, Ryan, is that you have overcounted -- you've counted many strings more than once. Consider, for example, the string consisting of all 1s. $\endgroup$ – symplectomorphic Mar 29 '18 at 15:35
  • $\begingroup$ $8^4$ contains all of X including the "1"s. $\endgroup$ – Rudi_Birnbaum Mar 29 '18 at 15:36

The problem with the third argument is that it counts some valid strings twice (or more).

For example the string 12341 is counted as [1][2341] and [1234][1].

The other way (subtracting the number of strings without '1's from the number of total strings) is correct, and it's indeed the simplest way.

Elsewhere, you could correct the overcounting by inclusion-exclusion :

$$ \binom51 8^4 - \binom52 8^3 + \binom53 8^2 - \binom54 8^1 + 1 = 15961 $$

Alternatively, you could count all the strings with exactly $1,2 \cdots 5$ ones, as in @drhab's answer.

BTW: you say

At this point I saw $8^5 \ne 7^4 + 5 \times 8^4$ and lost motivation.

You definitely shouldn't. On the contrary, to fall into that "trap" (and to realize there's something is wrong, and learn why) is rather the point of this problem.

  • $\begingroup$ Thank you, I understand perfectly now. In fact, it seems trivial to realize. Yet I similarly have this issue for other problems of combinatorics :(. $\endgroup$ – Ryan Cedar Mar 29 '18 at 18:11

What you call simplest solution is a correct one (and by far the most simple and elegant one).

If you still insist to go the other direction then your answer must be:$$\binom51\times7^4+\binom52\times7^3+\binom53\times7^2+\binom54\times7^1+\binom55\times7^0=15961$$

Here $\binom5{k}$ is the number of ways to choose $k$ ones among $5$ candidates.


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.