Pythonで各桁が厳密に増加するn桁の整数の個数を求めるプログラム

整数 n が与えられたとき、各位の数字が左から右へ厳密に増加している（隣り合う桁が必ず大きくなっている）n 桁の正の整数が何個存在するかを求めます。

たとえば入力が n = 3 の場合、出力は 84 となります。該当するのは 123、124、125、…、678、789 のような数です。

解き方のポイント

この問題は、組み合わせ（コンビネーション）の考え方を使うと非常にシンプルに解けます。

使用できる数字は 1〜9 の 9 種類です。この中から n 個の異なる数字を選ぶと、それらを昇順に並べる方法はちょうど 1 通りしかありません。つまり、「厳密に増加する n 桁の整数」の個数は、「9 個の数字から n 個を選ぶ組み合わせの総数」と一致します。

したがって、答えは次の式で求められます。

C(9, n) = 9! ÷ (n! × (9 − n)!)

なお、n が 9 より大きい場合は、1〜9 の 9 種類の数字だけでは n 桁の数を作れないため、答えは 0 になります。

アルゴリズムの手順

• n が 9 以下の場合：組み合わせ 9Cn を計算して返す

• n が 9 より大きい場合：0 を返す

それでは、実際の実装を見てみましょう。

実装例

from math import factorial as f

class Solution:
    def solve(self, n):
        if n <= 9:
            return f(9) // f(n) // f(9 - n)
        else:
            return 0

ob = Solution()
print(ob.solve(3))

入力

3

出力

84

計算量について

処理の中心は小さな数（最大 9）の階乗計算のみのため、時間計算量・空間計算量ともに実質 O(1) で済みます。n の値にかかわらず常に高速に動作するのがこの手法の大きな利点です。