C, 78 52 39 34 33 bytes
Even more C magic (thanks xsot):
c(n){return!n?:(4+6./~n)*c(n-1);}
This time by expanding the recurrence below (thanks xnor and Thomas Kwa):
$$ \begin{equation} \begin{split} C_0 & = 1 \\ C_n & = \frac{2 (2n - 1)}{n + 1} C_{n - 1} \\ & = \frac{2 (2n+2-3)}{n+1} C_{n - 1} \\ & = 2 \left(2\frac{n+1}{n+1} - \frac{3}{n+1}\right) C_{n - 1} \\ & = \left(4 - \frac{6}{n+1}\right) C_{n - 1} \end{split} \end{equation} $$
c(n){return n?(4+6./~n)*c(n-1):1;}
-(n+1)
is replaced by ~n
, which is equivalent in two's complement and saves 4 bytes.
Again as a function, but this time exploiting the following recurrence:
$$ \begin{equation} \begin{split} C_0 & = 1 \\ C_n & = \frac{2 (2n - 1)}{n + 1} \cdot C_{n - 1} \end{split} \end{equation} $$
c(n){return n?2.*(2*n++-1)/n*c(n-2):1;}
c(n)
enters an infinite recursion for negative n
, although it's not relevant for this challenge.
Since calling a function seems an acceptable alternative to console I/O:
c(n){double c=1,k=2;while(k<=n)c*=1+n/k++;return c;}
c(n)
takes an int
and returns an int
.
Original entry:
main(n){scanf("%d",&n);double c=1,k=2;while(k<=n)c*=1+n/k++;printf("%.0f",c);}
Instead of directly calculating the definition, the formula is rewritten as:
$$ \begin{equation} \begin{split} \frac{1}{n + 1} {2n \choose n} &= \frac{(2n)!}{(n!)^2 \cdot (n + 1)} \\ & = \frac{2n \cdot \ldots \cdot (n + 1)}{n! \cdot (n + 1)} \\ & = \frac{1}{n + 1} \cdot \frac{\prod_{k = 1}^n (n + k)}{\prod_{k = 1}^n k} \\ & = \frac{1}{n + 1} \cdot \prod_{k = 1}^n \frac{n + k}{k} \\ & = \frac{1}{n + 1} \cdot \prod_{k = 1}^n \left(1 + \frac{n}{k}\right) \\ & = \frac{1}{n + 1} (n + 1) \prod_{k = 2}^n \left(1 + \frac{n}{k}\right) \\ & = \prod_{k = 2}^n \left(1 + \frac{n}{k}\right) \end{split} \end{equation} $$
The formula assumes n >= 2
, but the code accounts for n = 0
and n = 1
too.
In the C mess above, n
and k
have the same role as in the formula, while c
accumulates the product. All calculations are performed in floating point using double
, which is almost always a bad idea, but in this case the results are correct up to n = 19n = 19
at least, so it's ok.
float
would have saved 1 byte, unfortunately it's not precise enough.