两个单形之积，分为单形，有多少对相邻的？

hbghlyj

$n\inN_+,$
$\Delta^1$是$1$维单形$0\to1$，即线段
$\Delta^n$是$n$维单形$0\to1\to\dots\to n$
则$\Delta^1\times\Delta^n$是由$\binom{n+1}{n}=n+1$个$\Delta^{n+1}$粘合得到的。
其中两个$\Delta^{n+1}$，若它们的交集是一个$n$维单形，则称它们“相邻”。
（等价于，它们有$n+1$个公共顶点。）

hbghlyj

$\Delta^1$是$0\to 1$
那麼$\Delta^1\times \Delta^1$可分为2个$\Delta^2$:
$$(0,0)\to(1,0)\to(1,1)$$
$$(0,0)\to(0,1)\to(1,1)$$
它们的交集是一个1维单形，$(0,0)\to(1,1)$，所以它们相邻。

hbghlyj

$\Delta^1$是$0\to 1$
$\Delta^2$是$0\to 1\to2$
那麼$\Delta^1\times \Delta^2$可分为3个$\Delta^3$:
$$(0,0)\to(0,1)\to(0,2)\to(1,2)$$
$$(0,0)\to(0,1)\to(1,1)\to(1,2)$$
$$(0,0)\to(1,0)\to(1,1)\to(1,2)$$
第一个和第二个是相邻的。第二个和第三个是相邻的。第一个和第三个不相邻。

hbghlyj

$\Delta^1\times\Delta^n$是由$\binom{n+1}{n}=n+1$个$\Delta^{n+1}$粘合得到的。
\begin{array}{l}
(0,0)\to(0,1)\to\dots\to(0,n-2)\to(0,n-1)\to(0,n)\to(1,n)
\\(0,0)\to(0,1)\to\dots\to(0,n-2)\to(0,n-1)\to(1,n-1)\to(1,n)
\\(0,0)\to(0,1)\to\dots\to(0,n-2)\to(1,n-2)\to(1,n-1)\to(1,n)
\\\cdots
\\(0,0)\to(1,0)\to\dots\to(1,n)
\end{array}可见，这$n+1$个$\Delta^{n+1}$中，共有$n$对是相邻的。

hbghlyj

$m,n\inN_+,$
$\Delta^m$是$m$维单形，
$\Delta^n$是$n$维单形，
则$\Delta^m\times\Delta^n$是由$\binom{m+n}{n}$个$\Delta^{m+n}$粘合得到的。
考虑其中两个$\Delta^{m+n}$，它们的交集是一个$m+n-1$维单形，则称它们“相邻”。
（等价于，它们有$m+n$个公共顶点。）
问题：这$\binom{m+n}{n}$个$\Delta^{m+n}$中，有多少对相邻的？

hbghlyj

hbghlyj 发表于 2024-10-25 17:11
这$\binom{m+n}{n}$个$\Delta^{m+n}$中，有多少对相邻的？

相邻等价于，它们有$m+n$个公共顶点，也就是只有1个顶点不同、剩下的都相同。
设这个不同顶点分别为$(i-1,j)$与$(i,j-1)$，因为$i-1\ge0,j-1\ge0$所以$i\ge1,j\ge1$.
考虑剩下的$m+n$个公共顶点：

• 在它前面的有$i+j-1$个顶点$(0,0)\to\dots\to(i-1,j-1)$
• 在它后面的有$m+n-i-j+1$个顶点$(i,j)\to\dots\to(m,n)$

因此，以$(i-1,j),(i,j-1)$这两点为不同顶点的“相邻对”的个数为$\binom{i+j-2}{i-1}\binom{m+n-i-j}{m-i}$.
对$i\in\{1,\dots,m\},j\in\{1,\dots,n\}$求和：WolframAlpha
\[\sum_{i=1}^{m}\sum_{j=1}^{n}\binom{i+j-2}{i-1}\binom{m+n-i-j}{m-i}=m\dbinom{m+n-1}{m}\]可以检查它确实关于 $m,n$ 对称。这个等式该如何证明？

hbghlyj

hbghlyj 发表于 2024-10-25 17:57
这个等式该如何证明？

弄懂了！其实就是upper negation版的Vandermonde's identity

我们来化简
\[\sum_{i=1}^{m}\sum_{j=1}^{n}\binom{i+j-2}{i-1}\binom{m+n-i-j}{m-i}\]
首先进行“upper negation” $\binom{n}{r}=(-1)^r\binom{-n+r-1}{r}$ 得
\[=\sum_{i=1}^{m}\sum_{j=1}^{n}(-1)^{i-1}\binom{-j}{i-1}(-1)^{m-i}\binom{-n+j-1}{m-i}\]
交换求和次序
\[=\sum_{j=1}^{n}\sum_{i=1}^{m}(-1)^{m-1}\binom{-j}{i-1}\binom{-n+j-1}{m-i}\]
由Vandermonde's identity得
\[=\sum_{j=1}^{n}(-1)^{m-1}\binom{-n-1}{m-1}\]
再次“upper negation”得
\[=\sum_{j=1}^{n}\binom{n+m-1}{m-1}\]
\[=n\binom{n+m-1}{m-1}\]