■完全グラフと同色の三角形(その3)
N(q)=q!Σ1/k!
は,完全順列の数を与える一般公式
F(q)=q!Σ(−1)^k/k!
の非交代版である.
===================================
5通の手紙と宛名の書かれた5枚の封筒があったとする.どの手紙も正しい封筒に入らないのは何通りあるかという場合の数がF(5)である.
F(5)=5!(1−1/1!+1/2!−1/3!+1/4!−1/5!)
=120(1−1+1/2−1/6+1/24−1/120)
=120−120+60−20+5−1=44
N(5)=120+120+60+20+5+1=326
F(4)=4!(1−1/1!+1/2!−1/3!+1/4!)
=24(1−1+1/2−1/6+1/24
=24−24+12−4+1=9
N(4)=24+24+12+4+1=65
F(3)=3!(1−1/1!+1/2!−1/3!)
=6(1−1+1/2−1/6)
=6−6+3−1=2
N(3)=6+6+3+1=16
F(2)=2!(1−1/1!+1/2!)
=2(1−1+1/2)
=2−2+1=1
N(2)=2+2+1=5
===================================