組合せの全体を算出できる数式は存在しますか?(再)
- 組合せの総数を算出するための数式や漸化式がありますが、組合せの全体を算出できる閉じた代数計算式は存在しないかもしれません。
- 最近、組合せ論に関する論文が公開されました。それは独自の漸化式を用いて組合せの全体を算出する方法を提案しています。
- この論文では、組合せの要素を取り出すための独自の組合せ網羅漸化式が示されており、組合せの全体が算出できます。しかし、同等の閉じた代数計算式はまだ存在しないようです。
- ベストアンサー
組合せの全体を算出できる数式は存在しますか?(再)
★★ 以下の内容をカテゴリ「数学・算数」へ1月19日に投稿しましたが,未だに回答が皆無で,"OKWAVE サポート担当" 様のご指導により「科学」へ再投稿してみました.★★ (再投稿) 最近(2018年12月12日)以下のような論文が,科学技術振興機構の運営する或る団体のサイトに提示されました. それは,数学の組合せ論に関する論文で「繰り返しを許さない組合せ」について,組合せの全体を算出できる数式(漸化式)に関する研究報告です. ● 論文タイトル:「繰り返しを許さない組合せの各組を全て算出できる数式」 組合せ論における「繰り返しを許さない組合せ」に関して,候補の数を n とし,選択の数を r とすると,組合せの総数 C(n,r) は,C(n,r) = n!/r!(n-r)! で与えられます. n と r,(n≧r)を任意に与えて,総個数が C(n,r) 個あるこの組合せの全てを,下記に示す数式(漸化式)で算出できます. この論文では,下に示す"組合せ網羅漸化式"(仮称)を用いた計算結果が,数多く示されています. 具体的には,例えば,組合せの要素を,1,2,3,4,5 で表し,この5個の要素から,4個を取り出した組み合せは, 〈1,2,3,4〉〈1,2,3,5〉〈1,2,4,5〉〈1,3,4,5〉〈2,3,4,5〉の5種類です. この5種類ような組合せも数式を用いて算出する方法が記述されています. この様な例のほか,全ての組み合せについて,ひとつの組合せ網羅漸化式を用いて組合せの全体が算出できます. 下記の数式以外で,これと同等の考え方・目的・主旨をもって創られている数式が存在すれば,それを教えて下さい. コンピューターを用いる数値計算で組合せを構成する方法は除きます.閉じた代数計算式の存在を問います.
- Knotopolog
- お礼率96% (178/184)
- 科学
- 回答数2
- ありがとう数4
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
自分だったらtは使わずb_k=b_{k-1}+1, ... , n-r+kとしますね。あとは『残り文字数m=r-k』を定義するか。まあこれはただの気分ですが。 論文拝見いたしました。それでこれのどこが代数っぽいと主張なされているのでしょうか? b_{k-1}がある値のときに、b_kが取りうる値を列挙して、b_{k-1}がそうである組み立て途中の組み合わせをこれまでの結果から漏れなく列挙してb_kと直積をとる、という手順のようですね。もれなく列挙するあたりで「これはコンピューターにはできまい、代数的だ!」とか思ったのでしょうか? 参考URLの画像をご覧ください。赤塗りつぶしがb_1~b_3に対応しており、同じ式で動いているものです。違いは、b_1の最初の候補『1』に着目した途端にb_2の候補のリストアップを始めて、b_2の最初の候補『2』に着目した途端にb_3の候補をリストアップし、最終的な組み合わせをとりあえず3個完成させていることです。こういう手順だとb_2=3のときのb_3の候補のリストアップが(1, 3, ...)と(2, 3, ...)の2回で重複して行うことになってしまいますが、組み立て途中の組み合わせを管理する必要がなくなります。これこそ小学生でもできる確実な計算方法です。 これまでの結果から列挙するのがだめということではありません(抜き出す操作の結果に興味深い性質が見つかったりするかもしれないし)が、それをするならするで組み立て途中の組み合わせにきちんと名前をつけてどう並べるかも定義する必要があります。それをしなかったからやたらと注意力が必要な計算になってしまったのではないでしょうか。 というわけでその数式は世界中のプログラマーが自力で導ける自明なものであり、問題の大部分はその数式の外側にあります。
その他の回答 (1)
- noname_deadbeef
- ベストアンサー率50% (10/20)
しらみつぶしにするとしか言っていない式のどこが代数的なのかが相変わらずさっぱりですが… 別解を挙げよとのことなので、 C(n,r)=C(n-1,r-1)+C(n-1,r) に対応する組み合わせ列挙方法を述べます。 (1, 2, ..., n)からr個を重複なく取り出す組み合わせは、以下の2群に分けられます。 (i) (1, 2, ..., n-1)からr個を重複なく取り出した組み合わせ。 (ii) (1, 2, ..., n-1)からr-1個を重複なく取り出した組み合わせのそれぞれにb_r=nを追加したもの。 なおr=0の場合はすべての組み合わせは{()}(空集合1個)となります。 r=nの場合はすべての組み合わせは{(1, 2, ..., n)}(集合1個)となります。 以上の定義を再帰的に適用することにより、すべての組み合わせを算出することができます。 これももちろん既知のアルゴリズムです。どこかの参考書には書いてありそうなレベルの内容です。
お礼
再投稿,ありがとうございます. 質問者さんに数式を作れと頼んではいません.世界のどこかに数式が存在するのかどうかを問うているだけです. 質問者さんは「代数的」という言葉に拘っていますが,これは単に,閉じた或る数式f(n,r,k)=0を意味しているだけです.
関連するQ&A
- 組合せの全体を算出できる数式は存在しますか?(2)
前回の質問に回答がありませんので,質問の主旨を変えて再度,質問します. 質問:前回の「組合せ網羅漸化式」以外に数式が無いことについて,なぜ無いのか,ご回答者諸氏方々のご意見・お考えをお聞かせ下さい.どの様な内容のご意見でもかまいません.遠慮無くご投稿下さい. ★ 前回の質問: https://okwave.jp/qa/q9579208.html 以下に「組合せ網羅漸化式」の画像を貼り付けておきます.
- ベストアンサー
- 数学・算数
- 組み合わせの漸化式について
組み合わせnCrは、漸化式nC(r-1) * (n-r+1)/rによって表されることを確かめようと、以下の計算をしたのですが、どうしても nC(r-1) * (n-r+1)になってしまいます。 nCr = n!/n!(n-r)! nC(r-1) = n!/n!(n-r+1)! nCr / nC(r-1) = n-r+1 漸化式が成り立つ理由をご教授お願いします。
- ベストアンサー
- 数学・算数
- 組合せ回数の算出数式について
エクセル関数を使って組合せ回数の算出をしたいのですが 1, 1番から20番までの番号の人があり 2, 例えば、1番と11番の人がペアとなり、2番と15番、3番と6番、等々の乱数の組合せをし 3, 次の回では、11番と1番等々のペアを作って15回まで行った場合に 4, 1番の人が2番~20番までの各々の人と何回ペアとなったか、また2番、~20番の人は何番と何 回ペアを組んだか、の算出の数式を作りたいのですが、どのような式を作ったらよいでしょうか。 宜しくお願いします。
- 締切済み
- その他(インターネット・Webサービス)
- EXCELで数式を比較する方法
既に過去例があるかもしれませんが見つけられず投稿します。よろしくお願いします。 たとえば、 2つのセルR1C1、R1C2があって、各々に数式が入っているとします。 この2つの数式自体が一致しているか否かを判定するにはどうすればよいのでしょうか? ちなみに、 =IF (R1C1=R1C2,"○","×") という条件式だと、数式の比較ではなくR1C1、R1C2に入っている数値(計算式に基づいた計算結果)の比較を行ってしまいます(当たり前だと思いますが)。 数値の比較ではなく、数式の比較をしたいのですが、どうすればいいのでしょうか?
- 締切済み
- オフィス系ソフト
- 完全順列(モンモール数)の2項間漸化式の組合せ論的解釈
http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97 より、 完全順列とは、整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のことであり、その総数をモンモール数という。 その総数をa[n]とすると、上記のサイトに、3項間漸化式 a[n]=(n-1)(a[n-1]+a[n-2]) の組合せ論的解釈が書かれています。 また、2項間漸化式 a[n]=n*a[n-1]+(-1)^n が成り立つのですが、普通は3項間漸化式を元に代数的に変形して示します。 しかし、これを直接に組合せ論的解釈したいのです。 いろいろ考えても、いろいろ調べてもわかりません。 興味ある方はどうか教えてください。
- 締切済み
- 数学・算数
- 組み合わせの問題について
初歩的な質問で失礼します。 「コインを5枚投げた時、2枚が表になる場合の数」が10通りになるという計算の導き出し方として、5C2=10 となる理由がよく分かりません。 組み合わせの基本的な考え方として、5つの異なる色のボールから2つを取り出す組み合わせが上記の式で算出される理由は分かるのですが・・ なぜコインを5枚投げた時、2枚が表になる場合の数の出し方が5C2となるのか、教えて頂けないでしょうか。
- ベストアンサー
- 数学・算数
- 組み合わせについて?
QNo.831096で質問したxylocaineです。いまいち理解できていない部分があるので教えて下さい。 質問内容は 9つの数字から4つの数字の組み合わせと9つの数字から5つの数字の組み合わせの数は同じでしょうか? (1,2,3,4)と(4,3,2,1)は使われている数字が同じなので1つと数えます。 数式では 9C5=126 9C4=126 これであっているのでしょうか? なぜ同じになるのでしょうか? でした。 新たな疑問(1)は126で同じになったのは偶然でしょうか? 例えば10C4と10C5は同じ数の組み合わせになるとか、何か同じになる法則があるのでしょうか? 新たな疑問(2)は9C4=126の組み合わせは全て9C5=126の組み合わせに含まれるのでしょうか? 例えば(1,2,3,4)は(1,2,3,4,5)に含まれますよね? 例えば(6,7,8,9)は(5,6,7,8,9)に含まれますよね? このように全て9C4=126の組み合わせは全て9C5=126の組み合わせに含まれるのでしょうか? 解かりやすく噛み砕いて説明していただけると嬉しいです。 宜しくお願いします!
- ベストアンサー
- 数学・算数
お礼
大変,貴重なご意見,ありがとうございました. 絵なども参考になりました. "数式化されている組合せの算出"についての記述がありませんので,これ以外には,やはり無いらしいという思いが強くなりました.