1ドルと1000円をつくる組み合わせ

質問

アメリカ通貨である1ドルをつくる組み合わせを考えた時に、
何通りできるか教えていただけないでしょうか？
硬貨の種類は、1￠（penny）、5￠（nickel）、10￠（dime）、25￠（quarter）、50￠。できれば、何がいくつ、何がいくつ．．．と表などでわかればたいへんありがたいのですが．．．。また、日本円硬貨(1円,5円,10円,50円,100円,500円）で1000円をつくる組み合わせについてもお願いします。これら以外にも限定がある組み合わせに使える計算式やフリーソフトのようなものがあれば教えてください。macユーザーも使えるようなものがあれば最高なのですが．．．数学に強くない典型的な文系人間なので、できるだけわかりやすくお願いします。

回答No.1

stomachman

コインの組み合わせ方を数え上げるためのアルゴリズムは簡単に構成できますけれども、それを理解して表計算ソフトのシートやプログラムに仕上げることが出来ないでしょ。
　また、「限定がある組み合わせに使える計算式」なんて都合良くはいきません。計算方法は限定の内容に強く依存するので、「どんな限定だろうとこれひとつで計算できる」というやり方は存在しません（「そんなやり方はどうやっても作れっこない」ということが数学的に示せます）。

　それはさておき、この程度の話なら手作業でこつこつ場合分けすればいいんです。ふつーにお金を使うときの感覚でやれば何でもありません。15分もあればできるでしょ。

　まずは、「50セント玉が2枚の場合」、「50セント玉が1枚の場合」、「50セント玉が0枚の場合」、と分けます。

　「50セント玉が2枚の場合」はこれでおしまいですが、残りの二つの場合についてはそれぞれ、今度は25セント玉の枚数で場合分けします。すなわち：
「50セント玉が1枚で、25セント玉が2枚の場合」、「50セント玉が1枚で、25セント玉が1枚の場合」、「50セント玉が1枚で、25セント玉が0枚の場合」。
「50セント玉が0枚で、25セント玉が4枚の場合」、「50セント玉が0枚で、25セント玉が3枚の場合」、…
という風に。

　しかしこんなの書いてらんないっすよね。
　そこで、略記法を使います。「50セント玉a枚、25セント玉b枚、10セント玉c枚、5セント玉d枚の場合」を(a,b,c,d)と書くことにするんです。（こういう書き方は「ベクトル(vector)」と呼ばれます。）
　なお、1セント玉の枚数は、他のコインの枚数が決まれば「合計が1ドルになる」という条件から直ちに決まってしまうから、場合分けの必要はありません。

この略記法で書くと、ここまでで
(2,0,0,0)
(1,2,0,0)
(1,1,?,?)
(1,0,?,?)
(0,4,0,0)
(0,3,?,?)
(0,2,?,?)
(0,1,?,?)
(0,0,?,?)
と場合分けしたことになっています。
　さらにそれぞれの場合(のうち、"?,?"が残ってるやつ）について10セント玉の枚数で場合分けします。たとえば、(1,1,?,?)をやってみると、既に合計50+25=75セントになってる訳だから、使える10セント玉は高々2枚（3枚以上だと1ドルを超えてしまう）。つまり、
(1,1,2,?)
(1,1,1,?)
(1,1,0,?)
の場合に分けられます。同様にして"?,?"の付いてるやつの場合分けが全部終わったら、いよいよ5セント玉の枚数での場合分けです。たとえば、(1,1,0,?)をやってみると、合計は50+25=75セントになってるから、使える5セント玉は高々5枚なので、
(1,1,0,5)
(1,1,0,4)
…
(1,1,0,0)
となる。たとえば(1,1,0,1)なら「50セント玉1枚、25セント玉1枚、10セント玉0枚、5セント玉1枚(従って、1セント玉20枚)」の組み合わせ、ということです。こうして、"?"が全部なくなったら一覧表の出来上がりです。

お礼

限定がある組み合わせに使える計算式」なんて都合良くはいきません。計算方法は限定の内容に強く依存するので、「どんな限定だろうとこれひとつで計算できる」というやり方は存在しません（「そんなやり方はどうやっても作れっこない」ということが数学的に示せます）。------そうですよね。
丁寧なアドバイスありがとうございました。地道にその都度考えたいと思います。