91Ó°ÊÓ

Let \(A=\\{1,2,3,4,5\\}\). How many injective functions \(f: A \rightarrow A\) have the property that for each \(x \in A, f(x) \neq x ?\)

Establish the identity below using a combinatorial proof. $$ \left(\begin{array}{l} 2 \\ 2 \end{array}\right)\left(\begin{array}{l} n \\ 2 \end{array}\right)+\left(\begin{array}{l} 3 \\ 2 \end{array}\right)\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+\left(\begin{array}{l} 4 \\ 2 \end{array}\right)\left(\begin{array}{c} n-2 \\ 2 \end{array}\right)+\cdots+\left(\begin{array}{l} n \\ 2 \end{array}\right)\left(\begin{array}{l} 2 \\ 2 \end{array}\right)=\left(\begin{array}{c} n+3 \\ 5 \end{array}\right) $$

Consider functions \(f:\\{1,2,3,4\\} \rightarrow\\{1,2,3,4,5,6\\}\) (a) How many functions are there total? (b) How many functions are injective? (c) How many of the injective functions are increasing? To be increasing means that if \(a

Explain why the coefficient of \(x^{5} y^{3}\) the same as the coefficient of \(x^{3} y^{5}\) in the expansion of \((x+y)^{8} ?\)

Let \(d_{n}\) be the number of derangements of \(n\) objects. For example, using the techniques of this section, we find $$ d_{3}=3 !-\left(\left(\begin{array}{l} 3 \\ 1 \end{array}\right) 2 !-\left(\begin{array}{l} 3 \\ 2 \end{array}\right) 1 !+\left(\begin{array}{l} 3 \\ 3 \end{array}\right) 0 !\right) $$ We can use the formula for \(\left(\begin{array}{l}n \\ k\end{array}\right)\) to write this all in terms of factorials. After simplifying, for \(d_{3}\) we would get $$ d_{3}=3 !\left(1-\frac{1}{1}+\frac{1}{2}-\frac{1}{6}\right) $$ Generalize this to find a nicer formula for \(d_{n} .\) Bonus: For large \(n\), approximately what fraction of all permutations are derangements? Use your knowledge of Taylor series from calculus.

We have seen that the formula for \(P(n, k)\) is \(\frac{n !}{(n-k) !}\). Your task here is to explain \(w h y\) this is the right formula. (a) Suppose you have 12 chips, each a different color. How many different stacks of 5 chips can you make? Explain your answer and why it is the same as using the formula for \(P(12,5)\). (b) Using the scenario of the 12 chips again, what does \(12 !\) count? What does \(7 !\) count? Explain. (c) Explain why it makes sense to divide \(12 !\) by \(7 !\) when computing \(P(12,5)\) (in terms of the chips). (d) Does your explanation work for numbers other than 12 and 5 ? Explain the formula \(P(n, k)=\frac{n !}{(n-k) !}\) using the variables \(n\) and \(k\).

The number 735000 factors as \(2^{3} \cdot 3 \cdot 5^{4} \cdot 7^{2}\). How many divisors does it have? Explain your answer using the multiplicative principle.

Explain using lattice paths why \(\sum_{k=0}^{n}\left(\begin{array}{c}n \\\ k\end{array}\right)=2^{n}\)

How many functions map \\{1,2,3,4,5,6\\} onto \(\\{a, b, c, d\\}\) (i.e., how many surjections are there)?