Bài tập 11, § 5

Cho E là một tập hợp có $n$ phần tử và cho S là một tập hợp các dấu sao cho S là hợp rời nhau của E và một tập hợp gồm một phần tử duy nhất $f$. Giả sử rằng $f$ có trọng số 2 và mỗi phần tử của E có trọng số 0 (Chương I, Phụ lục, Bài tập 3).

(a) Cho M là tập hợp các từ có nghĩa trong $L_0(S)$ chứa mỗi phần tử của E đúng một lần. Chứng minh rằng nếu $u_n$ là số phần tử của M, thì $u_{n+1} = (4n - 2)u_n$, và suy ra rằng

(Đây là số các tích của $n$ số hạng khác nhau đối với một luật hợp thành không kết hợp.)

(b) Cho $x_i$ là phần tử thứ $i$ trong các phần tử của E xuất hiện trong một từ của M. Chứng minh rằng số $v_n$ các từ của M, mà dãy $(x_i)$ được cho trước, bằng $\binom{2n-2}{n-1}/n$ và thỏa mãn quan hệ