Amidakuji

Amidakuji (Japanese: 阿弥陀籤) is a method for producing a random permutation of a set of objects.

In the beginning, a number of parallel vertical lines are drawn, one for each object. Then a specified number of horizontal rungs are added, each lower than any previous rungs. Each rung is drawn as a line segment spanning a randomly select pair of adjacent vertical lines.

For example, the following diagram depicts an Amidakuji with three objects ($A$, $B$, $C$) and six rungs:

The coloured lines in the diagram illustrate how to form the permutation. For each object, starting from the top of its vertical line, trace downwards but follow any rung encountered along the way, and record which vertical we end up on. In this example, the resulting permutation happens to be the identity: $A\mapsto A$, $B\mapsto B$, $C\mapsto C$.

Let $a(m, n)$ be the number of different three-object Amidakujis that have $m$ rungs between $A$ and $B$, and $n$ rungs between $B$ and $C$, and whose outcome is the identity permutation. For example, $a(3, 3) = 2$, because the Amidakuji shown above and its mirror image are the only ones with the required property.

You are also given that $a(123, 321) \equiv 172633303 \pmod{1234567891}$.

Find $a(123456789, 987654321)$. Give your answer modulo $1234567891$.

This problem involves calculating the number of different three-object Amidakujis that satisfy certain conditions and produce the identity permutation.

To solve this problem, we can use dynamic programming.

Specifically, we can use a two-dimensional array to keep track of the number of valid configurations for each pair of rung counts.

Here’s the Python code implementation to solve the problem:

def calculate_amidakujis(a, b, MOD):
dp = [[0] * (b + 1) for _ in range(a + 1)]
dp[0][0] = 1

for i in range(a + 1):
for j in range(b + 1):
if i > 0:
dp[i][j] += dp[i – 1][j] * j
dp[i][j] %= MOD
if j > 0:
dp[i][j] += dp[i][j – 1] * i
dp[i][j] %= MOD

return dp[a][b]

def main():
a = 123456789
b = 987654321
MOD = 1234567891

result = calculate_amidakujis(a, b, MOD)
print(result)

if __name__ == “__main__”:
main()

This code calculates the number of valid configurations for the given pair of rung counts using dynamic programming.

More Answers: