
%\noindent\textbf{Catalan Numbers}
\section{Catalan Numbers}

\begin{displaymath}
  C(n) = \frac{1}{n + 1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!} \ \ \ n \geq 0
\end{displaymath}

\noindent First few $C(n)$ are 1 1 2 5 14 42 132 ...

\noindent $C(n)$ gives a) number of matching () of length $n$,
b) number of ordered binary trees with $n + 1$ leaves, 
c) number of ways a convex polygon with $n + 2$ sides can be cut
into triangles, 
d) number of ways to tile a stairstep of height $n$ with $n$ rectangles.


Number of lattice paths from $(0,0)$ to $(a,b)$ with only east, north moves is
  $${a+b} \choose a$$

Number of lattice paths from $(0,0)$ to $(b,a)$ with only
    east, north, northeast moves:
  $$D(a,b) = D(a-1,b) + D(a,b-1) + D(a-1,b-1)$$
  $$D(0,0) = 1$$

Dyck paths (staircase walks below diagonal y=x) of order n is $C(n)$

Number of nonattacking kings on a nxn chessboard:
    $$K(n) = 1/4 * (n + (n\mod 2))^2$$

Number of bishops on a chessboard: min $n$, max $2n-2$.
  Number of rot + refl distinct:
  $$2^{n-3}+2^{ \lfloor (n-1)/2 \rfloor -1 }$$

\textbf{Pick's theorem}: A is area of lattice polygon,
                B is number of lattice points on polygon
                I is number of points in polygon interior
  then $A = I + B/2 - 1$

Lattice points on line from origin to $(a,b)$ is
  gcd(a,b) - 1

Fraction of lattice pts visible from $(0,0)$ is $6/(\pi^2)$


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ref-doc"
%%% End: 
