91Ó°ÊÓ

Show that the total number of inversions in all of the permutations of \(\\{1, \ldots, n\\}\) is \(n ! n(n-1) / 4 .\) Hint: If \(p_{1}, \ldots, p_{n}\) is a permutation of \(\\{1, \ldots, n\\},\) let \(p^{\mathrm{R}}=p_{n}, \ldots, p_{1}\) denote the reverse of \(p\). Consider the total number of permutations in \(p\) and \(p^{\mathrm{R}}\).

Show that the average number of inversions in permutations of \(\\{1, \ldots, n\\}\) is \(n(n-1) / 4\). Assume that all permutations are equally likely.

Solve the recurrence relation $$a_{n}=\sqrt{\frac{a_{n-2}}{a_{n-1}}}$$ with initial conditions \(a_{0}=8, a_{1}=1 /(2 \sqrt{2})\) by taking the logarithm of both sides and making the substitution \(b_{n}=\lg a_{n}\)

Solve the recurrence relation for the initial conditions given. \(a_{n}=-2 n a_{n-1}+3 n(n-1) a_{n-2} ; \quad a_{0}=1, \quad a_{1}=2\)

Exercises 40-46 refer to Ackermann's function A \((m, n)\). Compute \(A(2,2)\) and \(A(2,3)\)

Solve the recurrence relation for the initial conditions given. \(A(n, m)=1+A(n-1, m-1)+A(n-1, m), n-1 \geq m \geq 1,\) \(n \geq 2 ; A(n, 0)=A(n, n)=1, n \geq 0\)

If \(P_{n}\) denotes the number of permutations of \(n\) distinct objects, find a recurrence relation and an initial condition for the sequence \(P_{1}, P_{2}, \ldots\)

Let \(S(n, k)\) denote the number of functions from \(\\{1, \ldots, n\\}\) onto \(\\{1, \ldots, k\\}\). Show that \(S(n, k)\) satisfies the recurrence relation $$ S(n, k)=k^{n}-\sum_{i=1}^{k-1} C(k, i) S(n, i) $$

The Lucas sequence \(L_{1}, L_{2}, \ldots\) (named after Édouard Lucas, the inventor of the Tower of Hanoi puzzle) is defined by the recurrence relation $$ L_{n}=L_{n-1}+L_{n-2} \quad n \geq 3 $$ and the initial conditions \(L_{1}=1 . L_{2}=3\) (a) Find the values of \(L_{3}, L_{4},\) and \(L_{5}\). (b) Show that $$ L_{n+2}=f_{n+1}+f_{n+3} \quad n \geq 1 $$ where \(f_{1}, f_{2}, \ldots\) denotes the Fibonacci sequence.