プロジェクトオイラー 問１１３

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１３「非はずみ数」
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 10¹⁰未満では277032個しかない.
googol数 (10¹⁰⁰) 未満ではずみ数でないものの数を答えよ.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def g(n):
	if n<2: return 1
	else: return n*g(n-1)

def C(n, m): return g(n)//g(m)//g(n-m)

def H(n, m): return C(n+m-1, m)

def f(n):
	c = H(10, n)-H(10, 0)
	for i in xrange(1, n+1): c += H(10,i)
	c -= 10*n
	return c

n=100
s = f(n)
print s

与えられた数が大きすぎるので桁数ごとに個数を計算して合計することにします。

まず増加数です。
これは0から9までの数字10種類からi個を選ぶ重複組合せです。
重複組合せの個数は公式から以下の通りです。
　₁₀H_i  ...(A)

図にすると、i桁の数字が以下のように表せます。「｜」は仕切り棒です。
連続する0｜連続する1|・・・｜連続する9
つまり、i個の要素を連続する0から連続する9までの10個の部分に分けることと同じです。
重複組合せでは、仕切り棒の本数も含めた格納場所に仕切り棒を入れることを考えます
10個の部分に分けるので必要な仕切り棒は10-1で9本必要です。
つまり、i+9個の格納場所に9本の仕切り棒を格納し、仕切り棒の間には連続する数字を格納することと同じです。
なお仕切り棒が隣合う場合、その間の連続する数字は１つも無いことになります。
重複組合せの個数の式と、重複を許さない組合せの個数の式との関係は以下の通りです。
　_nH_m = _n+m-1C_m  ...(B)
m-1は、仕切り棒の本数です。

それから、最上位が0の場合、桁数がiではなくなってしまいますが、
その個数は最上位1桁だけ0固定で他のi-1桁分は重複組合せなので、
　₁₀H_i-1
この分を差し引くと
　₁₀H_i - ₁₀H_i-1
これを全桁分、つまり桁数iを1からnまで動かして和をとると、
ほとんどの項が打ち消しあって以下だけが残ります。
　₁₀H_n - ₁₀H₀  ...(C)

次に減少数です。
減少数と同じように図にすると、i桁の数字が以下のように表せます。
連続する9｜連続する8|・・・｜連続する0
この重複組合せの個数は上記(A)と同じです。

さらに、増加数と減少数で重複して数えている分を差し引きます。
増加数でも減少数でもカウントしている値は、全桁同じ数字の場合なので、
各桁数ごとに10個あり、n桁以下の範囲では、
10*n  ...(D)
です。

１．g(n)
・階乗n!を返します。
・問２０のものを流用しました。


２．関数C(n, m)
・n個の中からm個を選ぶ組合せの個数を返します。
・公式から、n!/（m!・(n-m)!）　です。

３．関数H(n, m)
・n個の中からm個を選ぶ重複組合せの個数を返します。
・上記(B)をそのまま実装しました。

４．関数f(n)
・10ⁿ未満、つまりn桁以下で、はずみ数以外の数の個数を返します。

・c = H(10, n)-H(10, 0)
　増加数の個数です。上記(C)をそのまま実装しました。

・for i in xrange(1, n+1): c += H(10,i)
　減少数の個数です。
　n桁の減少数である上記(A)をそのまま実装し、1桁からn桁の分の和を計算しました。

・c -= 10*n
　増加数と減少数の重複分を差し引きます。
　上記(D)をそのまま実装しました。




解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
51161058134250