Project Euler 113

http://projecteuler.net/index.php?section=problems&id=113

これは単なる重複組合せですね。
N桁までとすると増加数は、

₉H₁ + … + ₉H_N = ₉C₈ + … + _N-8C₈

減少数は0も使えるから数が0になる場合だけ除いて、

₁₀H₁ + … + ₁₀H_N - N = ₁₀C₉ + … _N+9C₉

あと、222などの重複を除けば答えが出ます。
少し考えると、増加数は0も使ってもよいと考えて、桁数で分けずに全てN桁で考えることが出来ます。数が0になる場合だけ除いて、

₁₀H_N - 1

となります。ということは、

₉H₁ + … + ₉H_N = ₁₀H_N - 1

だから、減少数のほうも、

₁₀H₁ + … + ₁₀H_N - N = ₁₁H_N - N - 1

となります。

def C(n, m):
    if m == 0:
        return 1
    else:
        return C(n, m - 1) * (n - m + 1) / m

def num_increasing(n):
    return C(n + 9, 9) - 1

def num_decreasing(n):
    return C(n + 10, 10) - n - 1

def num_not_bouncy(n):
    return num_increasing(n) + num_decreasing(n) - n * 9

N = 100
print num_not_bouncy(N)