二項係数と組合せ数学

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

二項係数と組合せ数学の違い

二項係数 vs. 組合せ数学

数学における二項係数（にこうけいすう、binomial coefficients）は二項展開において係数として現れる正の整数の族である。二項係数は二つの非負整数で添字付けられ、添字 を持つ二項係数はふつう \tbinom と書かれる（これは二項冪 の展開における の項の係数である。適当な状況の下で、この係数の値は \tfrac で与えられる）。二項係数を、連続する整数 に対する各行に を から まで順に並べて得られる三角形状の数の並びをパスカルの三角形と呼ぶ。 この整数族は代数学のみならず数学の他の多くの分野、特に組合せ論において現れる。-元集合から -個の元を（その順番を無視して）選ぶ方法が \tbinom nk 通りである。二項係数の性質を用いて、記号 \tbinom nk の意味を、もともとの および が なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。. 組合せ数学（くみあわせすうがく、combinatorics）や組合せ論（くみあわせろん）とは、特定の条件を満たす（普通は有限の）対象からなる集まりを研究する数学の分野。特に問題とされることとして、集合に入っている対象を数えたり（数え上げ的組合せ論）、いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり（組合せデザインやマトロイド理論）、「最大」「最小」「最適」な対象をみつけたり（極値組合せ論や組合せ最適化）、それらの対象が持ちうる代数的構造をみつけたり（代数的組合せ論）することが挙げられる。.

多重集合

数学における多重集合（たじゅうしゅうごう、multiset）あるいはバッグ（bag; かばん）は、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという重複度を考え合わせた集合概念である。非順序対、非順序組 (unordered tuple) ともいう。 クヌースによれば、1970年代に最初に多重集合 (multiset) という言葉を提案したのは、オランダ人数学者のニコラース・ホーバート・ド・ブラン (IPA) であるという クヌースは同書で、多重集合に対して提案された他の名前（例えば,リスト(list)、まとまり(bunch)、バッグ(bag)、堆積(heap)、標本(sample)、重みつき集合(weighted set)、コレクション(collection)、組(suite).など）も提示している。 多重集合の歴史に関するサーベイ論文である。 。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表されたリヒャルト・デデキントの有名な論文 "Was sind und was sollen die Zahlen?" （「数とは何か、何であるべきか？」）において、実質的に多重集合の概念が用いられている。.

二項係数と多重集合 · 多重集合と組合せ数学 · 続きを見る »

二項定理

