非減少列の数

この前のCode Jamの問題で、非減少列の数って意外と少ないんだなと思ったので、どれくらいあるのか調べてみた。

せっかくなので、問題を設定して解いてみることにする。

{0,1,...,9}からなる長さNの列Aのうち、A_i <= A_i+1となるものの個数を求めよ。

まあ普通に考えると、DPだよね。

import java.util.Scanner;

public class Main {
 Scanner sc = new Scanner(System.in);
 
 public static void main(String[] args) {
  new Main().solve();
 }
 
 public void solve() {
  int N = sc.nextInt();
  
  long[][] dp = new long[N+1][10];
  dp[0][0] = 1;
  
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < 10; j++)
    for (int k = j; k < 10; k++)
     dp[i+1][k] += dp[i][j];
  }
  
  long ret = 0;
  for (int i = 0; i < 10; i++)
   ret += dp[N][i];
  
  System.out.println(ret);
  
 }
}

しかしよくよく考えると、組み合わせ論を使って解けるな。ということで以下の式を導き出した。

これを実装すると、以下のようになる。（多倍長整数が面倒いのでPythonで。）

def fact(x):
    if x < 2:
        return 1
    return x * fact(x-1)

def comb(x, y):
    return fact(x) / fact(x-y) / fact(y)

def homog(x, y):
    return comb(x+y-1, y)

def solve(n):
    return sum ([comb(10, x) * homog(x, n - x) for x in range(1, min(10, n)+1)])

if __name__ == "__main__":
    n = int(raw_input())
    print solve(n)

DP解を使って検算したので、多分導いた式は正しいと思う。（追記: いや何やってんだ。これ。₁₀H_nでおしまいじゃん！）

で、以下が長さNの非減少列の個数。非減少じゃないものも合わせた列の個数は10^Nだけど、それに比べるとずっと小さい数におさまっている。

N	個数
5	2002
10	92378
15	1307504
20	10015005
25	52451256
30	211915132

うーん、なんか感覚的にすっきりしないな。
今見ている要素より上にいく確率を1/2、下にいく確率を1/2とすると、ずっと上に行きつづける確率は(1/2)^Nで、これだとパターン数がおよそ5^Nだけど、実際はこれよりもっと小さい。
いや違う、上に行きつづけるからどんどん数字が大きくなってきて最終的には、上に行く確率が(1/10)に近づくわけか。そう考えると納得できる気がする。