ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
インストール
ブラウザよりも高速アクセス!
 

数え上げ数学

索引 数え上げ数学

数学における初等組合せ論 (elementary combinatorics), 有限組合せ論 (finite combinatorics), 数え上げ組合せ論 (enumerative combinatorics) あるいは数え上げの数学(かぞえあげのすうがく、mathematics of counting)とは、一定のパターンに従って形作られる方法の総数を扱う組合せ論の一分野を言う。この種の問題の代表例が組合せと順列の総数を算えることである。より一般には、自然数で添字付けられた有限集合 の無限族が与えられたとき、各 に対する に属する元の総数を数える「計数函数」(counting function) を記述することを模索するのが数え上げ数学の主題である。特定の集合に属する元の数を算えるというのはより広汎なであるにも拘らず、そのような問題の多くは単純な組合せ論的記述に関連した応用から生じてくるのである。は順列、組合せおよび分割の数え上げに対する統一的な枠組みを与える。 最も単純な種類のパターンではそのような計数函数が、四則演算や冪あるいは階乗などの初等的な函数の合成となるような、として与えられる。例えば、 枚のカードからなる山札に対して、可能なすべての相異なる並べ方の総数は で与えられる。このような閉じた式を求める問題はとも呼ばれ、しばしば漸化式や母函数を導いてそれらを適切に解くことにより所望の閉じた形へ到達する。 閉じた形の式が複雑になると、算える対象の数の増加に伴って計数函数がどのように振る舞うかが洞察しづらくなることがよく起きる。そのような場合においては、単純な近似が有効となりうる。ここで函数 が の漸近近似である: とは、 が成り立つことを言う。.

15 関係: 包除原理バーンサイドの補題ポーヤの計数定理ブリタニカ百科事典第11版ケンブリッジ大学出版局組合せ (数学)組合せ爆発組合せ数学階乗順列自然数集合の分割母関数漸化式数学

包除原理

包除原理(ほうじょげんり、包含と排除の原理、 Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion (PIE))とは数え上げ組合せ論における基本的な結果のひとつで、 A1,..., An を有限集合としたとき和集合の濃度が となることをいう。(ここで |A| は集合 A の濃度をあらわす。)特別な場合 n.

新しい!!: 数え上げ数学と包除原理 · 続きを見る »

バーンサイドの補題

