1
$\begingroup$

In today's quiz (about combinatorics) there was a question I was not able to solve mathematically:

Find the number of words with length 3 over an alphabet $ \Sigma = \{1,2,...,10\} $ where $x \lt y \le z$. ($x$ is the first letter, and so on).

How can I solve this in an efficient way? Of course you can just count it like:

$9 \times 10 \times 10 \rightarrow$ 1 possiblity
$8 \times \{9,10\} \times \{9,10,10\} \rightarrow$ 2 + 1 possibilities
....

But how do I solve it with "combinatoric" methods?

$\endgroup$

2 Answers 2

2
$\begingroup$

Think about it like this: If we had to choose $a,b,c$ from $\{1,2,\ldots,10\}$ so that $a < b < c$, we could just choose a subset of $3$ elements from $\{1,2,\ldots,10\}$ and sort them, giving $a < b < c$. The number of such subsets is $\binom{10}{3}$. Now, since we have $x < y \leq z$, we have $x < y < (z + 1)$; we may thus choose $3$ distinct elements from $\{1,2,\ldots,11\}$ (the three elements are $x$, $y$, and $z+1$). We thus have $\binom{11}{3}$ ways to do so, yielding $\binom{11}{3}$ as our answer. In other words, counting $x < y \leq z$ from $\{1,2,\ldots ,10\}$ is the same as counting $x < y < (z + 1)$ from $\{1,2,\ldots,11\}$.

$\endgroup$
3
  • $\begingroup$ @BrianO, I think there's a misunderstanding. The answer is $\binom{11}{3}$, not the sum of $\binom{11}{3}$ and $\binom{10}{3}$. $\endgroup$
    – Marcus M
    Oct 20, 2015 at 22:15
  • $\begingroup$ Note that $\binom{11}{3} = \binom{10}{3} + \binom{10}{2}$, so our answers agree. $\endgroup$
    – Marcus M
    Oct 20, 2015 at 22:18
  • 1
    $\begingroup$ Ohhh OK -- doh, sorry, I can plead interruptions :) Yes they're the same (good!). I'll delete my "Hmm, problem". $\endgroup$
    – BrianO
    Oct 20, 2015 at 22:40
1
$\begingroup$

There are two kinds of length 3 words $w = xyz$ satisfying the conditions that $x < y \le z$ and $x, y, z \in \Sigma = \{1, 2, 3, \dots, 10\}$:

  1. Those with $y = z$

    These are in 1-1 correspondence with the set of all 2-element subsets of $\Sigma$, so there are $\binom {10} 2$ of them.

  2. Those with $y < z$

    These are in 1-1 correspondence with the set of all 3-element subsets of $\Sigma$, so there are $\binom {10} 3$ of them.

So the number of strings satisfying the conditions is $$ \begin{align} \binom {10} 2 + \binom {10} 3 &= 45 + 120 \\ &= 165 \text{.} \end{align} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .