２つの漸化式風の関数が同じあることの証明

質問

ある順列を2通りの方法で求めていて思いついた質問です。
n≧kなる自然数n,kに対して２つの関数f(n,k)とg(n,k)を定義します。
なお、下の定義式のCとPは高校数学で習う順列のことです。つまり、a≧b≧0なる整数a,bに対してC(a,b)＝a!/(b!・(a-b!)) で P(a,b)=a!/(a-b)!です。

k=1のとき　f(n,k)=1
ｋ≧２のとき　f(n,k)＝Σ(i=0to(n-k))｛C(n-1,i)・A(n-1-i,k-1)｝

k=1のとき　g(n,k)=1
ｋ≧２のとき　g(n,k)＝((k^n)-Σ(i=1tok-1){P(k,i)・A(n,i)})/k!

このとき、f=gを証明するにはどうすればいいでしょうか。

例えば、k=2のときはf(n,2)＝Σ(i=0to(n-2))｛C(n-1,i)・1｝
　　　　　　　　 ＝Σ(i=0to(n-1))｛C(n-1,i)｝-C(n-1,n-1)
＝2^(n-1)-1
g(n,2)＝{2^n-P(2,1)・1}/2!
　　　　　　　　　＝2^(n-1)-1　　　　
で等しくなりますが、k≧3の場合にどうやればいいのか、わかりません。

kに関する帰納法でない解法でも結構です。

回答No.4

zhidao

＞x桁のx進数x^x個のうち、"0からn-1までのn種類の数字が全て
＞出現しているものの個数"を数えるために、漸化式を考えていました。

漸化式で考えてももちろんいいですが、この問題には様々な
解法があります。
例えば、「包含と排除の原理」を使えば直ちに答えを出す
ことが可能です。
x桁のx進数x^x個のうち、0からn-1までのn種類の数字が全て
出現しているものの個数を F(x,n) とすると、
F(x,n)=Σ(i=0 to n){C(n,i)*((-1)^i)*(x-i)^x}
となります。

回答No.3

dfhsds

Binomial Transform
http://mathworld.wolfram.com/BinomialTransform.html
ににていますが、この問題の出典はなんですか？

補足

x桁のx進数x^x個のうち、"0からn-1までのn種類の数字が全て出現しているものの個数"を数えるために、漸化式を考えていました。
２つめに思いついた漸化式(gのほう)からは、binomial transform型の答えが出てきましたが、fからの計算はよくわかりません。
求めている個数は、binomial transformでa_k=k^xとしたものでよろしいのでしょうか。

回答No.2

Kules

普通に帰納法ではできませんか？
ｋ＝ｓの時成り立つと仮定
ｋ＝ｓ＋１の時
f(n,s+1)=f(n,k)+C(n-1,n-s+1)・A(n-1-(n-s+1),s)
を具体的に計算。ｇに関しても同じことをして、
f(n,s)=g(n,s)を使えば証明できると思います。
ただ、No.1の人の指摘にもあるとおりAが何なのかわからないので、
本当にできるかどうかは断言できません。

お礼

fの定義式に出てくるAをfに、gの定義式に出てくるAをgに訂正します。

補足

すいません。
fの定義式に出てくるAをfに、gの定義式に出てくるAをgに訂正します。

回答No.1

dfhsds

A(n,i)の意味合いが不明

お礼

fの定義式に出てくるAをfに、gの定義式に出てくるAをgに訂正します

補足

すいません。
fの定義式に出てくるAをfに、gの定義式に出てくるAをgに訂正します。