• ベストアンサー
  • 暇なときにでも

組合せの全体を算出できる数式は存在しますか?(2)

  • 質問No.9582918
  • 閲覧数203
  • ありがとう数3
  • 気になる数0
  • 回答数2
  • コメント数1

お礼率 96% (176/182)

前回の質問に回答がありませんので,質問の主旨を変えて再度,質問します.

質問:前回の「組合せ網羅漸化式」以外に数式が無いことについて,なぜ無いのか,ご回答者諸氏方々のご意見・お考えをお聞かせ下さい.どの様な内容のご意見でもかまいません.遠慮無くご投稿下さい.

★ 前回の質問: https://okwave.jp/qa/q9579208.html

以下に「組合せ網羅漸化式」の画像を貼り付けておきます.

質問者が選んだベストアンサー

  • 回答No.2
  • ベストアンサー

ベストアンサー率 63% (52/82)

ですから、例えば後半で書いたような考え方で別の漸化式を作れるでしょ?といっている。その逆順でも別の漸化式を作れるので、そういう意味ではいくらでも作れる。で、別にそれを論文に投稿しようとは多分思わないでしょう。なぜなら皆「それはそうだよね」という内容だから。
お礼コメント
Knotopolog

お礼率 96% (176/182)

再度の,ご回答,ありがとうございます.

全組合せを算出する数式が比較的簡単に作れるだろうという感覚は以前から持っていましたが,では,何故,書籍や辞書などに作られた計算式が載っていないのかが不思議だったので,「組合せ網羅漸化式」なる計算式を作って"researchmap"へ公開したのです.

そして,もしや,世界のどこかに,全組合せを算出できる数式があるかも知れないと思って,OKWaveへ質問してみたのですが,
どうやら,作れるけれども,まとまった形の計算式は作られていないらしい,という事が分かってきました.
投稿日時:2019/02/01 15:22

その他の回答 (全1件)

  • 回答No.1

ベストアンサー率 63% (52/82)

何というか、つまり論文で書いているのは、要はこういう事です。

つまり、{1,2,...,n}の中からr個を選んだものの一つを、b = {b(1), b(2), ..., b(s), ..., b(r)} (1≦s≦r , b(1) < b(2) < ... < b(r))と書いた時、b(s+1)の取り得る値としては、b(s)が分かっている時、 b(s)+1≦ b(s+1)≦ n-(r-s-1) (★)の全ての可能性がある。また、b(1)の取り得る値は、1≦b(1)≦ n - (r - 1)である。
従って、{b(1)}については、1≦b(1)≦ n - ( r - 1)の間で全て書いておいて、 {b(1), b(2), .... , b(s)}とs番目までの要素のものを全て書き出した時、s+1番目のものは b(s)の値を見て、(★)の範囲で全部下記出せば、{b(1), b(2), .... , b(s), b(s+1)}とs+1番目までの要素は全て書き出せる。これをr番目まで繰り返せば良い。

... とまあそれはそうだよね、といった内容で、それを「漸化式」と呼ぶか、「アルゴリズム」と呼ぶかはなんか微妙なところです、というかアルゴリズムですよね。

別の考え方としては、b = {b(1), b(2), ..., b(s), ..., b(r)}の「次」のもの c={c(1), c(2), .... , c(r)}を出すアルゴリズムを考える。bからcを産出するアルゴリズムを「漸化式」っぽく c = f(b) みたいに書けば、そちらの方がより「漸化式」っぽい。
で、そのアルゴリズムは、例えば次のようになる。つまり、 {b(1), b(2), ..., b(s), ..., b(r)}の次のものは、
* {b(1)+1, b(1)+2, b(1)+3, ... , b(1)+r}
* {b(1), b(2)+1, b(2)+2, ..., b(2)+ (r-1)}
* {b(1), b(2), b(3)+1, b(3)+2, ... , b(3) + (r-2)}
* {b(1), b(2), b(3), b(4), b(4)+1, b(4)+2, ... , b(4)+(r-3)}
....
....
* {b(1), b(2), b(3), ... , b(r-1), b(r)+1}
のどれかなのだから、上の中から {}の中の数字がnを越えてないものを選んで、その中から(辞書順で)最も小さいものを取ってくれば、それが b={b(1), b(2), ..., b(s), ..., b(r)}の次のものとなる。で、「{}の中の数字がnを越えてないか判定する」とか、「残ったものの中から(辞書順で)最も小さいものを取ってくる」とかは、(閉じた代数計算式というものの範囲が不明だが、)漸化式っぽく書ける。
補足コメント
Knotopolog

お礼率 96% (176/182)

■前質問が無回答削除になるため,前質問をここへ書き込みます■
タイトル:「組合せの全体を算出できる数式は存在しますか?」
最近(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種類ような組合せも数式を用いて算出する方法が記述されています.
この様な例のほか,全ての組み合せについて,ひとつの組合せ網羅漸化式を用いて組合せの全体が算出できます.
下記の数式以外で,これと同等の考え方・目的・主旨をもって創られている数式が存在すれば,それを教えて下さい.
コンピューターを用いる数値計算で組合せを構成する方法は除きます.閉じた代数計算式の存在を問います.

数式TeX (1):
\begin{align*}
\text{{\footnotesize (組合せの表示)}}. \mkern7mu
\langle \mkern3mu b_1, {}&{} b_2, \ldots, b_k, \ldots, b_r \mkern3mu \rangle,\\[1ex]
b_k & = b_{k-1} + t_{k-1},\\
t_{k-1} & = 1, \; 2, \; \ldots \ldots \: ,\; n-r+k-b_{k-1},\\
k & = 1, \; 2, \; \ldots \ldots \: ,\; r.\\
b_0 & = 0. \; \text{(定義)}.
\end{align*}

数式TeX (2):
(組合せの表示)

$\langle \mkern3mu b_1, {}&{} b_2, \ldots, b_k, \ldots, b_r \mkern3mu \rangle$,\\
$b_k = b_{k-1} + t_{k-1}$,\\
$t_{k-1} = 1, \; 2, \; \ldots \ldots \: ,\; n-r+k-b_{k-1}$,\\
$k = 1, \; 2, \; \ldots \ldots \: ,\; r$.\\
$b_0 = 0. \; \text{(定義)}$.
投稿日時:2019/02/03 10:46
お礼コメント
Knotopolog

お礼率 96% (176/182)

回答を頂きまして,ありがとうございます.

しかし,残念ながら回答にはなっておりません.
論文の解説を頼んでいるのではなく,
論文と同じ目的で短く簡潔に書かれた数式が,世界のどこかに存在するかどうかを問うています.
投稿日時:2019/02/01 06:29
結果を報告する
    • 2019/05/04 16:04
    • コメントNo.1

    質問は解決しました. なお,下記のURLで,タイトル: 「繰り返しを許さない組合せの各組を全て算出できる数式」 の論文のPDFファイル(224KB,A4判,42ページ)をダウンロー ...続きを読む

AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,600万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A

その他の関連するQ&Aをキーワードで探す

ピックアップ

ページ先頭へ