Bourbaki

Exercise 5, § 7

Algebra, I, 160

Let XX be a set with one element. If nn is an integer ⩾1\geqslant 1, let unu_n denote the number of elements in M(X)M(X) of length nn.

(a) For every set YY, show that

Card⁡(Mn(Y))=un⋅Card⁡(Y)n. \operatorname{Card}(M_n(Y)) = u_n \cdot \operatorname{Card}(Y)^n.
(Use Exercise 3.)

(b) Establish the relation

un=∑p=1n−1upun−pfor n⩾2. u_n = \sum_{p=1}^{n-1} u_p u_{n-p} \quad \text{for } n \geqslant 2.

(c) *Let f(T)f(T) be the formal power series ∑n=1∞unTn\sum_{n=1}^{\infty} u_n T^n. Show that

f(T)=T+f(T)2. f(T) = T + f(T)^2.
Deduce the formulae
f(T)=12(1−(1−4T)1/2),un=2n−1n!1⋅3⋅5…(2n−3)for n⩾2.∗ f(T) = \frac{1}{2}(1 - (1 - 4T)^{1/2}), \qquad u_n = \frac{2^{n-1}}{n!} 1 \cdot 3 \cdot 5 \ldots (2n-3) \quad \text{for } n \geqslant 2.*
Obtain the last result using Exercise 11 of Set Theory, III, § 5.

Solution

No solution has been written yet.

Transcribed from the printed volume. Not translated.