Some formulas about combinatorics

\begin{equation} C_{n+1}^{k+1} = C_n^k + C_n^{k+1} \end{equation} \begin{equation} C_k^k + C_{k+1}^k + \cdots + C_n^k = C_{n+1}^{k+1} \end{equation}

clrs Exercise 5.3-3

Suppose that instead of swapping element $A[i]$ with a random element from the subarray $A[i \ldots n]$, we swapped it with a random element from anywhere in the array:

PERMUTE-WITH-ALL(A)
n = A.length
for i = 1 to n
    swap A[i] with A[RANDOM(1,n)]

Does this code produce a uniform random permutation? Why or why not?

Of course, this is a popular problem and there are tons of posts and papers written on it. Here's one from Coding Horror

clrs Exercise 5.2-2

Ref http://clrs.skanev.com/05/02/02.html
5.2-2
In HIRE-ASSISTANT, assuming that the candidates are presented in a random order,
what is the probability that you hire exactly twice?
You hire twice when you first hire is the candidate with rank $i$ and all the candidates with rank $k > i$ come after the candidate with rank $n$. There are $n - i$ better suited candidates and the probability of the best one coming first is $1/(n-i)$ (we can ignore the other candidates and they don't affect the probability). Thus, the probability for hiring twice if your first candidate has rank $i$ is:
$$ \Pr\{T_i\} = \frac{1}{n}\frac{1}{n-i} $$
The first part reflects the probability of picking that particular candidate out of $n$.
The probability to hire twice is:
$$ \Pr\{T\} = \sum_{i=1}^{n-1}\Pr\{T_i\} = \sum_{i=1}^{n-1}\frac{1}{n}\frac{1}{n-i} = \frac{1}{n} \sum_{i=1}^{n-1}\frac{1}{i} = \frac{1}{n} \Big(\lg(n-1) + \O(1)\Big) $$