Project Euler Problem 892
Consider a circle where 2n distinct points have been marked on its circumference.
Solution
Answer: 469137427
Let the regions formed by a cutting be coloured in checkerboard fashion, with the outer region black.
A standard Catalan bijection identifies each noncrossing perfect matching on $2n$ points with a rooted plane tree with $n$ edges (equivalently $n+1$ vertices):
- regions $\leftrightarrow$ vertices,
- shared chord boundary $\leftrightarrow$ edges,
- outer region $\leftrightarrow$ root.
Under this bijection, black/white colouring corresponds exactly to parity of depth in the rooted tree. Therefore
$$d(C)=\left|#(\text{even depth vertices})-#(\text{odd depth vertices})\right|.$$
A classical Narayana-number refinement gives:
$$#{C : d(C)=|n+1-2k|}=N(n,k),$$
where
$$N(n,k)=\frac1n\binom{n}{k}\binom{n}{k-1}.$$
Hence
$$D(n)=\sum_{k=1}^n |n+1-2k|,N(n,k).$$
This sum simplifies to closed forms:
- for even $n=2m$,
$$D(2m)=\frac12\binom{2m}{m}^2;$$
- for odd $n=2m-1$,
$$D(2m-1)=\frac{2(m-1)}{m}\binom{2m-2}{m-1}^2.$$
Check against the given value:
$$D(100)=\frac12\binom{100}{50}^2 \equiv 1172122931 \pmod{1234567891},$$
which matches the problem statement.
Now compute
$$\sum_{n=1}^{10^7} D(n) \pmod{1234567891}.$$
Using the recurrence
$$a_m=\binom{2m}{m}^2, \qquad a_m=a_{m-1}\cdot \frac{4(2m-1)^2}{m^2},$$
and iterating modulo $1234567891$ up to $m=5\cdot10^6$, the resulting sum is
$$469137427.$$
Answer: 469137427