鳩の巣原理の一般化
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/25 08:26 UTC 版)
鳩の巣原理を一般化する。n 個の離散的な対象を m 個の入れ物に割り当てるとすると、少なくとも1個の入れ物には、 ⌈ n / m ⌉ {\displaystyle \lceil n/m\rceil } 個より少なくない対象が割り当てられている。ここで ⌈ x ⌉ {\displaystyle \lceil x\rceil } は天井関数のことであり、x に等しいか、xより大きい最小の整数を表す。 鳩の巣原理はさらに一般化され、グラフなどのより複雑な数学的構造、また算術的な関係などに対しても類似の定理が知られている(ラムゼーの定理など)。それらをラムゼー型の定理という。
※この「鳩の巣原理の一般化」の解説は、「鳩の巣原理」の解説の一部です。
「鳩の巣原理の一般化」を含む「鳩の巣原理」の記事については、「鳩の巣原理」の概要を参照ください。
- 鳩の巣原理の一般化のページへのリンク