平行四边形网格中的路径计数
如图,在 的平行四边形中, 为一对角线的两个顶点。动点从 出发, 沿图中箭头方向(向右或往上)移动,每次移动一步(一步是图中最小平行四边形的两条邻边之一, 或是最小平行四边形的一条对角线),到达最小平行四边形的一个顶点。则动点从 移动到 有种不同的移动方法。
题图已按步型重绘,仅作示意;未核对原图。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
把两条邻边方向视为横、纵方向,对角线一步同时增加两个坐标。
按对角线步数分类即可。
若使用 次对角线步,其中 ,则还需沿两条邻边方向各走 步。 总步数为 ,其排列数为
故移动方法总数为中央 Delannoy 数
当 时,显然有“先走两条邻边”的两种方法和“直接走对角线”的一种方法,共 种; 公式也给出 。
含水平、竖直和对角步的单调网格路径应按对角步数分类;每一步的净位移必须先列方程,再排列步型。
固定对角步数s后,两侧方向各需k−s步,任意排列三类步都合法,逐s求和即可。
已记下,谢谢!