ha]_s

has the expression

1
1/2 . -----------------------------------------------------------------------------------------------------------------,
1 - 2([Sigma]t1[a]1 - [Sigma]t1t2[a]1[a]2 + [Sigma]t1t2[a]1[a]2[a]3 - ... + (-)^(s+1) t1t2...t_s[a]1[a]2...[a]_s)

and therefore the coefficient of [alpha]1^p1 [alpha]2^p2...[alpha]s^ps
in the latter fraction, when t1, t2, &c., are put equal to unity, is
equal to the coefficient of the same term in the product

1/2 (2[a]1 + [a]2 + ... + [a]s)^p1 (2[a]1 + 2[a]2 + ... +[a]s)^p2 ... (2[a]1 + 2[a]2 + ... + 2[a]s)^ps.

This result gives a direct connexion between the number of compositions
and the permutations of the letters in the product [alpha]1^p1
[alpha]2^p2...[alpha]s^ps. Selecting any permutation, suppose that the
letter a_r occurs q_r times in the last p_r + p_(r+1) + ... + p_s places
of the permutation; the coefficient in question may be represented by
1/2[Sigma] 2^(q1+q2+...+qs), the summation being for every permutation,
and since q1 = p1 this may be written

2p1^(-1)[Sigma] 2^(q2+q3+...+qs).

_Ex. Gr._--For the bipartite /22, p1 = p2 = 2, and we have the following
scheme:--

[a]1 [a]1 | [a]2 [a]2 q2 = 2
[a]1 [a]2 | [a]1 [a]2 = 1
[a]1 [a]2 | [a]2 [a]1 = 1
[a]2 [a]1 | [a]1 [a]2 = 1
[a]2 [a]1 | [a]2 [a]1 = 1
[a]2 [a]2 | [a]1 [a]1 = 0

Hence F(22) = 2(2^2 + 2 + 2 + 2 + 2 + 2^0) = 26.

We may regard the fraction

1
-------------------------------------------------------------------------------------------------------------------,
1/2 . {1 - t1(2[a]1 + [a]2 + ... + [a]s)} {1 - t2(2[a]1 + 2[a]2 + ... + [a]s)} ... {1 - t_s(2[a]1 + 2[a]2 + ... + 2[a]s)}

as a redundant generating function, the enumeration of the compositions
being given by the coefficient of

(t1[alpha]1)^p1 (t2[alpha]2)^p2 ... (t_s[alpha]_s )^ps.

The transformation of the pure generating function into a factorized
redundant form supplies the key to the solution of a large number of
questions in the theory of ordinary permutations, as will be seen later.

The theory of permutations.

[The transformation of the last section involves a comprehensive theory
of Permutations, which it is convenient to discuss shortly here.

If X1, X2, X3, ... Xn be linear functions given by the matricular