前两天人教群的组合题$\abs{a_i-a_k}=1$

kuing

鄂L教师yuzi(5755*****) 20:25:14


粤A爱好者fungarwa(2593******) 23:08:22
(1,?,?,?,?,?)=(1,2,3,4,5,6)=1
(2,?,?,?,?,?)=(2,1,3,4,5,6)+(2,3,?,?,?,?)
=1+(2,3,1,4,5,6)+(2,3,4,?,?,?)
=2+(2,3,4,1,5,6)+(2,3,4,5,?,?)=5
(3,?,?,?,?,?)=(3,2,?,?,?,?)+(3,4,?,?,?,?)
=(3,2,1,4,5,6)+(3,2,4,?,?,?)+(3,4,2,?,?,?)+(3,4,5,?,?,?)
=1+(3,2,4,1,5,6)+(3,2,4,5,?,?)+(3,4,2,1,5,6)+(3,4,2,5,?,?)+(3,4,5,2,?,?)+(3,4,5,6,2,1)
=4+2+2+2=10

16*2=32

粤A爱好者fungarwa(2593******) 23:23:03
(?,?,...,?,X,?,...,?,?)
=(?,?,...,X,X,?,...,?,?)+(?,?,...,?,X,X,...,?,?)
=(?,?,...,X,?,...,?,?)+(?,?,...,?,X,...,?,?)
a(n,k)=a(n-1,k-1)+a(n-1,k)
...真的是C

鄂L教师yuzi(5755*****) 23:31:11
好高端大气，就是不懂
粤A爱好爪机kuing(4396*****) 23:31:30
不明觉厉
鄂L教师yuzi(5755*****) 23:32:17
这个递推。嘛意思 。不明觉厉

看不懂的说，那个……@tommywong 可以解释一下是啥意思么

tommywong

在$a_1=k$时，都有$C_5^{k-1}$种排列，总排列数为$2^5=32$

刚开始时考虑$(a_1,a_2,a_3,a_4,a_5,a_6)$，但后来证明递推式的是另一种角度。

若$a_1=3$，把该情况考虑成$(?,?,X,?,?,?)$，换句话说3被用掉了。
轮到$a_2$，$|a_2-a_1|=1$，即$a_2$从$a_1$向左走向右走
$(?,?,X,?,?,?)=(?,X,X,?,?,?)+(?,?,X,X,?,?)$
轮到$a_3$，$|a_3-a_1|=1$，$|a_3-a_2|=1$，
此时应该发现了，从这个角度看的话不需要再理会那些$X$到底是$a_1$还是$a_2$
因为直接向左走向右走就可以了
$(?,X,X,?,?,?)+(?,?,X,X,?,?)=(X,X,X,?,?,?)+(X,X,X,X,?,?)+(?,X,X,X,?,?)+(?,?,X,X,X,?)$