听说所有symmetric Pascal matrix的行列式都是1

故事背景是这样的。。r_64在进入五道口抖m体校之后，成了脑浆炸裂男孩，发现什么题都做不出了，急需一发数学题来补补脑。。

然后听说symmetric Pascal matrix的行列式都是1。。觉得这个东西的证明好像是个水题。。然后就开始刚

没错这是个水题。。结果脑浆炸裂男孩硬是花了将近一周才证出来。。

首先说一下symmetric Pascal matrix是什么吧。。举个例子

\begin{pmatrix}1&1&1&1\\1&2&3&4\\1&3&6&10\\1&4&10&20\end{pmatrix}

对任意一个$n$，定义$M$为一个$n\times n$矩阵，$M_{ij}=\binom{i+j}{j}$，其中$M$的行、列编号都是$0\sim (n-1)$。

求证：$\det(M)=1$。

先注明：以下符号中$\binom{n}{m}$表示$n$个球中选$m$个的方案数。。要强调的是$0\le m\le n$不成立时$\binom{n}{m}=0$。

这个证明会按照我思考的顺序来。。不知道有没有更妙的方法，反正我想的比较歪。。

首先，大小为$n$的sPm的左上角就是大小为$n-1$的sPm。。这诱导我们使用数学归纳法，把最下面一行消成一堆$0$最后一个数的形式，再证明这个数是$1$，就好了。

然后脑浆炸裂了，不知道怎么消元就去找规律，找了几个规律发现是第$i$行乘以$(-1)^{n+i+1}\binom{n-1}{i}$然后加到最后一行上面。

也就是说，令$M$的第$i$行为$r_i$，那么

$$\det(A)=\det(\begin{pmatrix}r_0\\r_1\\\vdots\\r_{n-1}\end{pmatrix})=\det(\begin{pmatrix}r_0\\r_1\\\vdots\\\sum_{i=0}^{n-1}(-1)^{n+i+1}\binom{n-1}{i}r_i\end{pmatrix})$$

然后我们再证明$\sum_{i=0}^{n-1}(-1)^{n+i+1}\binom{n-1}{i}r_i=\begin{pmatrix}0&0&\dots&0&1\end{pmatrix}$，这样按最后一行展开就大功告成了。

根据我的找规律大法，

$$\sum_{i=0}^{n-1}(-1)^{n+i+1}\binom{n-1}{i}\binom{i+j}{j}=\binom{j}{n-1}$$

(其实我们只需要利用$j\le n-1$的情况就好，然而这整个式子是可以证的)

然后脑浆炸裂男孩跟这个式子刚了一周

首先我们令$N=n-1$就相当于证

$$LHS=\sum_{i=0}^N(-1)^{N+i}\binom{N}{i}\binom{i+j}{j}=\binom{j}{N}\ \ \ \ (1)$$

然后这个式子不是很漂亮就改一下

$$LHS=\sum_{i=0}^N(-1)^i\binom{N}{i}\binom{N-i+j}{j}$$

于是我望着这个式子陷入了沉思炸裂。。

因为有$(-1)$的多少次方所以肯定是集合容斥。。然而我并不会容斥那一套理论，那就用反演来做吧。

强行扯入集合，那么$LHS=\sum_{S\subseteq [N]}(-1)^{|S|}\binom{N-|S|+j}{j}$，其中$[N]=\{0,1,\dots,N-1\}$。

然后想办法把最正常的反演形式套进去。。正常的反演形式指的是$\sum_{S\subseteq T}(-1)^{|S|}=[T=\emptyset]$。

根据上面的公式我们会想到枚举$S$的超集$T$，然后交换枚举顺序啥的。但是在哪枚举$T$呢?换句话说$T$的意义是什么?

我们分析一下原式。。$\binom{N-|S|+j}{j}$相当于有$j$个黑球$N$个白球，$S$是白球的子集，$S$内不能选，从可以选的球中选出$j$个。

那么很容易想到让$T$表示所有没有被选的白球，这样

$$LHS=\sum_{S\subseteq T\subseteq [N]}(-1)^{|S|}\binom{j}{j-N+|T|}$$

(其实写到$T$的定义这里我发现这就是个容斥。。只是感觉这样理解而且把推式子中间过程写出来的话更靠谱)

上面式子中$\binom{j}{j-N+|T|}$表示：白球中$N-|T|$个已经被钦点了，所以黑球只能选$j-N+|T|$个。为了严谨我们还要考虑$j<N-|T|$的情况，此时$\binom{j}{j-N+|T|}=0$且方案数也是$0$。

好，可以用我们的魔法公式$\sum_{S\subseteq T}(-1)^{|S|}=[T=\emptyset]$代进去!

$$LHS=\sum_{T\subseteq [N]}\binom{j}{j-N+|T|}(\sum_{S\subseteq T}(-1)^{|S|})$$

然后我们直接得到$LHS=\binom{j}{j-N}=\binom{j}{N}$。

完结撒花。。脑浆爆完。。不对这里应该写QED

upd 9.29

这又是一个被r_64毁掉了的小清新定理。。查资料之后发现其实有一个很妙的证明。

令$S_n,L_n,U_n$分别为$n$阶对称pascal矩阵、左三角pascal矩阵、上三角pascal矩阵。其定义为

$$(S_n)_{ij}=\binom{i+j}{i},(L_n)_{ij}=\binom{i}{j},(U_n)_{ij}=\binom{j}{i}$$

由于$\binom{i+j}{i}=\sum_{k=0}^i\binom{i}{i-k}\binom{j}{k}=\binom{i}{k}\binom{j}{k}$

所以$S_n=L_nU_n$

然后$L_n,U_n$都是三角阵且对角线都是$1$

所以$\det(L_n)=\det(U_n)=1$

这样$\det(S_n)=1$就很显然啦

我好菜啊.jpg