Page:Philosophical Transactions of the Royal Society A - Volume 184.djvu/999

63. Hence the number of lines of route through the reticulation which possess exactly $s$ essential nodes is equal to the number of permutations of the letters in

$\alpha _{1}^{p_{1}}\alpha _{2}^{p_{2}}\,.\,.\,.\,\alpha _{n}^{p_{n}},$

for which

$r_{2}+r_{3}+\,.\,.\,.\,+r_{n}=s\;;$

$r_{l}$ denoting the number of times that the letter $\alpha _{l}$ occurs in the first

$p_{1}+p_{2}+\,.\,.\,.\,+p_{l-1}$

places of permutation.

64. We are at once led to an important identity of enumeration in the pure theory of permutations. Following the nomenclature of a previous section of the investigation, a line of route through the reticulation is traced out by a succession of steps, each step being an $\alpha _{1}$ step or an $\alpha _{2}$, &c., or an $\alpha _{n}$ step.

The whole length of the line of route there are altogether $p_{1},\alpha _{1}$ steps, $p_{2},\alpha _{2}$ steps, &c.,$\,.\,.\,.\,p_{n},\alpha _{n}$ steps.

Without regard to the characteristic of lines of route in respect of essential nodes, the whole number of lines of route is equal to the number of different orders in which these steps can be taken, viz., equal to the whole number of permutations of the letters in

$\alpha _{1}^{p_{1}}\alpha _{2}^{p_{2}}\,.\,.\,.\,\alpha _{n}^{p_{n}},$

An essential node occurs whenever a step $\alpha _{n}$ immediately precedes a step $\alpha _{l}$ where $u>t,$.

In the corresponding permutation there is a contact

$\alpha _{n}\alpha _{l},\quad u>t,$

which may be called a major contact.

Hence a line of route with $s$ essential nodes is represented by a permutation with $s$ major contacts. We have thus the theorem:—

"In the reticulation of the multipartite number $p_{1}p_{2}\,.\,.\,.\,p_{n}$ the number of lines of route which possess exactly $s$ essential nodes is equal to the number of permutations of the letters in the product

$\alpha _{1}^{p_{1}}\alpha _{2}^{p_{2}}\,.\,.\,.\,\alpha _{n}^{p_{n}},$

which possess exactly $s$ major contacts."

" Calling a contact $\alpha _{n}\alpha _{l},$ a major contact when $u>t,$ the number of permutations of the letters in the product

$\alpha _{1}^{p_{1}}\alpha _{2}^{p_{2}}\,.\,.\,.\,\alpha _{n}^{p_{n}},$