There are $n$ children queuing in a line. You have $m$ candies and will begin handing out 1 or 2 candies to each child, starting from the first child in the line. You hand out the candies until reaching the end of the line or until there are no candies left. Answer the following questions. Note that $n$ and $m$ are positive integers.
I. Show the number of distribution patterns of candies if $n = m = 4$.
II. Show the number of distribution patterns of candies if $m \geq 2 n$.
III. Define $X _ { m }$ as the number of distribution patterns of candies if $n \geq m$. Show the recurrence formula satisfied by $X _ { m }$.
IV. Obtain $X _ { m }$ using the recurrence formula in Question III.
V. Consider the situation where the number of children is larger than the number of candies. Define $P ( m )$ as the ratio of the number of distribution patterns (where the distribution finishes by giving 2 candies) to the total number of distribution patterns. $P ( m )$ converges as $m$ increases. Compute the convergence value.
VI. Consider the situation where $m \geq 2 n$. The following rules are added to the way of handing out the candies: For the first child in the line, the probability of receiving 1 candy is $1 / 2$ and the probability of receiving 2 candies is $1 / 2$. If a child receives 1 candy, the probability of the next child receiving 1 candy is $1 / 2$ and the probability of receiving 2 candies is $1 / 2$. If a child receives 2 candies, the probability of the next child receiving 1 candy is $3 / 4$ and the probability of receiving 2 candies is $1 / 4$. Compute the probability that the $n$-th child in the line receives 2 candies.