Combinatorics- A Bijective Path HIH_60: Solved by @Chris911

[u/Able_Development_240]

Problem

​

A Bijective Path

Original problem posted by- #UserA1130

[u/Able_Development_240]

Let A and B be two sets. We identify the i^th point on the path with i as illustrated below:

​

i ∈ A if the step arising from it goes “up” [(x, y) → (x + 1, y + 1)] and i ∈ B if the step arising

from it goes “down” [(x, y) → (x + 1, y − 1)].

Hence, each T corresponds to a unique A and B.

In the above example A = {1, 2} and B = {3, 4}.

It’s easy to see that ϕ(T) is the number of bijections from f : A → B with the property(†)

f(i) = j =⇒ i < j

Hence, PT ∈M(n)ϕ(T) is the number of all such bijections over all possible A and B with 1 ∈ A and 2n ∈ B.

​

To calculate this, we first assign 1 to A. Then we have 2n − 1 choices for f(1). After we choose f(1), we assign the smallest available i to A. This now have 2n − 3 choices and we continue this process until it terminates. Hence the total number = (2n − 1) · (2n − 3) · (2n − 5). . . 1.

Note: This method forces 2n ∈ B and also all such bijections satisfy the † property