組合せ数学
C ( n , 1 ) = n {\displaystyle \ C(n,1)=n} , C ( n , 2 ) = n ( n − 1 ) 1 ⋅ 2 {\displaystyle C(n,2)={\frac {n(n-1)}{1\cdot 2}}} , C ( n , 3 ) = n ( n − 1 ) ( n − 2 ) 1 ⋅ 2 ⋅ 3 {\displaystyle C(n,3)={\frac {n(n-1)(n-2)}{1\cdot 2\cdot 3}}}
P ( n , 1 ) = n {\displaystyle \ P(n,1)=n} , P ( n , 2 ) = n ( n − 1 ) {\displaystyle \ P(n,2)=n(n-1)} , P ( n , 3 ) = n ( n − 1 ) ( n − 2 ) {\displaystyle \ P(n,3)=n(n-1)(n-2)}
に対応する組合せと順列の規則を含んでいる(記号C(n, r)とP(n, r)については#繰り返しを許さない組合せと#繰り返しを許さない順列節を参照のこと。)。
n が 2, 3, 4 の場合には実際の数値が計算されていて、さらに著者はより大きい n についても同じ方法で計算できると述べた。
このやり方で 5, 6, 7, ..., 10 など、あるいは数えきれるもの、数えきれないもの、無限のものまでが指定される。一時に一つのものをとる、あるいは二つのものをとる、...、十個のものをとる、組合せの数が構成された以上それらはすべて達成される。
これは算術が様々な無限大の数に拡張されうることを示唆している。組合せの数と二項展開の係数との間の関係は紀元前3世紀にピンガラ(en:Pingala)によって楽曲の形で指摘されている。
彼はグル(guru)(長音)とラグ(laghu)(短音)の様々な組み合わせをいわゆるパスカルの三角形(彼はメル・プラスターラ /「メル山(須弥山)の階段」と呼んだ)によって与え、公式
C ( n + 1 , r ) = C ( n , r ) + C ( n , r − 1 ) {\displaystyle \ C(n+1,r)=C(n,r)+C(n,r-1)}
に基づいてパスカルよりも単純な規則を与えている。
6世紀のヴァラーハミヒラは「16 のものが 4 つの方向に行くとしたら 1820 通りの結果がある」と記している。彼はこの事実をパスカルの三角形に似た規則を用いて見いだした。9世紀にはマハーヴィーラが組合せの数を計算するアルゴリズムをはっきりとした形で与え、有名な一般式
C ( n , r ) = n ( n − 1 ) ( n − 2 ) ⋯ ( n − r + 1 ) r ! {\displaystyle C(n,r)={\frac {n(n-1)(n-2)\cdots (n-r+1)}{r!}}}
を示した。
時代が下って、イスラム圏の数学者たちは遅くとも13世紀から組合せの研究をしている。13世紀の初めに北アフリカのマグレブでイブン・ムニーム(Ibn Mun'im)は組合せ論の問題に取り組んでいる。彼は n 種類の色をp回組み合わせる方法の場合をすべて決定する規則を述べ、帰納的に
C ( n , p ) = C ( n − 1 , p − 1 ) + C ( n − 2 , p − 1 ) + ⋯ + C ( p − 1 , p − 1 ) {\displaystyle \ C(n,p)=C(n-1,p-1)+C(n-2,p-1)+\dots +C(p-1,p-1)}