证明一个组合求和公式：∑(k=0,min(m,n))(-1)^k C(m,k) C(m+n-k,m)=1

0-1110

0-1110

感谢各位老师：
不曾想此题轻易地被“二进制”+“位运算”证明并扩展了！
不由想到年前的：
《宿南澳岛》
云舒云卷海天清
潮落潮生岛月明
大浪淘沙淘不净
无名小贝也晶莹

王守恩

0-1110 发表于 2022-9-25 13:21

连这也可以有通项公式的!

任取自然数 m,n,    m≥n,    在集合 {0,1,2,...,n} 中，

有且仅有一个元素 k,    使得 \(\frac{(m+n-k)!}{k!(m-k)!(n-k)!}\) 为奇数。

记满足 \(\frac{(m+n-k)!}{k!(m-k)!(n-k)!}\) 为奇数的 k 为 a(m,n)=k,

a(0,0)=0,
a(1,0)=0,  a(1,1)=1,
a(2,0)=0,  a(2,1)=0,  a(2,2)=2,
a(3,0)=0,  a(3,1)=1,  a(3,2)=2,  a(3,3)=3,
a(4,0)=0,  a(4,1)=0,  a(4,2)=0,  a(4,3)=0,  a(4,4)=4,


                                                             00
                                                           00,01,
                                                         00,00,02,
                                                       00,01,02,03,
                                                     00,00,00,00,04,
                                                   00,01,00,01,04,05,
                                                 00,00,02,02,04,04,06,
                                               00,01,02,03,04,05,06,07,
                                             00,00,00,00,00,00,00,00,08,
                                           00,01,00,01,00,01,00,01,08,09,
                                         00,00,02,02,00,00,02,02,08,08,10,
                                       00,01,02,03,00,01,02,03,08,09,10,11,
                                     00,00,00,00,04,04,04,04,08,08,08,08,12,
                                   00,01,00,01,04,05,04,05,08,09,08,09,12,13,
                                 00,00,02,02,04,04,06,06,08,08,10,10,12,12,14,
                               00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,
                             00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,16,
                           00,01,00,01,00,01,00,01,00,01,00,01,00,01,00,01,16,17,
                         00,00,02,02,00,00,02,02,00,00,02,02,00,00,02,02,16,16,18,
                       00,01,02,03,00,01,02,03,00,01,02,03,00,01,02,03,16,17,18,19,
                     00,00,00,00,04,04,04,04,00,00,00,00,04,04,04,04,16,16,16,16,20,
                    00,0100,01,04,05,04,05,00,01,00,01,04,05,04,05,16,17,16,17,20,21,
                  00,00,02,02,04,04,06,06,00,00,02,02,04,04,06,06,16,16,18,18,20,20,22,
                00,01,02,03,04,05,06,07,00,01,02,03,04,05,06,07,16,17,18,19,20,21,22,23,
              00,00,00,00,00,00,00,00,08,08,08,08,08,08,08,08,16,16,16,16,16,16,16,16,24,
            00,01,00,01,00,01,00,01,08,09,08,09,08,09,08,09,16,17,16,17,16,17,16,17,24,25,
          00,00,02,02,00,00,02,02,08,08,10,10,08,08,10,10,16,16,18,18,16,16,18,18,24,24,26,
        00,01,02,03,00,01,02,03,08,09,10,11,08,09,10,11,16,17,18,19,16,17,18,19,24,25,26,27,
      00,00,00,00,04,04,04,04,08,08,08,08,12,12,12,12,16,16,16,16,20,20,20,20,24,24,24,24,28,
    00,01,00,01,04,05,04,05,08,09,08,09,12,13,12,13,16,17,16,17,20,21,20,21,24,25,24,25,28,29,
  00,00,02,02,04,04,06,06,08,08,10,10,12,12,14,14,16,16,18,18,20,20,22,22,24,24,26,26,28,28,30,
00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,28,30,31,

0-1110

感谢您的关注，
通项公式a(m,n)=k，如果k能用m,n表示出来，那就好了，估计难！

王守恩

0-1110 发表于 2022-12-3 13:10
感谢您的关注，
通项公式a(m,n)=k，如果k能用m,n表示出来，那就好了，估计难！

a(m,n)=BitAnd[m, n]=\(m_{2}*n_{2}\)=k,

\(m_{2}\): 用二进制来表示 m,
\(n_{2}\):  用二进制来表示 n,
\(*\): 二进制乘法(四句口诀: 0*0=0, 0*1=0, 1*0=0, 1*1=1)
    k 表示 \(m_{2}*n_{2}\) 所得的结果。

0-1110

明白了，比如：m=25,n=10
11001
01010
--------
01000
k=8

王守恩

0-1110 发表于 2022-12-4 11:07
明白了，比如：m=25,n=10
11001
01010

仔细观察金字塔：可以发现很多有趣的规律。