<pre>
Let y(n) = expected number of EMPTY seats for row of n seats
f = (n - y(n)) / n


y(1) = 1
y(2) = 0
y(n) <code> 2 * SUM(i</code>1 to n-2) ~[[y(i)]] / (n-1)


To see this recurrence, consider the first person to sit down.
The expected total number of empty seats will the sum of the
expected number of empty seats to his left and to his right --
i.e. the sum of two previous y() values. The first person can
sit in any of (n-1) equiprobable locations.  Hence, y(n) is the
sum of left and right portions over all n-1 locations divided
by n-1.


To solve this, we are going to have to get rid of the summation.


By our formula,
y(n-1) <code> 2 * SUM(i</code>1 to n-3) ~[[y(i)]] / (n-2)
(I) (n-2)'''y(n-1) <code> 2 ''' SUM(i</code>1 to n-3) ~[[y(i)]]


We can also get this same summation from our formula for
y(n) by moving the i=(n-2) term out of the summation.


y(n) <code> 2 * {SUM(i</code>1 to n-3) ~[[y(i)]] + y(n-2)} / (n-1)
(II) y(n) <code> {2 ''' SUM(i</code>1 to n-3) ~[[y(i)]] + 2'''y(n-2)} / (n-1)


Now substitute for the summation using (I),


(''') y(n) = {(n-2)'''y(n-1) + 2*y(n-2)} / (n-1)


(n-1)'''y(n) - (n-2)'''y(n-1) - 2*y(n-2) = 0


A note on terminology:
This recurrence would be usually be called linear with nonconstant
coefficents.  Linearity in difference equations usually refers
to linearity in the y(n), so that given solutions y1(n) and y2(n),
(a y1(n) + b y2(n)) is also a solution.)

One way of handling recurrences of this type (having coefficients
which are polynomial in n) is to deal with a generating function,
which is the function Y(z) of the formal variable z which has
Taylor coefficients y(n): i.e.,
<pre>
  Y(z) <code> sum_{n</code>0}^infty y(n) z^n
</pre>
(here we set y(0)=0 for convenience).  Now coefficients which are
polynomials in n may be replaced by derivatives of the Y(z),
giving a differential equation for Y (of order the maximal degree
of the polynomials in n).  Here, for example (where D = d/dz)
<pre>
  0 <code> sum_{n</code>0}^infty z^n~[[(n+1)'''y(n+2) - n'''y(n+1) - 2*y(n)]]
    = sum_n ~[[(n+1)'''z^n'''y(n+2) - n'''z^n'''y(n+1) - 2'''z^n'''y(n)]]
    = sum_n ~[[D~[y(n+2)'''z^{n+1}]] - z'''D~[[y(n+1)'''z^n]] - 2'''z^n*y(n)]
    = sum_n ~[[D~[(1/z)'''y(n+2)'''z^{n+2}]] - z'''D~[[(1/z)'''y(n+1)*z^{n+1}]]
             - 2'''z^n'''y(n)]
      (here I'm going to be cavalier about the summation limits;
       if you check it, it actually does work out nicely)
    = ~[[D (1/z) - z D (1/z) - 2]]'''sum_n z^n'''y(n)
    = (1-z) D (Y(z)/z) - 2*Y(z)
</pre>
giving the first-order differential equation
<pre>
  Y'(z) / Y(z) = (2'''z^2 - z + 1) / (z'''(1-z))
</pre>
for the generating function.


This is mildly ugly but can be solved.  Then Taylor expansion
gives the coefficients y(n).  In this case, y(n) can be computed
exactly with a sum over n terms; the terms are well approximated,
for large n, by y(n) ~ (n+2) exp(-2), for a filling factor (for
large n) of 1 - exp(-2).
</pre>
