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

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

  • 質問No.9584847
  • 閲覧数163
  • ありがとう数4
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 96% (176/182)

★★ 以下の内容をカテゴリ「数学・算数」へ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種類ような組合せも数式を用いて算出する方法が記述されています.
この様な例のほか,全ての組み合せについて,ひとつの組合せ網羅漸化式を用いて組合せの全体が算出できます.

下記の数式以外で,これと同等の考え方・目的・主旨をもって創られている数式が存在すれば,それを教えて下さい.
コンピューターを用いる数値計算で組合せを構成する方法は除きます.閉じた代数計算式の存在を問います.

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

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

ベストアンサー率 50% (10/20)

自分だったら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回で重複して行うことになってしまいますが、組み立て途中の組み合わせを管理する必要がなくなります。これこそ小学生でもできる確実な計算方法です。

これまでの結果から列挙するのがだめということではありません(抜き出す操作の結果に興味深い性質が見つかったりするかもしれないし)が、それをするならするで組み立て途中の組み合わせにきちんと名前をつけてどう並べるかも定義する必要があります。それをしなかったからやたらと注意力が必要な計算になってしまったのではないでしょうか。

というわけでその数式は世界中のプログラマーが自力で導ける自明なものであり、問題の大部分はその数式の外側にあります。
お礼コメント
Knotopolog

お礼率 96% (176/182)

大変,貴重なご意見,ありがとうございました.
絵なども参考になりました.
"数式化されている組合せの算出"についての記述がありませんので,これ以外には,やはり無いらしいという思いが強くなりました.
投稿日時:2019/02/22 04:27

その他の回答 (全1件)

  • 回答No.2

ベストアンサー率 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個)となります。

以上の定義を再帰的に適用することにより、すべての組み合わせを算出することができます。

これももちろん既知のアルゴリズムです。どこかの参考書には書いてありそうなレベルの内容です。
お礼コメント
Knotopolog

お礼率 96% (176/182)

再投稿,ありがとうございます.
質問者さんに数式を作れと頼んではいません.世界のどこかに数式が存在するのかどうかを問うているだけです.
質問者さんは「代数的」という言葉に拘っていますが,これは単に,閉じた或る数式f(n,r,k)=0を意味しているだけです.
投稿日時:2019/02/23 06:35
結果を報告する
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。
AIエージェント「あい」

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

関連するQ&A

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

ピックアップ

ページ先頭へ