Warning: Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297

Warning: Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660

Warning: session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834

Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126

Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127

Warning: session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133

Warning: session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773

Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294

Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300

Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46

Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46

Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
http:///mymemo.xyz/wiki/api.php?action=feedcontributions&user=126.247.193.132&feedformat=atom miniwiki - 利用者の投稿記録 [ja] 2024-05-01T11:03:48Z 利用者の投稿記録 MediaWiki 1.31.0 組合せ (数学) 2017-05-17T02:06:18Z <p>126.247.193.132: 微修正</p> <hr /> <div>[[数学]]において、&#039;&#039;&#039;組合せ&#039;&#039;&#039;（くみあわせ、{{lang-en-short|combination, choose}}）とは、相異なる（あるいは区別可能な）いくつかの[[元 (数学)|要素]]の集まりからいくつかの要素を（重複無く）選び出す方法である{{sfn|岩波数学辞典|loc=184. 順列・組合せ p.&amp;nbsp;526}}。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである{{sfn|伏見|1942|loc=第I章　数学的補助手段 1節 組合わせの理論|p=5}}。組合せは[[組み合わせ数学|組合せ論]]と呼ばれる数学の分野で研究される。卑近な例でいえば、[[カードゲーム|デッキ（山札）から決まった数のカード（手札）を引く]]ことや、[[数字選択式全国自治宝くじ|ロトくじ]]などがその例である。<br /> <br /> == 定義 ==<br /> [[濃度 (数学)|位数]] {{mvar|n}} の[[有限集合]] {{mvar|E}} と[[非負整数]] {{mvar|k}} に対し、集合 {{mvar|E}} に関する&#039;&#039;&#039;組合せ&#039;&#039;&#039;とはこの集合の（有限）[[部分集合]]のことを言い、特に {{mvar|E}} に関する {{mvar|k}}-組合せ（あるいはもっと具体的に、与えられた {{mvar|n}} 個の元から {{mvar|k}} 個選んで得られる組合せ）とは {{mvar|E}} の {{mvar|k}}-元部分集合を言う。<br /> <br /> {{mvar|E}} の {{mvar|k}}-組合せ全体の成す集合を {{math|𝒫{{ind|&#039;&#039;k&#039;&#039;}}(&#039;&#039;E&#039;&#039;)}} と表す&lt;ref&gt;[[Louis Comtet]], &#039;&#039;Analyse combinatoire élémentaire&#039;&#039;, [https://books.google.fr/books?id=Mx6Va5RiENEC&amp;pg=PA2 {{p.|2}}].&lt;/ref&gt;&lt;ref&gt;Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, &#039;&#039;Problèmes choisis de mathématiques supérieures&#039;&#039;, [https://books.google.fr/books?id=TySkMs-B_JkC&amp;pg=PA120 {{p.|120}}].&lt;/ref&gt;とき、{{math|𝒫{{ind|&#039;&#039;k&#039;&#039;}}(&#039;&#039;E&#039;&#039;)}} の位数は有限であり、初等組合せ論においては {{lang|en|&#039;&#039;&#039;C&#039;&#039;&#039;ombination}} の頭文字を取って、{{mvar|{{msub|n}}C{{msub|k}}, C{{su|p=n|b=k}}, {{msup|n}}C{{msub|k}}, C{{msub|n,k}}}} または {{math|&#039;&#039;C&#039;&#039;(&#039;&#039;n&#039;&#039;, &#039;&#039;k&#039;&#039;)}} のような記号で表す。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 &lt;math&gt;\textstyle\binom{n}{k}&lt;/math&gt; と書かれる。特に[[二項定理]]<br /> : &lt;math&gt;(1+x)^n=\sum_{k=0}^{n}{n \choose k}x^k&lt;/math&gt;<br /> に係数として現れることは顕著であり、これにより &lt;math&gt;\textstyle\binom{n}{k}&lt;/math&gt; はふつう&#039;&#039;&#039;[[二項係数]]&#039;&#039;&#039;と呼ばれる。二項展開の係数として数 &lt;math&gt;\textstyle\binom{n}{k}&lt;/math&gt; を定義するものと考えれば {{math|1=&#039;&#039;k&#039;&#039; = &#039;&#039;n&#039;&#039;}} または {{math|1=&#039;&#039;k&#039;&#039; = 0}} のとき &lt;math&gt;\textstyle\binom{n}{k}=1&lt;/math&gt;, {{math|&#039;&#039;k&#039;&#039; &amp;gt; &#039;&#039;n&#039;&#039;}} のとき &lt;math&gt;\textstyle\binom{n}{k}=0&lt;/math&gt; と考えるのは自然である。<br /> <br /> 実用上は個々の係数が具体的に<br /> : &lt;math&gt;\binom{n}{k}=\frac{n\times (n-1)\times\dotsb\times(n-k+1)}{k\times(k-1)\times\dotsb\times 1} \left(= \frac{P(n,k)}{k!}\right)&lt;/math&gt;<br /> で与えられることを利用するのが簡便である。この式の分子は {{mvar|k}}-[[順列]]（{{mvar|k}}-個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれら {{mvar|k}}-個の[[置換 (数学)|並べ替え]]の総数が {{math|&#039;&#039;k&#039;&#039;!}} であることを表し。並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。<br /> <br /> == 組合せの数え上げ ==<br /> {{mvar|A}} は {{mvar|n}}-元集合で、{{mvar|a}} は {{mvar|A}} に属さない元、{{mvar|k}} は非負整数とする。このとき、{{math|&#039;&#039;A&#039;&#039; &amp;cup; {&#039;&#039;a&#039;&#039;} }}の {{math|&#039;&#039;k&#039;&#039; + 1}} 個の元からなる部分集合は、{{mvar|A}} の {{math|&#039;&#039;k&#039;&#039; + 1}} 個の元からなる部分集合か、さもなくば[[単元集合]] {{math|{&#039;&#039;a&#039;&#039;} }}に {{mvar|A}} の {{mvar|k}}-元部分集合を併せたものであるから、<br /> : &lt;math&gt;\mathcal P_{k+1}(A\cup\{a\})=\mathcal P_{k+1}(A)\cup\left\{X\cup\{a\}\mid X\in\mathcal P_k(A)\right\}<br /> &lt;/math&gt;<br /> と書ける。ただし、{{math|&#039;&#039;k&#039;&#039; &gt; &#039;&#039;n&#039;&#039;}} のとき {{math|1=𝒫{{ind|&#039;&#039;k&#039;&#039;}}(&#039;&#039;A&#039;&#039;) = &amp;empty;}} である。（この等式の位数は、[[パスカルの三角形]]を構成するのに用いる[[漸化式]] &lt;math&gt;\tbinom{n+1}{k+1}=\tbinom{n}{k+1}+\tbinom{n}{k}&lt;/math&gt; に対応する）。<br /> <br /> == 組合せの数の計算 ==<br /> {{mvar|n}}-元に対する {{mvar|k}}-組合せの総数を効率的に計算するために以下の等式が利用できる&lt;ref&gt;この式は例えば任意の精度の算術[[ライブラリ]]である [[GNU Multi-Precision Library|GMP]] が用いている。{{en}} [http://gmplib.org/manual/Binomial-Coefficients-Algorithm.html Binomial coefficients algorithm] を参照。&lt;/ref&gt;。{{math|0 ≤ &#039;&#039;k&#039;&#039; ≤ &#039;&#039;n&#039;&#039;}} として:<br /> : &lt;math&gt;\binom{n}{k} = \binom{n}{n-k},\quad \binom{n+1}{k+1} = \frac{n+1}{k+1}\binom{n}{k},\,<br /> \binom{n}{0} = 1.&lt;/math&gt;<br /> 最初の式は {{math|&#039;&#039;k&#039;&#039; ≤ &#039;&#039;n&#039;&#039;/2}} なる場合に帰着するのに利用できるし、後の二つは<br /> : &lt;math&gt;\binom{n}{k} = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \dotsb \cdot \frac{n}{k}<br /> &lt;/math&gt;<br /> となることを示せる。<br /> <br /> == 注釈 ==<br /> {{reflist}}<br /> <br /> == 参考文献 ==<br /> * {{Cite book|和書|author=西岡康夫|year=2013|title=数学チュートリアル やさしく語る 確率統計|publisher=[[オーム社]]|isbn=9784274214073|ref={{sfnref|西岡|2013}}}}<br /> * {{Cite book|和書|author=[[伏見康治]]|year=1942|title=確率論及統計論|publisher=[[河出書房]]|isbn=9784874720127|url= http://ebsa.ism.ac.jp/ebooks/ebook/204| ref={{sfnref|伏見|1942}}}}<br /> * {{Cite book|和書|editor=[[日本数学会]]編|year=2007|title=数学辞典|edition=第4版|publisher=[[岩波書店]]|isbn=9784000803090|ref={{sfnref|岩波数学辞典}}}}<br /> <br /> == 関連項目 ==<br /> * [[重複組合せ]]<br /> * [[順列]]<br /> * [[重複順列]]<br /> * [[置換 (数学)]]<br /> * [[重複置換]]<br /> * {{仮リンク|12種の数え上げ問題|en|Twelvefold way}}<br /> <br /> == 外部リンク ==<br /> * {{MathWorld | title= Combination | urlname= Combination}}<br /> * {{MathWorld | title= Choose | urlname= Choose}}<br /> * {{MathWorld | title= k-Subset | urlname= k-Subset}}<br /> <br /> {{DEFAULTSORT:くみあわせ}}<br /> [[Category:組合せ論|*]]<br /> [[Category:数学に関する記事]]</div> 126.247.193.132
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46