数学Ａ、場合の数

質問

1が1個、2が2個、3が3個・・・9が9個の合計45個の数字の中から9個の数字を使ってできる9桁の自然数はいくつあるか。

適当に考えた問題なんですがどうやって数えればよいのかわかりません
この問題の解き方を教えてください

回答No.1

nag0720 · ベストアンサー

おもしろい問題ですね。

関数 f(n,p) を

1が1個、2が2個、3が3個・・・nがn個の数字の中からp個の数字を使ってできるp桁の自然数の数

と定義すると、問題の答えは f(9,9) ですよね。

で、この関数 f(n,p) について下記の関係が成り立つと思うのですがいかがでしょう。

f(n,p) ＝ Σf(n-1,p-i)*Ｃ(p,i) { i=0...min(n,p) } (Ｃはコンビネーション関数)

f(4,4) を考えると、

f(4,4) ＝ f(3,4)*1 + f(3,3)*4 + f(3,2)*6 + f(3,1)*4 + f(3,0)*1

f(n,0)=1 , f(n,1)=n であることや
f(2,4)=0 , f(2,3)=3 , f(2,2)=3 などから

f(3,4) ＝ f(2,4)*1 + f(2,3)*4 + f(2,2)*6 + f(2,1)*4 ＝ 38
f(3,3) ＝ f(2,3)*1 + f(2,2)*3 + f(2,1)*3 + f(2,0)*1 ＝ 19
f(3,2) ＝ f(2,2)*1 + f(2,1)*2 + f(2,0)*1 ＝ 8

したがって、

f(4,4) ＝ 38 + 19*4 + 8*6 + 3*4 + 1 ＝ 175

これは実際に書き出してみて合っているようでした。

再帰関数でプログラミングすれば f(9,9) も計算できるとは思うけどそれはまたの機会に。

上記の f(n,p) の式が本当に合っているかどうか誰か検証（証明）しれくれませんか。

お礼

とんでもない数字になって申し訳ないのですが
お二方とも答えが一致したのできっと正解なんでしょうね

わかりやすい回答ありがとうございました！

回答No.3

20080715

＞適当に考えた問題なんですがどうやって数えればよいのか
＞わかりません
＞この問題の解き方を教えてください

計算機を使って解けばよいのです。
求める場合の数は、xの多項式
9!*(1+x)*(1+x+x^2/2!)*(1+x+x^2/2!+x^3/3!)*…*(1+x+x^2/2!+…+x^9/9!)
の展開式におけるx^9の係数になります。
計算ソフトを利用してx^9の係数をもとめてしまえばよいのです。

以下はフリーソフト Risa/Asir にこの計算をさせたときの
入力と出力の結果です。
この結果を見ると、258068893通りあることがわかります。

[0] for(A=fac(9),J=1;J<=9;J++){for(B=0,K=0;K<=J;K++){B+=x^K/fac(K);}A*=B;}coef(A,9,x);
[1] 258068893

お礼

>求める場合の数は、xの多項式
>9!*(1+x)*(1+x+x^2/2!)*(1+x+x^2/2!+x^3/3!)*…*(1+x+x^2/2!+…+x^9/9!)
>の展開式におけるx^9の係数になります。
ここのところをもっと詳しく解説してもらいたかったです
回答ありがとうございました

回答No.2

nag0720

＃１です。

＃１で定義した関数をプログラミングして f(9,9) を求めてみたら

f(9,9) ＝ 258,068,893

になりました。合っているのかな？