「繰り返しのない組合せ」の各組を数式の計算で出した

質問

組合せ（繰り返しのない）の要素を
　　1，2，3，4，5，6，7，8，9
とします．この 9個から 7個を取り出した 36通りの組み合せを，全て書き出したいのですが，計算式を教えて下さい．
（補集合を使う計算の方法がありますが，そうではなく，正式な計算式を知りたい）

数冊の数学辞典やウィキペディアなどを調べましたが，計算式が載っていません．
パソコンを用いた数値計算が苦手ですので，計算式を教えて頂きたいのです．

また，13個から 10個を取り出した 286通りの組み合せも計算式でゆっくりと計算したいです．
よろしくお願いします．

回答No.4

f272 · ベストアンサー

(1)
> これを代数的な数式に置き換えるのは，かなり困難であると思われますが，如何でしょうか？
かなり困難であることはそのとおりでしょう。ちょっと考えてもどうすればよいのかよくわからないし...
でも，まあ，殆どの人はあなたの言うような代数的な数式には興味がないのです。興味があるのは計算できるかどうかです。
(2)
関数F(n,k,m)の定義があいまいというのは，単に明確に述べていなかっただけです。m番目というのはすべての組み合わせを辞書式に並べたときのm番目ということです。つまり1番目の数値が小さいほど前にくる。1番目の数値が同じ場合は２番めの数値が小さいほど前に来る。2番めの...以下同じです。すべての数値が同じものはないので必ず順序は決まります。
なお#3で言った式はm番目を直接に出すときに使うべき式であって，順番にすべての組み合わせを作るときには別のやり方をするほうが効率的です。
つまり1からnまでの整数からk個を取り出して出来る組み合わせを作るときは
1番めは{1,2,3,...,k}です。
次の組み合わせは，今できている組み合わせの数値を後ろから見ていきます。後ろからj番目の数値がn-j+1でないものが見つかったら，それが何番目の数値かを記憶します。それが前からi番目であれば，1番目からi-1番目まではそのままにして，i番目の数値は1を加えます。そしてi+1番目からk番目の数値はi番目の数値に順に1を加えたものにします。このようにして次の組み合わせを作ります。これを繰り返してnCk個の組み合わせを作ればよいのです。
{1,2,3}，次は3を4にする。
{1,2,4}，次は4を5にする。
{1,2,5}，次は2,5を3,4にする。
{1,3,4}，次は4を5にする。
{1,3,5}，次は3,5を4,5にする。
{1,4,5}，次は1,4,5を2,3,4にする。
{2,3,4}，次は4を5にする。
{2,3,5}，次は3,5を4,5にする。
{2,4,5}，次は2,4,5を3,4,5にする。
{3,4,5}，おしまい
これも代数的な数式に置き換えるのは困難でしょうね。

お礼

再度にわたるご親切なご回答，誠に，ありがとうございます.

（１）
＞殆どの人はあなたの言うような代数的な数式には興味がない・・・
なるほど，まさに，その通りでしょう．回答者さんの仰る通りです．
過去に誰も代数的な数式を作らなかったのですから・・・．
計算できれば，それで終わり！　と言うことでしょう．
組合せを計算する代数的な数式は，簡単そうなのに，なぜ無いのかが不思議なのです．
難しかった，四色問題，フェルマーの最終定理，ポアンカレ予想などか解かれているのに・・・．
（２）疑問が解消しました．
関数F(n,k,m)の定義が明確に，かつ，完璧になされたため，これで関数F(n,k,m)の計算ができます，
＞これも代数的な数式に置き換えるのは困難でしょうね。
このお言葉が印象的に聞こえます．

色々と，ご指導いただきまして，本当に，ありがとうございました．

回答No.3

f272

#1 & #2です。
まずC関数を定義します。まあ，組み合わせ数と同じですが...
C(n,k)=nCk ただしn<kのときは0
次にV関数を定義します。
V(a,b,x)=(v<a and C(v,b)≦x)を満たす最大の整数v
最後にE関数を定義します。これは要素数がk個の集合が関数の値となっていて，漸化式で定義することにします。また補助的にxを使います。
E(n,k,m)={e[i]}, i=1,2,...,k
x[1]=C(n,k)-m
e[1]=n-V(n,k,x[1])
x[i]=x[i-1]-C(n-e[i-1],k-i+2), i=2,3,...,k
e[i]=n-V(n-e[i-1],k-i+1,x[i]), i=2,3,...,k
これで定義されるE関数が#2で言った関数Fになります。

お礼

何度もご回答を，ありがとうございました．
ご提示いただいた数式について，感想を述べます．

（１）最大の整数 v を求める関数V(a,b,x)は数値解析的な手法で解を求めるため，目的の代数的な数式ではないので，計算全体が組合せを算出する，目的の数式とはなっていない．
n,k が大きな数になれば，結局，v を求めるために，コンピューターによる数値解析としての計算を行うこととなってしまう．

