Project Euler 158

プロジェクトオイラー
http://projecteuler.net/index.php

Q158.
26個のアルファベットから違う文字n個を持ってきて並べる。そのとき"bacdef"のように辞書順に並んでいない部分が1箇所だけの文字列の数をp(n)とする。最大のp(n)。

アルファベットは分かりにくいので以下では1〜nの数字で考える。
N個からn個を選ぶのは、_NC_nだから、選んだ後を考えればよい。
順序が逆になるのが1回だから、そのときの数字でまとめる。それが1なら、1の左に1個以上の数字がある。n-1個の各数字が左右のどちらかに配置されるかが決まれば並びが決まるから、全部左に配置される場合を除いて、2^n-1-1となる。逆順になるのが3なら、4以上の並びを同様に考えればよいから、2^n-3-1となる。全てを足し合わせると、

2^n-1-1 + ... + 2¹-1 = 2ⁿ - n - 1

実際には、ややこしい再帰を使ったプログラムを動かして答えを出してから、これを思いついた。

def C(n, m):

    return reduce(lambda f, i: f * (n - i + 1) / i, range(1, m + 1), 1)
def f(n):

    return 2 ** n - n - 1
def p(n):

    return f(n) * C(N, n)
N = 26

print reduce(max, map(p, range(N + 1)))