面白い問題おしえて〜な 30問目

>>94
行列の添字はZ/nZでとるとして行列Aと列ベクトルvを
Aij = 1 if j=i,i+1,i-1
. =0 otherwise
vi = 1 if i=0
. =0 otherwise
で定める。
この時求める場合の数は
v^A^kv 、
ただしv^はvの転置ベクトル。
ζ=exp(2πi/n)とおけば、計算して
v^A^kv =(1/n)Σ[t](1+ζ^t+1/ζ^t)^k