組合せ数学
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/02/08 14:45 UTC 版)
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2024年1月) |
組合せ数学(くみあわせすうがく)あるいは組合せ論(くみあわせろん、英: combinatorics)とは、特定の性質を備えた(普通は有限の)対象からなる集まりについて研究する数学の分野であり、離散数学と呼ばれる分野の一つである。
組合せ論において研究されるのは主に以下のような問題である:
- 特定の性質を備えた対象を数えること。(数え上げ組合せ論)
- 様々な対象が特定の性質を帯びるか判定したり、特定の性質を備えた対象を構成あるいは解析すること。(組合せデザイン)
- 要素同士の関連性がなす部分的または全体的な構造について調べること。(グラフ理論)
- 特定の性質を有する対象の中で、何らかの観点における「最大(最小)」あるいは「極大(極小)」のものを特定すること。(極値組合せ論)
- 代数的構造を伴う対象について、あるいは対象に代数的構造を与えることで、上記のような組合せ論の問題に答えること。(代数的組合せ論)
数学の諸分野の分類体系であるMSC2020においては、大分類として組合せ論に05が、その下の中分類として数え上げ組合せ論に05A、デザインと配置に05B、グラフ理論に05C、極値組合せ論に05D、代数的組合せ論に05Eが、それぞれ割り当てられている[1]。
概観と歴史
組合せ数学は理論構築と同じくらい、(特に20世紀後半以降は)与えられた問題を解決することが目標になっている。組合せ数学のうちで最も古く取っ付きやすいものはグラフ理論であり、今では他の様々な分野と結びつけられている。
組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか?というものが挙げられる。これに対する答えは 52! (52 の階乗)であり、この数は(だいたい 8.065817517094 × 1067)、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数(1068)に匹敵するほど大きい。
別の種類の問題には、n人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか?というものがある。答えはnにより、今でも部分的な回答しかえられていない。 組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ(en:Sushruta)によって書かれた医学書スシュルタ・サミタ(en:Sushruta Samhita)には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは
組合せ (数学)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/10/22 13:31 UTC 版)
![]() | この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
数学において、組合せ(くみあわせ、英: combination, choose)とは、有限個の互いに区別可能な要素の集まりから有限個を選び出す方法である[1]。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである[2]。組合せは組合せ数学と呼ばれる数学の分野で研究される。身近な例でいえば、デッキ(山札)から決まった数のカード(手札)を引くことや、ロトくじなどがその例である。
日常では組合せとは要素が2個以上の物を示すが、数学においては要素が1個や0個の場合も組合せの内に含めて考える。
定義
位数 n の有限集合 E と非負整数 k に対し、集合 E に関する組合せとはこの集合の(有限)部分集合のことを言い、特に E に関する k-組合せ(あるいはもっと具体的に、与えられた n 個の元から k 個選んで得られる組合せ)とは E の k-元部分集合を言う。
E の k-組合せ全体の成す集合を 𝒫k(E) と表す[3][4]とき、𝒫k(E) の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、nCk , Cn
k , nCk , Cn,k または C(n, k) のような記号で表す。ピエール・エリゴンが1634年の『実用算術』で nCk の記号を定義した[5]。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合