In how many ways can the word MATHEMATICS be partitioned?
A partition here is completely described once I tell you where the cuts are (e.g. if I tell you "cut after the E and the I, the partition must be MATHE/MATI/CS). The restriction that each piece must contain a vowel leads to two further restrictions:
- No cut can be located before the first A or after the I.
- Between any two vowels, there can be at most 1 cut.
So if I want to describe the cuts to you, I can tell you first what cut (if any) is located between the first A and the E, then what cut (if any) is located between the E and the second A, then what cut (if any) is located between the second A and the I.
That's three things I need to tell you. How many possibilities are there for each of those things?
Here is a proposal to systematically derive the number of wanted partitions. The word \begin{align*} M\color{blue}{A}TH\color{blue}{E}M\color{blue}{A}T\color{blue}{I}CS \end{align*} contains four vowels and since each part of a valid partition has to contain at least one vowel we can subdivide the word in one, two, three or four parts. In the following we classify partitions by the number of valid parts they contain.
Example: (1,1,2)
The $3$-tuple $(1,1,2)$ denotes the valid partitions consisting of three parts. The first two parts contain one vowel, the third part contains two vowels. We mark the letters blue which are elements of a certain part in any case and leave the other letters marked black. \begin{align*} \color{blue}{MA}\,\mathbf{TH}\color{blue}{E}\,\mathbf{M}\color{blue}{ATICS}\quad\longrightarrow\quad 3\cdot 2 = 6 \end{align*}
-
Since the string $TH$ has length $2$ we have three choices: zero, one or two letters which can be element of the left part.
-
To each of these choices we have the string $M$ which has length $1$ and which gives us two choices: zero of one letter which can be element of the left part.
-
This gives a total of $3\cdot 2=6$ valid partitions of type $(1,1,2)$.
Using this approach we obtain \begin{align*} \begin{array}{l|l|l} \text{pattern}&\quad \text{partition type}&\quad \text{nr partitions}\\ \hline &&\\ \color{blue}{MATHEMATICS}&\quad(4)&\quad 1\\ &&\\ \color{blue}{MA}\,\mathbf{TH}\,\color{blue}{EMATICS}&\quad(1,3)&\quad 3\\ \color{blue}{MATHE}\,\mathbf{M}\,\color{blue}{ATICS}&\quad(2,2)&\quad 2\\ \color{blue}{MATHEMA}\,\mathbf{T}\,\color{blue}{ICS}&\quad(3,1)&\quad 2\\ &&\\ \color{blue}{MA}\,\mathbf{TH}\,\color{blue}{E}\,\mathbf{M}\,\color{blue}{ATICS}&\quad(1,1,2)&\quad 3\cdot 2=6\\ \color{blue}{MA}\,\mathbf{TH}\,\color{blue}{EMA}\,\mathbf{T}\,\color{blue}{ICS}&\quad(1,2,1)&\quad 3\cdot 2=6\\ \color{blue}{MATHE}\,\mathbf{M}\,\color{blue}{A}\,\mathbf{T}\,\color{blue}{ICS}&\quad(2,1,1)&\quad 2\cdot 2=4\\ &&\\ \color{blue}{MA}\,\mathbf{TH}\,\color{blue}{E}\,\mathbf{M}\,\color{blue}{A}\,\mathbf{T}\,\color{blue}{ICS}&\quad(1,1,1,1)&\quad 3\cdot 2\cdot 2=12\\ \end{array} \end{align*}
Adding up the number of partitions we find \begin{align*} 1+(3+2+2)+(6+6+4)+12=1+7+16+12\,\color{blue}{=36} \end{align*} in accordance with the claim.