Exercise 11, § 5

Let E be a set with $n$ elements and let S be a set of signs such that S is the disjoint union of E and a set consisting of a single element $f$. Suppose that $f$ has weight 2 and that each element of E has weight 0 (Chapter I, Appendix, Exercise 3).

(a) Let M be the set of significant words in $L_0(S)$ which contain each element of E exactly once. Show that if $u_n$ is the number of elements in M, then $u_{n+1} = (4n - 2)u_n$, and deduce that

(This is the number of products of $n$ different terms with respect to a non-associative law of composition.)

(b) Let $x_i$ be the $i$th of the elements of E which appears in a word of M. Show that the number $v_n$ of words of M, for which the sequence $(x_i)$ is given, is equal to $\binom{2n-2}{n-1}/n$ and satisfies the relation