組合せ数学
選んだものがどの順番で並ぶかは問題でなくて、それぞれのものを何回でも選べるとき、あり得る組合せの数は
( n + r − 1 ) ! r ! ( n − 1 ) ! = ( n + r − 1 r ) = ( n + r − 1 n − 1 ) {\displaystyle {{(n+r-1)!} \over {r!(n-1)!}}={{n+r-1} \choose {r}}={{n+r-1} \choose {n-1}}}
になる。ここで n は選ぶ候補の数で、r は選択の回数である。
例えば、10種類のドーナッツがあるとき3つのドーナッツを選ぶ選び方は ( 10 + 3 − 1 ) ! 3 ! ( 10 − 1 ) ! = 220 {\displaystyle {{(10+3-1)!} \over {3!(10-1)!}}=220} 通りある。多重集合も参照のこと。
フランク・ラムゼイはどのような6人が集まっても、その中には常に互いに知り合いの3人か、互いに全く知らない3人が見つけられる、ということを証明した。
証明は背理法による短いものである。 この主張が正しくないと仮定する。 これは、どの3人を見てもその中の2人は知り合いで、2人は知り合いではない、ということを意味している。ここで、この6人の中の1人を"A"としよう。残りの5人の中には"A"と知り合いである3人か、知り合いでない3人が存在する。これは、片方の否定がもう片方になることから明らかである。では、始めの方の条件をまず仮定する。このとき3人中2人以上は互いに知り合いである。なぜなら、そうでないとすると、互いに知り合いでない3人がいることになり仮定に反するからである。しかし、そうすると、その2人はAも知っているので、この3人が互いに知り合いになってしまう。これは最初の仮定に矛盾する。もう一方の条件 (残りの5人には"A"と知り合いでない3人が存在すること) を仮定する場合も同様な矛盾が導かれる。
これはラムゼーの定理の特殊な場合である。
無秩序な配置に秩序を見出すという考えからラムゼー理論は生まれた。 一言で言うと、この理論は任意に大きな配置にはある別の種類の配置を少なくとも1つは含むことを主張している。