经典组合数学题推论求证
  • 板块学术版
  • 楼主Joe2011
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/2/23 13:55
  • 上次更新2024/2/23 15:48:03
查看原帖
经典组合数学题推论求证
552404
Joe2011楼主2024/2/23 13:55

有一个经典的组合数学题: 将前 2n2n 个正整数填入 2×n2\times n 的表格,每格一个数,使得每行从左往右递增,每列从上往下递增。求不同填表方式的数目。

一种思路就是按升序顺序填入数(每一行从左往右填,上一行的数必须多于下一行的),在另一个坐标系里,将在原表上一列填数看做向右走,在下一列填数看做向上走,就有一个标数的方法了。

我们标出来的数表大概长这样:

&&&&14\\ &&&5&14\\ &&2&5&9\\ &1&2&3&4\\ 1&1&1&1&1 \end{array}$$ 设左下角1的坐标是(0,0),那么 $$f(a,b)=\begin{cases}f(a-1,b)+f(a,b-1)&a\le b\\0&a>b\end{cases}$$ 这些元素好像都可以表示为 $$f(a,b)=C_{a+b}^a-C_{a+b}^{a+1}$$ 可以大概给一个代数或组合上的解释吗?
2024/2/23 13:55
加载中...