ネットワークの経路問題

質問

図にある問題が解けません。簡単な数学の問題のような気がするのですが・・・
よろしくお願いします。

回答No.1

f272

1列目のノードのノード間距離は
a[n]=(1+2+3+4)+(1+2+3)+(1+2)+(1)
=n(n+1)(n-1)/6
です。1列目から5列目までを考えるとこれをn倍します。
1列目と2列目のノード(隣の列)のノード間距離は
(1+2+3+4+5)+(2+1+2+3+4)+(3+2+1+2+3)+(4+3+2+1+2)+(5+4+3+2+1)
=a[n]*2+n^2
です。1列目から5列目までを考えるとこれを(n-1)倍します。
1列目と3列目のノード(1列開けた列)のノード間距離は
(2+3+4+5+6)+(3+2+3+4+5)+(4+3+2+3+4)+(5+4+3+2+3)+(6+5+4+3+2)
=a[n]*2+2n^2
です。1列目から5列目までを考えるとこれを(n-2)倍します。
というように順に考えると全部で
b[n]=a[n]*n+(a[n]*2+n^2)*(n-1)+(a[n]*2+2n^2)*(n-2)+...+(a[n]*2+(n-1)n^2)*(1)
がノード間距離の総和になります。
計算すると
b[n]=n^3(n^2-1)/3
です。
ノード間距離の総数はn^2(n^2-)/2ですからノード間平均距離は(2/3)nになります。