0
$\begingroup$

Using an alphabet of $n$ letters, how many middle peaked words of length 5 are there?

Let's define "middle peaked word" as a word with the middle letter dividing the word into two. To the left of this peak letter, the letters increase (are ordered alphabetically) and to the right of this peak letter, the letters decrease (are ordered reverse-alphabetically). For example: A < D < L > K > B.

I've been really struggling with this problem. I tried splitting into three, for example :

________ | _ | ________

With the left space being a word with "increasing" order. So how many ways can this word be chosen? This word would be of length 2 and chosen from an alphabet of $n$ letters, so the number of ways to choose this word is $\binom{2+n-1}{2}$. But I'm not sure where to go after this because the second word (of reverse alphabetical order) would have less options than $n$ since it needs to decrease from whatever is chosen as the peak.

$\endgroup$
2
$\begingroup$

Hint: Instead of picking the initial two letters first, pick the middle letter first.

More details are hidden below:

If you choose letter $k$ for the middle letter, then you have $\binom{k-1}{2}$ choices each for the first two letters and the last two letters. So in total you have $\sum_{k=1}^{n}\binom{k-1}{2}^2$ possible words. If you want you can turn this into a closed form which will be a polynomial in $n$ of degree $5$, since $\binom{k-1}{2}^2$ is a degree $4$ polynomial in $k$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What if all 5 letters need to be distinct? $\endgroup$ – big_math_boy May 14 at 20:10
  • $\begingroup$ You can use the same method, you'll just have fewer choices for the last two letters. Alternatively, you could first choose an unordered set of 5 letters and then count how many ways there are to order it. $\endgroup$ – Eric Wofsey May 14 at 20:31

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.