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

留学警示（商务部公告2026年第12号）

根据中华人民共和国商务部公告2026年第12号，东京科学大学（東京科学大学/Institute of Science Tokyo）已被列入关注名单。请中国留学申请者慎重考虑相关风险，在做出留学决定前充分了解相关政策及其可能带来的影响。

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