组合数难题

student_qwh

杨辉三角第n行的n+1个数之和 = 2^n.

除首尾两个的1不计，第 p(p是质数) 行的每个数都能被 p 整除.

二项式 (a+b)^n 系数的平方和等于 C(2n,n) = (2n)!/(n!)^2.

由上，易证：

若 p 是素数，
则 C(2p, p) - 2 能被 p^2 整除。

设：素数 p>4，
求证：C(2p, p) - 2 能被 p^3 整除。

问：二项式 (a+b)^n 系数的立方和公式？？？

realnumber

问题即$((p+1)(p+2)....(2p-1)×2)/(1×2×3×....(p-1))=2   mod p^2或p^3$---2
因为(p,i)=1,i=1,2,3,....,p-1,
所以问题相当于证明
$(p+1)(p+2)....(2p-1)=1×2×3×....(p-1)   mod p^2或p^3$ ----③
左边这么两两搭配$(p+k)(p+p-k)=2p^2+k(p-k)=k(p-k)  modp^2$,k=1,2,....,$(p-1)/2$----①
这就证明了问题1
以下利用①证明问题2
先介绍一个同余概念----逆元
(a,p)=1,p质数,则存在整数u,v,使得等式ua+vp=1,那么ua=1(modp),称u为a的逆元.
若有ma=1(modp),则相减可得(m-u)a=0(modp),因为(a,p)=1,所以有m=u(modp)
即在p的最小非负剩余系集M={0,1,2,....,p-1}中,a的逆元是唯一存在的.------②
接③,并利用①相当于证明
$(2p^2+1(p-1))(2p^2+2(p-2))....(2p^2+(p-(p-1)/2)(p-(p+1)/2))=(p-1)!  (mod p^3)$
(注意以上左边看成2p^2的多项式,那么都是p的偶数次,高于p的2次的不必考虑,且常数项和右边相等)
所以要证明3,只要证明$2p^2$的系数是p的倍数.以下证明这个问题
$2p^2$的系数
$\sum_{k=1}^{(p-1)/2}((p-1)!)/(k(p-k))$,
而对任意k∈M,存在唯一i∈M,有$((p-1)!)/(k(p-k))=i(p-i)  mod p$,ki≠0(理由体会②)
所以$\sum_{k=1}^{(p-1)/2}((p-1)!)/(k(p-k))=\sum_{k=1}^{(p-1)/2}(k(p-k))$
=$2\sum_{k=1}^{(p-1)/2}(k(p-k))=\sum_{k=1}^{(p-1)}(k(p-k))$  modp  (理由a=0modp,则2a=0modp,反之也成立)
=$\sum_{k=1}^{p-1}(kp-k^2)=0  mod p$
完

realnumber

aoshoo.com/bbs1/dispbbs.asp?BoardID=59&ID=11354&skin=0
以前证的,不晓得对不对,现在遗忘了,有些不想看懂了.

student_qwh

设n>=2,且1+C(n,2)为完全平方数，求 n（转载）

realnumber

回复 6# student_qwh

var a,b,c,n:longint;
begin
for a:=2 to 40000 do
begin
b:=1+(a*(a-1) div 2);
c:=trunc(sqrt(b));
if c*c=b then write(a,'  ');
end;
writeln;
end.
3  6  16  33  91  190  528  1105  3075  6438  17920  37521
程序找的,估计我不会做.

student_qwh

没关系，我其实也不会，网上找的，分享一下，谢谢

student_qwh

student_qwh

兔子数列中的勾股数

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,

987,1597,2584,4181, ......


设兔子数列中的任意四个连续的兔子数：
第一个为a,第二个为b,第三个为c,第四个为d.

则(ad)^2+(2bc)^2=(b^2+c^2)^2


（转载）

student_qwh

组合论问题

设 n>1,
设 C(4n, 2n)   mod   (2n)^2 = r,
则 r 一定是大于2的偶数。即：
若 n=2^k, 则 r = 4t+2, (t>=1)
若 n≠2^k, 则 r = 4t.     (t>=1)

student_qwh

由于 $(2 n)^2$ 是 4 的倍数，所以 $r$ 是否 $4 t$ 或 $4 t+2$ 形式只取决于 $C_{4 n}^{2 n}$ 因子分解后 2 的次数到底是 0，1 还是大于 1。
设 $n=2^k \cdot h$ ，其中 $h$ 为奇数，于是 $(4 n) \neq\left(2^{k+2} h\right)!$ 中 2 的次数为 $2^{k+1} h+2^k h+2^{k-1} h+\ldots+h+c$ ，其中 $c$ 为 $h!$ 中 2 的因子的数目即 $c=\left[\frac{h}{2}\right]+\left[\frac{h}{4}\right]+\ldots$. ，显然 $h-c \geq 1$ 。而且显然将 h 写成二进制形式后可以看出，只要h中比特 1 的数目大于 1 ，那么取整过程中舍去的值就超过1．
也就是是当且仅当 $h=1$ 时 $c=1$ ，其余情况都有 $c \geq 2$ ．
而 $(2 n)!$ 中 2 的因子的数目为 $2^k h+2^{k-1} h+\ldots+h+c$ ，于是计算可以得出 $C_{4 n}^{2 n}$ 中因子 2 的数目为 $h-c$ ，所以当且仅当 $n$ 为 2 的幂时因子 2 的数目为 1 ，其余情况因子 2 的数目不小于 2 ．

student_qwh

设 C(2n, n)   mod   n^2 = r,
若 C(2n, n)   mod   n^2 = 2,                                                                           
则 n 一定是素数。

可以证明：
若 n 是偶合数，命题成立。
若 n 是奇合数，余数 r 是奇数，命题成立；
如何证明：
若 n 是奇合数，余数 r 是偶数，
r=2^k*Q ,  Q是大于 1 的奇数。