バーンサイドの補題(Burnside's lemma)、あるいはバーンサイドの数え上げ補題、コーシー・フロベニウスの補題、軌道の数え上げ補題とは、対称性を考慮して数学的な対象を数え上げるときに有用な群論の結果である。 以下では は有限群で集合 に作用しているとする。群 の各元 に対して で元 によって固定されるすべての の元からなる集合を表す。バーンサイドの補題は軌道の数 || は次の式で表せることを主張している。 つまり軌道の数(これは自然数あるいは+∞)は群 の元による固定点の数の平均(これも自然数あるいは+∞)と等しい。もし が無限群ならば || による除法は定義されないが、その場合には次の基数に関する主張が成り立つ。.

新しい!!: 数え上げ数学とバーンサイドの補題 · 続きを見る »

ポーヤの計数定理

組合せ論におけるポーヤの計数定理(ポーヤのけいすうていり、Pólya enumeration theorem; 数え上げ定理、枚挙定理)あるいはレッドフィールド–ポーヤの定理 (Redfield–Pólya Theorem) は、集合への群作用の軌道の総数を求めるバーンサイドの補題の極めて一般化するものである。定理が最初に公になるのは1927年のによるものだが、それとは独立にジョージ・ポリア(ポーヤ)が1937年に再発見し、ポーヤはその結果を多くの数え上げ問題、特に化合物の枚挙に適用して大いに普及させた。 ポーヤの計数定理はやに組み込むこともできる。.

新しい!!: 数え上げ数学とポーヤの計数定理 · 続きを見る »

ブリタニカ百科事典第11版

ブリタニカ百科事典第11版(ブリタニカひゃっかじてん だい11はん、1911年版ブリタニカ百科事典、1911 Encyclopædia Britannica)は、1910年から1911年にかけて発行されたブリタニカ百科事典の11番目の版で、全29巻からなる20世紀初頭の知識の集大成である。製作には当時の著名な研究者や、後に有名になる執筆者が多数参加している。また、この版は現在、米国で著作権の保護期間を経過しパブリックドメインになっている。.

新しい!!: 数え上げ数学とブリタニカ百科事典第11版 · 続きを見る »

ケンブリッジ大学出版局

ンブリッジ大学出版局(Cambridge University Press)は、ケンブリッジ大学の出版事業を手がける出版社である。1534年、ヘンリー8世により特許状が発せられたのを起こりとする世界最古の出版社、かつ世界第2の規模の大学出版局であり、聖書や学術誌の出版も手掛けている。 「出版活動を通して、大学の理念である全世界における学問、知識、研究の促進を推し進めること」を使命として掲げている。これは、ケンブリッジ大学規約中の「Statute J」に規定されている。そして、「公益のため継続的に出版活動を行い、ケンブリッジという名前の評価を高めること」を目的としている。 ケンブリッジ大学出版局は、学術、教育分野の書籍の出版を行なっており、ヨーロッパ、中東、アフリカ、アメリカ、アジア太平洋といった地域で事業を展開している。世界中に50以上の事業所を持ち、2000人近くの従業員を抱え、4万以上のタイトルの書籍を発行している。その種類は、専門書、教科書、研究論文、参考書、 300近くに及ぶ学術誌、聖書、祈祷書、英語教育教材、教育ソフト、電子出版など、多岐にわたる。.

新しい!!: 数え上げ数学とケンブリッジ大学出版局 · 続きを見る »

組合せ (数学)

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

新しい!!: 数え上げ数学と組合せ (数学) · 続きを見る »

組合せ爆発

組合せ爆発(くみあわせばくはつ、Combinatorial explosion)は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ(combination)的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。.

新しい!!: 数え上げ数学と組合せ爆発 · 続きを見る »

組合せ数学

組合せ数学(くみあわせすうがく、combinatorics)や組合せ論(くみあわせろん)とは、特定の条件を満たす(普通は有限の)対象からなる集まりを研究する数学の分野。特に問題とされることとして、集合に入っている対象を数えたり(数え上げ的組合せ論)、いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり(組合せデザインやマトロイド理論)、「最大」「最小」「最適」な対象をみつけたり(極値組合せ論や組合せ最適化)、それらの対象が持ちうる代数的構造をみつけたり(代数的組合せ論)することが挙げられる。.

新しい!!: 数え上げ数学と組合せ数学 · 続きを見る »

階乗

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

新しい!!: 数え上げ数学と階乗 · 続きを見る »

順列

初等組合せ論における順列(じゅんれつ、sequence without repetition、arrangement)は、区別可能な特定の元から有限個を選んで作られる重複の無い有限列をいう。 初等組合せ論における「」はともに n-元集合から -個の元を取り出す方法として可能なものを数え上げる問題に関するものである。取り出す順番を勘案するのが -順列、順番を無視するのが -組合せである。.

新しい!!: 数え上げ数学と順列 · 続きを見る »

自然数

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

新しい!!: 数え上げ数学と自然数 · 続きを見る »

集合の分割

集合を6つの部分に分割した図(オイラー図による表現) 数学において、集合 X の分割 (partition) とは、X 全体を互いに重ならない部分/ブロック/セルに分けることを言う。より形式的に言えば、それらの「セル」は分割された集合から見て相互に排他的で完全な全体集合 (MECE) となっている。.

新しい!!: 数え上げ数学と集合の分割 · 続きを見る »

母関数

数学において、母関数(ぼかんすう、generating function; 生成関数)は、(自然数で添字付けられた)数列 に関する情報を内包した係数を持つ、形式的冪級数である。母関数は、一般線型回帰問題の解決のためにド・モアブルによって1730年に初めて用いられた。複数の自然数で添字付けられる数の配列(多重数列)の情報を取り込んだ多変数冪級数を同様に考えることもできる。 母関数には、通常型母関数、指数型母関数、ランベルト級数、ベル級数、ディリクレ級数 など様々なものがある。これらについては定義と例を後述する。原理的にはあらゆる列についてそれぞれの種類の母関数が存在する(ただし、ランベルト級数とディリクレ型は添字を 1 から始めることが必要)が、扱い易さについてはそれぞれの種類で相当異なるかもしれない。どの母関数が最も有効かは、その列の性質と解くべき問題の詳細に依存する。 母関数を、形式的冪級数に対する演算・操作を用いるなどして(級数の形ではなく)の式で表すこともよく行われる。このような母関数の表示は、母関数の不定元を x とすれば、四則演算、母関数のx に関する微分、他の母関数へ代入すること、などを行った結果として得られる。これらの操作は関数に対しても定義されるものであるし、結果として得られる式もやはり x の関数であるかのように見える。実際、母関数を x の(十分小さい)具体的な値で評価することのできる関数として解釈することができる場合も少なくない(このとき、母関数の冪級数表示は、母関数の閉じた形の式のテイラー級数と解釈される)のであり、それがこの式が「母関数」と呼ばれる所以でもある。しかし、形式的冪級数は x に何らかの数値を代入したときに収束するかどうかは問題にしないのであって、母関数についてそのような関数としての解釈が可能であるということは必ずしも要求されるものではないし、同様に x の関数として意味を持つ式がいずれも形式的冪級数に対して意味を持つわけではない。 慣例的に母「関数」と呼ばれてはいるが、始域から終域への写像という関数の厳密な意味に照らして言えば母関数は関数ではなく、今日的には生成級数(母級数)と呼ぶこともしばしばである。.

新しい!!: 数え上げ数学と母関数 · 続きを見る »

漸化式

数学における漸化式(ぜんかしき、recurrence relation; 再帰関係式)は、各項がそれ以前の項の函数として定まるという意味で数列を再帰的に定める等式である。 ある種の漸化式はしばしば差分方程式 (difference equation) と呼ばれる。また、「差分方程式」という言葉を単に「漸化式」と同義なものとして扱うことも多い。 漸化式の例として、ロジスティック写像 が挙げられる。このような単純な形の漸化式が、しばしば非常に複雑な(カオス的な)挙動を示すことがあり、このような現象についての研究は非線型解析学などと呼ばれる分野を形成している。 漸化式を解くとは、 添字 n に関する非再帰的な函数として、一般項を表すの式を得ることをいう。.

新しい!!: 数え上げ数学と漸化式 · 続きを見る »

数学

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

新しい!!: 数え上げ数学と数学 · 続きを見る »

ここにリダイレクトされます:

初等組合せ論有限組合せ論枚挙組合せ論数え上げ組合せ論

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »