Solutions for HW4, 2002/2003

4. (a) The bad property Pi, 1 <= i <= n-1:

    number i+1 goes exactly after i.

If it holds, then we as if arrange only the numbers except
for i+1, while the place of i+1 is pre-determined. 
Hence, if some k of these properties hold, then
all SUCH possibilities correspond to all the possibilities
to arrange the n-k numbers left.

There are (n-k)! such possibilities, and this is W_ij...s.
There are C(n,k) choices of such k properties, so
W[k] = C(n,k) * (n-k)!. Substituting this formula
into the Inclusion-Exclusion Rule, we obtain the answer.


(b) Let us write down the three formulas: for d_n,
for d_(n-1), and the sum obtained above.
Let us consider the three coefficients before (n-k)!,
in these formulas. The rule C(n,k)=C(n-1,k-1)+C(n-1,k)
shows that the required equality holds for each such
coefficient triple.


5. First, the event is composed from the two independent
sub-events: for the green and for the blue masks. So,
on us to compute the number of possibilities for each event,
and to square it.

This number is exactly the number of derangements
(hafarot seder), for k. Approximately, this is 0.37*k!

  (0.37*k!)*(0.37*k!)/(k!)*(k!) is approx. 0.37 * 0.37 ,
  which is less than 0.2 * 0.2 = 0.16.



10. Let s be at row i, and t in column j.
Let Aij be the matrix element at the row i and column j. 
Since s is the greatest one in row i, s>=Aij.
Since t is the least one in column j, Aij>=t.
As a consequence, s>=t.