に基づいてパスカルよりも単純な規則を与えている。

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)}

の関係の算術三角形を確立させた。彼はさらに類似の公式を、わかりやすくするためにアラビア語のアルファベットを使いながら、繰り返しを許すときや許さない順列について適用した。彼は組合せ的な理由付けについてもいくつかの仕事をしている。

ペルシャの数学者アル・ファリシ(en:Al-Farisi)は13世紀の終わりに因数分解と組み合わせ方法に関連した考え方を導入した。アル・ファリシのアプローチは、彼自身も証明した算術の基本定理である自然数の素因数分解の一意性に基づいたものだった。アル・ファリシは三角数と二項係数の関係を見て取り、数学的帰納法の萌芽的な議論を用いて三角数や三角錐数、五胞体数、などと n 個の対象から k 個のものを選ぶ場合の数の間の関係を示している。

数え上げ的組合せ論は、おきうる事象を数え上げることが17世紀のパスカルらの仕事に始まる初等的な確率論で重要な問題になってからヨーロッパで大きな関心を集めるようになった。現代的な組合せ論は19世紀の終わりに発展を始め、パーシー・アレクサンダー・マクマホンによって1915年に発表された数え上げに関する系統的な書である組合せ解析やロナルド・フィッシャーによる実験計画法に関する1920年代の一連の仕事などをへて、20世紀にははっきりとした研究分野として確立した。近年の主要な組合せ論学者には、主に極値組合せ論に関する仕事をしてすばらしい問題を提起し解き続けたポール・エルデシュや、1960年代における数え上げ化・代数化の定式化に大きな役割を果たした ジャン・カルロ・ロタがいる。ものをどうやって数え上げるかという研究は時に数え上げ論とよばれて別の分野だと見なされることもある。
順列と組合せ
繰り返しを許した順列

ものを順番に並べることを考えていて、一つのものが何回も選ばれてもよいとき、可能な並べかたの数は n r {\displaystyle n^{r}}

になる。ここで n は選ぶ候補として考えているものの数で r は選択の回数である。

たとえば A, B, C, D の四つの文字を使って長さ三文字の文字列を作るやり方は 43 通り、つまり 64 通りある。つまり、一文字目について四つの文字のどれを選んでもよく、二文字目についてもふたたび四つの文字のどれを選んでもよく、最後の文字についてもまた四つの文字のどれを選んでもよいからである。これらをすべて掛け合わせて全体の可能性の数をえる。
繰り返しを許さない順列

ものが並ぶ順番を考えていて、それぞれものは一回しか選べないときに可能な並べ方の数は P ( n , r ) = n ! ( n − r ) ! = n ( r ) {\displaystyle P(n,r)={\frac {n!}{(n-r)!}}=n_{(r)}}

になる。ここで n は選ぶ候補として考えているものの数で r は選択の回数、! 記号は階乗を表す慣用的な記号、 n ( r ) {\displaystyle n_{(r)}} は降冪を意味するポッホハマー記号である。

例えば5人の人から3人を選び出して並べる方法は 5!/(5-3)! = 60 通りある。

r = n のとき（つまり選ぶ候補になっているものをすべて選ぶとき）には公式は n ! ( n − n ) ! = n ! 0 ! = n ! {\displaystyle {\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!}

となる。ただし 0! = 1 と解釈することにする。

例えば、3人の人がいるとき、その人たちを並べる方法は 3! つまり 3 × 2 × 1 = 6 通りある。これは、最初の人として3人のうち一人を選ぶことができ、2番目の人として残りの二人のうちどちらかを選ぶことができるが、そうすると最後に並ぶ人はもう選択の余地がないからである。これらを掛け合わせて全体の可能性の数をえる。
繰り返しを許さない組合せ

選んだものがどの順番で並ぶかは問題でなくて、それぞれのものは一回までしか選べないときあり得る組合せの数は C ( n , r ) = n ! r ! ( n − r ) ! = ( n r ) {\displaystyle C(n,r)={{n!} \over {r!(n-r)!}}={n \choose r}}

になる。ここで n は選ぶ候補の数で、r は選択の回数である。

たとえば10個の数があってそのうちから5個を選ぶ選び方は 10 ! 5 ! ( 10 − 5 ) ! = 252 {\displaystyle {{10!} \over {5!(10-5)!}}=252} 通りある。
繰り返しを許した組合せ

選んだものがどの順番で並ぶかは問題でなくて、それぞれのものを何回でも選べるとき、あり得る組合せの数は ( 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} 通りある。多重集合も参照のこと。
数え上げ組合せ論

組合せ論の始まりは特定のパターンが形成される場合の数を計算することだった。S を n 個の元からなる集合とすると、S から k 個のものを選ぶ組合せは S の部分集合で k 個の元を持つもの（要素が並ぶ順番は区別されない）に対応する。S から k 個のものを選んで並べることは k 個の相異なる S の元による順列（長さが違ったり、元が同じでも順番が違う順列は区別される）に対応する。組合せや順列の数の公式は簡単に見て取れるが組合せ論のいたるところで重要な役割を果たしている。

より一般的に、数え上げ組合せ論では、(通常、自然数全体の集合を添字集合とする) 有限集合の無限族 {Si} が与えられたとき、任意のnに対してSnの要素の数を数える数え上げ関数 f(n)を記述する様々な方法を探究している。集合の要素数を数えるという行為はかなり大きな数学的問題であるが、組合せ的な問題では集合S(n)は割と単純な組合せ的記述を持ち、付加的な構造が少ししかないことが普通である。

そのような関数で最も簡単なものは閉じた公式であり、階乗、べき乗のような単純な関数の合成で表現できるものである。例えば、上でも述べたように、n枚のトランプの異なる並べ方の数はf(n) = n!である。

このアプローチが常に満足いくもの (すなわち実用的なもの) であるとは限らない。例えば、f(n)を区間[1,n]における異なる整数から成る部分集合で連続する2つの整数を含まないものの数であるとする。例えば、n = 4の場合、{}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}という集合が得られるので、f(4) = 8である。実際、f(n)がn+2番目のフィボナッチ数F(n+2)であることが分かるので、 f ( n ) = ϕ n + 2 − ( 1 − ϕ ) n + 2 5 {\displaystyle f(n)={\frac {\phi ^{n+2}-(1-\phi )^{n+2}}{\sqrt {5}}}}