1,2,...,nをノードに持つ二分探索木が何通りできるか考える. n = 1のとき二分探索木の個数は1通り n > 1のとき 根は1,2,...,nまでありうるから 異なるn個の値をノードに持つ二分探索木の個数をf(n)通りとすると f(1) = 1 f(n) = 根が1の二分探索木の個数 + .…

Project Euler 240 {1,...,i}からn個をとった上位t個の和がsになる出方の個数をf(i,n,t,s)とする. f(12,20,10,70)の値を求めたい.まず{1}からn個とったうち上位t個の和がtになる出方は1通り, 和がそれ以外になるのは0通り.{1,...,i}からn個をとった上位t個の…

Project Euler 151 A1の紙がa1枚, A2の紙がa2枚, ..., A5の紙がa5枚あるときから始めて, 封筒に紙が1枚だけ入っている回数の期待値を として漸化式を立てて, を求める. 例えば紙の枚数がの日にA3の紙を手にとったら, 次の日の紙の枚数はになる. Project Eule…

元の質問は, a,b,c,d,e,fの6文字から重複を許してn個選び, 選んだn個をそれぞれ2倍に複製した2n個を並べる並べ方の個数を求めたいとのこと. http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12151668017例えば, n=3で最初に「aが1個とbが2個 (a,b…

を作る f(n):=genmatrix(lambda([i,j],mod(i+j-2,n)+1),n,n); ちなみに行列式は

包除原理の例題みたいな問題。先頭から続く0は無視することだけ注意すればよい。n桁の16進数xの個数は15*16^n個 f(prop) = 条件propを満たすn桁の16進数の個数 とするとf(0を含む & 1を含む & Aを含む) = 15*16^n - f(0を含まない | 1を含まない | Aを含まな…