To find the arrangement of given letters so that there is fixed number of transition between them.

105 Views Asked by At

A 10 letter word is composed of $P,\ Q,\ R,\ S$. The problem is to find the number of arrangements of these letters which could lead to a fixed number of transitions between each pair of letters.

Example, consider the following arrangement of $P,\ Q,\ R,\ S$ given as $PQPRSPQRSS$ has $3\ P$, $2\ Q$, $2\ R$, $3\ S$ has $3$ transitions between $P$ and $Q$, $1$ transition between $P$ and $R$, $1$ transition between $P$ and $S$, $2$ transition between $R$ and $S$ and $1$ transition between $Q$ and $R$.

The question here is to find the number of ways it can be arranged so that the transition between alphabets remains conserved.

1

There are 1 best solutions below

1
On BEST ANSWER

Consider a $4 \times 4$ symmetric matrix $M$ with entries $m_{ij}$ and diagonal entries $1$. I'll label the indices $1,2,3,4$ as $P,Q,R,S$. Each entry of $M^{9}$ is a polynomial of total degree $ \le 9$ in the $m_{ij}$, where the coefficient of each monomial in $M^9_{ij}$ gives the number of $10$-letter words starting with $i$, ending with $j$, and with the numbers of transitions specified by the monomial. Thus for the number with $3$ transitions between $P$ and $Q$, $1$ between $P$ and $R$, $1$ between $P$ and $S$, $1$ between $Q$ and $R$, $2$ between $R$ and $S$, and $0$ for the other pairs, you would take the coefficient of $m_{PQ}^3 m_{PR} m_{PS} m_{QR} m_{RS}^2$. Since you don't care where you start and end, add these for all $i,j$. Using Maple I get $288$.