Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Here are the /Solutions.

1. Increasing subsequences

Consider a random permutation of the numbers 1..2n. Suppose we take the subsequence consisting of the 1st, 3rd, 5th, etc. numbers in this sequence.

What is the probability that this subsequence is increasing?
What is the probability that this subsequence and the subsequence consisting of the 2nd, 4th, 6th, etc. cards are both increasing?

2. Inversions

An inversion in a permutation p of the numbers 1..n is a pair of positions i < j with p_i > p_j. For example, 123 has no inversions, 312 has two inversions (31 and 32) and 321 has three inversions (32, 31, and 21).

Compute the expected number of inversions X in a random permutation on 1..n. (Hint: consider a single pair of positions and then use linearity of expectations.)
Compute the variance of X.

3. A deck of cards

A dealer constructs a deck of cards by choosing a number X between 0 and n uniformly at random (i.e., so that each possible value occurs with probability 1/(n+1)), and then putting in X red cards and n-X black cards. The dealer then shuffles the deck, obtaining a uniform random permutation of the n cards.

Suppose that the dealer turns over the first card and it's black. Conditioned on this event:

What is the probability that none of the cards in the deck are red?
What is the probability that the next card in the deck is red? (Assume in this case that n >= 2.)
What is the expected value of X, the number of red cards in the deck?

It may be useful for some of these cases to recall the formulas

$\begin{eqnarray*} \sum_{i=0}^{n} i &=& \frac{n(n+1)}{2},\\ \sum_{i=0}^{n} i^2 &=& \frac{n(n+1)(2n+1)}{6}. \end{eqnarray*}$

4. Some related relations

Consider the binary relation R on sets given by R = { (A,B) : there exists an injection f:A->B }.¹

Show that R is reflexive.
Show that R is transitive.
Prove or disprove: R is a partial order.
Show that R is a refinement of the usual subset relation, in the sense that if A⊆B, then A R B holds.

Technically, if R ranges over all sets, it's too big to be a set itself. If this worries you, assume that R is restricted to some very large universe of sets. (1)