■ポール・エルデス・離散数学の魅力(その74)
n個の元からなる集合から、以下の条件を満たすp個の組をいくつ作れるか?
どのq個の組もそれらのp個の組に1回しか現れない。
もし、配列は常に可能とは限らないが、可能ならば、答えはC(n,q)/C(p,q)である。
p=3,q=2の特別な場合は
n個の元からなる集合から、以下の条件を満たす3つ組をいくつ作れるか?
どのペアもそれらのp個の組に1回しか現れない。
この場合、n=6k+1,またはn=6k+3の形で表されなければならない。
n=7のとき、C(7,2)/C(3,2)=7 (本質的にひとつ)
n=9のとき、C(9,2)/C(3,2)=12 (本質的にひとつ)
n=13のとき、C(13,2)/C(3,2) (本質的にふたつ)
n=15のとき、C(15,2)/C(3,2) (本質的に80)
n=19,21,25,27,・・・のとき、C(n,2)/C(3,2) (本質的に何百万)
nが3で割れるとき、すなわち、n=6k+3のとき、分解可能である
===================================