東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問C

Author

祭音Myyura

Description

以下の図に示すような の格子を考える．ただし とする．

ここで，点 から点 まで，条件 1 を満たすように隣接する点の間を移動する経路全体の集合を とする．

• 条件 1: 経路上の全ての点に関して，その右または上の隣接点へのみ移動可能．

有限集合 A に対して |A| は A の濃度 (要素数) を表すものとする．

(1) を求めよ．

に含まれる経路で，条件 2 を満たす経路全体の集合を とする．

• 条件 2: ある に対して，経路上に点 が存在する．すなわち，経路は上図に示した • 印の点を少なくとも 1 つ経由する．

集合 を と に分割する．

• に含まれる経路で，点 を通る経路全体の集合．
• に含まれる経路で，点 を通る経路全体の集合．

(2) を求めよ．

(3) を求めよ．

(4) | を求めよ．ただし ． また として を求めよ．

Kai

(1)

Total number of moves in which we have to move up to reach the last row

Total number of moves in which we have to move right to reach the last column

Total moves

Now think of moves as a string of ‘R’ and ‘U’ characters where ‘R’ at any ith index will tell us to move ‘Right’ and ‘U’ will tell us to move ‘Up’. Then equals to how many unique strings (moves) we can make where in total there should be characters and there should be ‘U’ character and ‘R’ character. Note that choosing positions of ‘R’ characters results in the automatic choosing of ‘U’ character positions

Therefore,

(2)

Note that all paths go through the point will cross the line , hence

(3)

We take a path from to which touch (cross) the line , and let be the point where it first touches this line.

If we reflect the portion of the path from to around the line , then we get a path from to . Conversely, any path from to must cross the line . If we let be the point where the path first touches this line and reflect the portion of the path from to about this line, then we get a path from to .

Since this gives a bijection between the two types of paths, and since the number of paths from to is given by , we have

(4)

By (2) and (3) we have

Then