nCr 組合せ数字からの順位の逆算

質問

１～１００までの３つの数字の組合せでは、

１番目　　１、２、３
２番目　　１、２、４
　　・
　　・
　　・
１６１７００番目　９８，９９，１００

となりますが、任意の３つの組合せ数字が何番目なのかを求める方法はあるのでしょうか？

このケースでは、２、３、４の組合せは４９５１番目になる。というような事です。
これは単純に 100C2 + 1 で計算しました。

このようにｎとｒの数値を変えて加算していけばできそうな気もするのですが繰り返し計算が多すぎて混乱しています。
もっとシンプルな方法はないのでしょうか？

回答No.2

dame_dame_ · ベストアンサー

何かうまいやり方がありそうな気もしますが…

素直にやれば
一番小さい数がiであるのは他の2数を考えて
(100-i)C2通り
一番小さい数がiで二番目がjであるのは
(100-j)C1通り

(k,l,m)(k<l<m)の前に来るのは
(一番目がk未満のもの)
+(一番目がkで二番目がl未満のもの)
+(一番目がkで二番目がlで三番目がm未満のもの)
=Σ[i=1,k-1](100-i)C2+Σ[j=k+1,l-1](100-j)C1+(m-l-1)

（※k=1のときは最初のΣを0、l=k+1のときは二項目のΣを0とする)

展開整理することは可能ですが簡単にはならないと思います
（最初の例は99C2+1かと）

お礼

お礼が遅くなり申し訳ありません。

そうですね、99C2 + 1 でした・・・イメージでは分かっていたのですが相当混乱していたようです。

素直に考える・・・その通りですね。プログラムに組み込むとき少しでもシンプルにと考えすぎていたようです。
10万～600万件ほどの全データを質問内容の通りに（実際は7個の数字）瞬時に処理する事が必要なソフトなので繰り返し計算を避けようとして雑念があったようです。

頂いた回答は私が描いていたイメージそのものです。
数式として形にして頂いたおかげでソフトに組み込む事ができました。

処理速度はプログラムの工夫で何とかなりそうです。
ありがとうございました。

回答No.1

alice_44

辞書式に並べると、先頭が 2 の三つ組は、
先頭が 1 の三つ組が並んだ後に来る。
先頭が 1 の三つ組の総数は、99C2。

先頭が 2 の三つ組の中で、二番目が 3 のものは、
二番目が 1 のものの後に来る。
先頭が 2 で二番目が 1 のものの総数は、98C1。

先頭が 2 で二番目が 3 のものの中で、
234 は 231 の次で 2 個目に並ぶ。

よって、234 は全体の 99×98/2 + 98 + 2 個目。

このように、三つ組の中で
各数の左に、それより小さい数が何個あるか
を考えて計算する必要がある。

お礼

お礼が遅くなり申し訳ありません。

私が 100C2 + 1 などと書いた為、誤解させてしまったようです。すみません。

>各数の左に、それより小さい数が何個あるか
>を考えて計算する必要がある。

順列のケースも必要な為、このアドバイスは非常に助かりました。

alice_44さんとdame_dame_さんの回答だけですべてが解決しました。
ありがとうございました。