I have encountered a derangement problem described as follow:
n people will take n seats indexed as 1,2,3...,n; they choose seat one by one starting from person 1. For first n-1 people, they are not allowed to take the seat with same number as him and choose unoccupied seat randomly, eg. person 1 is not allowed to sit in seat 1, he can choose other seats randomly from 2 to n. Then person 2 choose under same rule: person 2 will choose unoccupied ones other than seat 2. What is the probability that the last person n take seat number n?
For example:
p(n=2) = 0, there is no way person 2 can sit in seat 2. Person 1 will have no choice but to choose seat 2.
for n=3, if you take an one-by-one view, P(n=3) = 1/2*1/2=1/4
p(n=4) = $1/3*1/3*1/2 + 1/3*1/2*1/2 = 5/36$ following same logic.
The series is found here! http://oeis.org/A102262 p(2) to p(10): 0, 1/4, 5/36, 19/144, 203/1800, 4343/43200, 63853/705600
OEIS is really amazing!
@Troposphere gives a inductive solution. But the analytic approximation need further explanation.
$p(n) = 1/(n+log(n)+Euler Const)$ when n is large. Credit to OEIS.
Not a full answer down to a closed formula (which might not exist), but an algorithm for calculating the probability faster than by considering all cases individually:
It will make a recursive analysis somewhat simpler if we renumber the people such that person $n$ makes his choice first, and the question is whether person $1$ will be forced to sit in chair $1$.
Now, we make this observation:
So we can reduce the state of the game to knowing:
Let the probability when we start in this state be $P(k,m)$. Your original $P(n)$ is now called $P(n,0)$. At the end of the gave we have $P(1,0)=1$ and $P(1,1)=0$. (In general $P(k,k)=0$, because the last chair is already occupied).
Now consider $P(k,m)$ for $k>1$ and $0\le m\le k$. Since all distributions of the $m$ occupied chairs are equally likely, the probability of chair $k$ being occupied is $m/k$.
Thus with probability $m/k$, person $k$ finds he can choose freely among the $k$ free chairs in the room. The probability that he chooses one in the interval $[1,k-1]$ is $(k-m)/k$. The next $m$ is either $m$ or $m-1$ -- the occupied chair at position $k$ drops out of the count, but the chair person $k$ sits down in may or may not be added to it.
On the other hand, with probability $1-m/k=(k-m)/k$ chair $k$ is free, and person $k$ has only $k-1$ chairs to choose uniformly between. The probability that he chooses one in the interval $[1,k-1]$ is $(k-m-1)/(k-1)$. The next $m$ is either $m+1$ or $m$.
Summing up this analysis, we have $$ P(k,m) = \tfrac{m}{k}\Bigl[ \tfrac{k-m}{k} P(k-1,m) + \tfrac{m}{k} P(k-1,m-1) \Bigr] + \tfrac{k-m}{k}\Bigl[ \tfrac{k-m-1}{k-1} P(k-1,m+1) + \tfrac{m}{k-1} P(k-1,m) \Bigr]$$ or, multiplying out and collecting the coefficients of $P(k-1,m)$: $$ P(k,m) = \tfrac{(k-m)(k-m-1)}{k(k-1)} P(k-1,m+1) + \tfrac{m(k-m)(2k-1)}{k^2(k-1)} P(k-1,m) + \tfrac{m^2}{k^2} P(k-1,m-1) $$ which one can use to build a table of the $P(k,m)$s in $O(k^2)$ operations and finally read out $P(n)=P(n,0)$.
This recurrence reproduces your answers $P(3)=1/4$, $P(4)=5/36$: $$\begin{array}{l} P(1,0)=1 & P(1,1)=0 \\ P(2,0)=0 & P(2,1)=1/4 & P(2,2)=0 \\ P(3,0)=1/4 & P(3,1)=5/36 & P(3,2) = 1/9 & P(3,3) = 0 \\ P(4,0)=5/36 & & & P(4,3)=1/16 & P(4,4) = 0 \end{array}$$
The value of $P(n)=P(n,0)$ is the probability that persons $n, n-1, \ldots, 2$ all avoid sitting in chair number $1$. For person $k$, this probability is between $\frac{k-2}{k-1}$ and $\frac{k-1}{k}$ assuming chair $1$ is still unoccupied when they choose. If we use this bound for $k\ge 4$ and handle persons $3$ and $2$ by noting that $\frac19\le P(3,m)\le\frac14$ for $0\le m<3$, we can bound $P(n)$ by telescoping products, to get at least the asymptotic behavior: $$ \frac2{9(n-1)} \le P(n) \le \frac3{4n} \quad\text{for }n\ge 3$$