ローマ水道は、縦横に流れる水が合流する地点のいくつかにおいて橋をかけ、立体交差させることで、水の流れが衝突しないように工夫されています。
下の図は、ローマ水道をシンプルにしたものです。
縦と横にn区間ずつある格子状に水道があるとして、A地点からB地点に最短距離で移動したいのですが、左下と右上を結ぶ対角線上の点のうち、スタートとゴール以外の水の流れが衝突する箇所には橋をかけ、立体交差させています。
つまり、この交差点では曲がることができません。
※図では立体交差を表現するために道を曲げていますが、立体交差の上を超えても下をくぐっても距離は変わらないものとします。
図のようにn＝4のとき、スタートからゴールまでの道順は28通りあります。
では、n＝10のときとn＝20のときについて、スタートからゴールまでの道順が何通りあるかを求めてください。
n = 10 のときは無理矢理求めた（この記事のコメントを参照）が，そのやり方は n = 20 では通用しない。
数列の法則も見いだせない（なさそうに思う）。
lst = rep(1,n)
for(i in 2:n) {
lst = cumsum(lst)[-1]
}
return(lst*2)
}
> count.ways2(10)
[1] 33592
library(e1071)
a = bincombinations(2*n)
a = a[rowSums(a) == n, ]
ans = logical(nrow(a))
for (i in 1:nrow(a)) {
b = a[i,]
r = cumsum(b)
u = cumsum(!b)
ok = TRUE
for (j in 1:(n-1)*2) {
if (r[j] == u[j] && b[j]!=b[j+1]) {
ok = FALSE
break
}
}
ans[i] = ok
}
sum(ans)
}
> calc(10)
[1] 33592