01204211/homework5 counting 2

This is part of 01204211-58

Due: 19 Oct 2015

H.1

H.2 How many anagrams can you make from the word INNOVATION?

H.3 How many sorted lists of integer of length $k$ consisting only integers from $1$ to $n$ are there? (For example, when $k=2$ and $n=3$, there are 6 of them (i.e.: 1,1; 2,2; 3,3; 1,2; 1,3; and 2,3)).

H.4 (LPV-3.4.1) In how many ways can you distribute all $n$ pennies to $k$ children if each child is supposed to get at least 2?

H.5 (LPV-3.6.3) Prove the following identity:

${\binom {n}{0}}{\binom {m}{k}}+{\binom {n}{1}}{\binom {m}{k-1}}+\cdots +{\binom {n}{k-1}}{\binom {m}{1}}+{\binom {n}{k}}{\binom {m}{0}}={\binom {n+m}{k}}.$

H.6 (LPV-3.8.8) Prove the following identity

$\sum _{k=0}^{n}{\binom {n}{k}}{\binom {k}{m}}={\binom {n}{m}}2^{n-m}.$

H.7 In a village, there are $n$ houses built along a single road. They plan to plant gardens in front of the houses; therefore they have to choose a set of houses to host the gardens. Since they do not want to plant too many gardens, they do not want to have two gardens on consecutive houses. In how many ways can they choose a set of houses such that no two consecutive houses are in the set? (It is possible that, in the end, they do not plant any garden at all.)

For example, if we have 3 houses these are the 5 ways to choose houses. (* is chosen; o is not) The first example does not choose any houses.

1 2 3
-----
o o o
* o o
* o *
o * o
o o *

H.8