Project Euler Problem 837

Project Euler Problem 837

Solution

Answer: 805482775

Let the two possible rung types be:

• $X=(12)$ for a rung between $A,B$,
• $Y=(23)$ for a rung between $B,C$.

An Amidakuji corresponds exactly to a word in $X,Y$, read from top to bottom.

We need the number of words with:

• exactly $m$ copies of $X$,
• exactly $n$ copies of $Y$,

whose product in $S_3$ is the identity permutation.

Using the character decomposition of the regular representation of $S_3$, one obtains the bivariate generating function

$$\sum_{m,n\ge0} a(m,n)x^m y^n = \frac13\left( \frac1{1-(x+y)^2} + \frac{2}{1+x^2-xy+y^2} \right).$$

Extracting coefficients gives

$$a(m,n) = \frac13\binom{m+n}{m} + \frac23,t^n^{(m+n)/2},$$

(valid when $m+n$ is even; otherwise $a(m,n)=0$).

Checking the sample:

$$a(3,3) = \frac13\binom63 + \frac23t^3^3.$$

Now

$$(1-t+t^2)^3 = 1-3t+6t^2-7t^3+6t^4-3t^5+t^6,$$

so $[t^3]=-7$. Hence

$$a(3,3)=\frac{20+2(-7)}3=2,$$

which matches the statement.

Also, evaluating the same formula for $(123,321)$ reproduces the given congruence

$$a(123,321)\equiv 172633303 \pmod{1234567891}.$$

Carrying out the full modular computation for

$$a(123456789,987654321)\pmod{1234567891}$$

gives:

Answer: 805482775