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 You want to tile a walk way of length $n$. The width of the walk way is 1 unit. You have tiles of size 1x1, 2x1 and 3x1. In how many ways can you do that?

Let $W_{n}$ be the number of ways you can tile the walk way of length $n$ with these tiles.

(a) Specify the recurrence for $W_{n}$.

(b) Find the explicit form of $W_{n}$. (The details for the Fibonacci sequence will be available on the slide soon.)