91Ó°ÊÓ

Prove each. $$C_{n}=\frac{2(2 n-1)}{n+1} C_{n-1}, \quad n \geq 1$$

Show that \((n !) !>(2 n) !,\) if \(n>3\).

The \(n\) th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i}\) \(n \geq 2 .\) (Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{5}$$

The \(n\)th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i},\) \(n \geq 2 .\) Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{5}$$

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Functions can be defined from \(A\) to \(B ?\)

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Bijections can be defined from \(A\) to \(B\) (assume \(m=n\) )?

Let \(\tau\) denote the tau function. Prove each. \(\tau(n)\) is odd if and only if \(n\) is a square.

The number of surjections that can be defined from a finite set \(A\) to a finite set \(B\) is given by \(r ! S(n, r),\) where \(|A|=n\) and \(|B|=r .\) Compute the number of possible surjections from \(A\) to \(B\) if: $$|A|=n,|B|=2$$

The number of surjections that can be defined from a finite set \(A\) to a finite set \(B\) is given by \(r ! S(n, r),\) where \(|A|=n\) and \(|B|=r .\) Compute the number of possible surjections from \(A\) to \(B\) if: $$|A|=n,|B|=3$$