初等代数学における二項定理（にこうていり、binomial theorem）または二項展開 (binomial expansion) は二項式の冪の代数的な展開を記述するものである。定理によれば、冪 は の形の項の和に展開できる。ただし、冪指数 は を満たす非負整数で、各項の係数 は と に依存して決まる特定の正整数である。例えば の項の係数 は二項係数 \tbinom (.

二項係数と二項定理 · 二項定理と組合せ数学 · 続きを見る »

係数

係数（けいすう、coefficient）は、多項式の各項（単項式）を構成する因子において、変数（不定元）を除いた、定数等の因子である。例えば、4α+3β+2における、4と3と2である。この例では2がそれであるが、それ自体で項全体となっている項（あるいは、形式的には 1に掛かっている係数）を、特に定数項と呼ぶ。.

二項係数と係数 · 係数と組合せ数学 · 続きを見る »

パスカルの三角形

パスカルの三角形（パスカルのさんかくけい、英語：Pascal's triangle）は、二項展開における係数を三角形状に並べたものである。ブレーズ・パスカル（1623年 - 1662年）の名前がついているが、実際にはパスカルより何世紀も前の数学者たちも研究していた。 この三角形の作り方は単純なルールに基づいている。まず最上段に1を配置する。それより下の行はその位置の右上の数と左上の数の和を配置する。例えば、5段目の左から2番目には、左上の1と右上の3の合計である4が入る。このようにして数を並べると、上から n 段目、左から k 番目の数は、二項係数 に等しい（n-1Ck-1 と表すこともある）。これは、パスカルによって示された以下の式に基づいている。 負でない整数 n ≥ k に対して が成り立つ。 パスカルの三角形は三次元以上に拡張が可能である。3次の物は「パスカルのピラミッド」「パスカルの四面体」と呼ばれる。4次以上のものは一般に「パスカルの単体」と呼ばれる。.

パスカルの三角形と二項係数 · パスカルの三角形と組合せ数学 · 続きを見る »

フィボナッチ数

フィボナッチ数列の各項を一辺とする正方形 メインページ（2007年〜2012年）で使われていたイメージ画像もフィボナッチ数列を利用している フィボナッチ数（フィボナッチすう、Fibonacci number）は、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）にちなんで名付けられた数である。.

フィボナッチ数と二項係数 · フィボナッチ数と組合せ数学 · 続きを見る »

組合せ (数学)

数学において、組合せ（くみあわせ、combination, choose）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである。組合せは組合せ論と呼ばれる数学の分野で研究される。卑近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。.

二項係数と組合せ (数学) · 組合せ (数学)と組合せ数学 · 続きを見る »

階乗

数学において非負整数 の階乗（かいじょう、factorial） は、1 から までのすべての整数の積である。例えば、 である。空積の規約のもと と定義する。 階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は 個の相異なる対象を一列に並べる方法（対象の置換）の総数が 通りであるという事実である。この事実は少なくとも12世紀にはインドの学者によって知られていた。は1677年にへの応用として階乗を記述した。再帰的な手法による記述の後、Stedman は（独自の言葉を用いて）階乗に関しての記述を与えている: 感嘆符(!)を用いた、この "" という表記は1808年にによって発明された。 階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。.

二項係数と階乗 · 組合せ数学と階乗 · 続きを見る »

階乗冪

数学、とくに離散数学の各分野における階乗冪（かいじょうべき、factorial powerKnuth, The Art of Computer Programming, Vol. は、冪乗によく似た演算だが、階乗のように因子が 1 ずつずれていく。階乗冪には下降階乗冪 (falling factorial) 降冪、下方階乗冪とも。と上昇階乗冪 (rising factorial) 昇冪、上方階乗冪とも。とがある。また、両方向へずらしながら積をとる類似の概念に、中心階乗冪 (central factorial) がある。 階乗冪は冪あるいは冪函数の類似であり、特殊函数論あるいは組合せ論に広く応用を持つ。.

二項係数と階乗冪 · 組合せ数学と階乗冪 · 続きを見る »

自然数

自然数（しぜんすう、natural number）とは、個数、もしくは順番を表す一群の数のことである。集合論においては、自然数は物の個数を数える基数のうちで有限のものであると考えることもできるし、物の並べ方を示す順序数のうちで有限のものであると考えることもできる。 自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる（詳しくは自然数の歴史と零の地位の節を参照）。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。 数学の基礎付けにおいては、自然数の間の加法についての形式的な逆元を考えることによって整数を定義する。正の整数ないしは負でない整数を自然数と同一視し、自然数を整数の一部として取扱うことができる。自然数と同様に整数の全体も可算無限集合である。 なお、文脈によっては、その一群に属する個々の数（例えば 3 や 18）を指して自然数ということもある。.

二項係数と自然数 · 組合せ数学と自然数 · 続きを見る »

数学

数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.

二項係数と数学 · 数学と組合せ数学 · 続きを見る »

数学的帰納法

数学的帰納法（すうがくてききのうほう、mathematical induction）は自然数に関する命題 が全ての自然数 に対して成り立っている事を証明するための、次のような証明手法である自然数の定義は を含む流儀とそうでない流儀があるが、ここでは後者を採用した。。.

二項係数と数学的帰納法 · 数学的帰納法と組合せ数学 · 続きを見る »