（２）m番目にくる組合せを出力する関数F(n,k,m)の定義があいまいであるため，C(n,k)個存在する組合せのどの位置にくるのか，明確な計算ができない．
1,2,...,n および k の数と関連づけて，m番目を決定するための明確な定義が必要がある．

ご提示いただいた数式を用いて，実際の計算例として，n=5, k=3 の場合を以下のように計算しましたが，うまくいっていません．

i=1, e[1]=5-V(5,3,10-m), m=1,2,...,10.　　（C(5,3)=10）

i=2, e[2]=5-V{V(5,3,10-m),2,10-m-C(V(5,3,10-m),3)}.

i=3, e[3]=（複雑なため省略）.

E(5,3,m)={e[1],e[2],e[3]}.

関数V(a,b,x)，および F(n,k,m)について，これを代数的な数式に置き換えるのは，かなり困難であると思われますが，如何でしょうか？

補足

ご回答，ありがとうございます.
詳しく数式を書いていただき，ありがとうございます.
今，直ぐには飲み込めませんので，少し検討してみます．

回答No.2

f272

あなたの考えていることがわかってきた。あなたの考えるような計算式は作ることが出来ますが，例えばn個からk個を取り出した組み合わせ(全部でnCk個ある)を辞書式に並べたときにm番目にくる組み合わせを出力する関数をF(n,k,m)としましょう(かなり複雑な式になりますが...)。このFは組み合わせを文字列として出力するとします。例えば
F(5,3,5)="1 3 5"です。
ちなみに全部書けば"1 2 3”，"1 2 4"，"1 2 5"，"1 3 4"，"1 3 5"，"1 4 5"，"2 3 4"，"2 3 5"，"2 4 5"，"3 4 5"ですね。
この関数を使って「全組み合せを計算で算出する」とすれば
F(5,3,1)を計算して，F(5,3,2)を計算して，...，F(5,3,9)を計算して，F(5,3,10)を計算することになります。でもこのFの計算はほとんど同じような計算を行うことになって違いはわずかなのです。そんな無駄なことをする気ですか？
無駄を省いて「全組み合せを計算で算出する」とするときはこんな関数は使わずに，全部を出力するような計算をするでしょう。そういう計算は普通は計算式とは言いません。計算アルゴリズムあるいは計算手順などと呼びます。

補足

ご回答，ありがとうございます.

回答者さんは“あなたの考えるような計算式は作ることは出来ますが，・・・”と書かれています．
と言うことは，過去に完成されて，永い間，既に使われているような計算式は，やはり無い．と私は解釈しました．
もし，計算式が存在するのであれば，数学辞典などには載っているはずですから．
結局，計算アルゴリズムや計算手順としてはあるが，計算式としては整えられていない，と言うことなのでしょう．

回答者さんの言われる関数F(n,k,m)が多項式や三角関数，指数関数，超越関数，複素数関数など，何れかの関数を用いて表現されているのであれば，話はそこで終わりです．

また，「・・・こんな関数は使わずに，全部を出力するような計算をするでしょう。・・・」と書かれている，この「全部を出力するような計算」とは，多分，コンピュータによる数値計算だろう思いますが，実用的には，常識的に考えても，それでいいのです．

ここで問題にしているのは，純粋数学的に考えて「全部を出力するような計算」が数式化されていない，という事です.
計算が早いか遅いか，長ったらしい計算かどうか，無駄な計算かどうか，などは問題にしていません．
また，計算アルゴリズムか，計算手順か，計算式か，などの呼び方も問題にしていません．

ここで，回答者さんに，もう一つの問いかけをしますが，過去に「全部を出力するような計算」を数式化するような試みがなされた事はあるのでしょうか，それとも，無いのでしょうか．

よろしくお願いします.

回答No.1

f272

計算式ってどういうものをイメージしていますか？
普通なら9C7を計算して36という値を求めるように，計算式からは一つの値が出てくるのであって組み合せが得られるわけではありません。
36通りの組み合せを出力するような手順はありますが，それは計算式と言われるようなものではありません。

補足

ご回答，ありがとうございます.
要するに，当回答者さんの結論としては，
「繰り返しの無い組み合わせの各組を全て算出する事が出来る数式」
は無い．と言うことであると解釈します．

計算式のイメージとしては，たとえば，組合せの要素を，
a, b, c, d, e, f, g, h, i とします．
また，F, G, H, J, K, L, M, N　を或る関数としますと，例えば，

b＝F(a), c＝G(b), d＝H(c), e＝J(d), f＝K(e), g＝L(f), h＝M(g), i＝N(h)

と言ったような数式です．これは仮の話ですから，上記のような数式になるかどうかは分かりません．

回答者さんの言われる 9C7＝36 は，組合せの個数ですから，これとは別問題です.
この 36通りの全組み合せを計算で算出する事を考えています．