ポーランド記法から変換して不要な括弧を除去
締め切りが 2017/01/03 10:00 AM なので，その 1 分後に投稿されるように予約
設問
ポーランド記法や逆ポーランド記法を使うと、括弧を使わなくても演算を一意に表記できます。
例えば、通常の式(中置記法)で
(1 + 3) * (4 + 2)
のような場合、括弧を省略すると演算順序が変わってしまいますが、ポーランド記法で
* + 1 3 + 4 2
のように記述すると、括弧は不要です。
今回は数字は1種類のみ、演算子は「+」「*」の2種類だけを考えます。
これらの数字と演算子で構成され、数字が入る場所が n 箇所あるポーランド記法の式をすべて考え、
それらを通常の式(中置記法)に変換した上で、不要な（演算順序に影響がない）括弧を除去します。
（「+」よりも「*」の方が、演算の優先度が高い前提です）
この作業を行ったとき、括弧のペアがいくつ残るかを求めます。
例えば、n = 3 のときは以下の8パターンがあり、必要な括弧は全部で2ペアです。
（数字は何でも構いませんが、例えば「5」を使うと以下のようになります。）
+ + 5 5 5 => 5 + 5 + 5
+ * 5 5 5 => 5 * 5 + 5
* + 5 5 5 => (5 + 5) * 5 ← ペアが1つ
* * 5 5 5 => 5 * 5 * 5
+ 5 + 5 5 => 5 + 5 + 5
+ 5 * 5 5 => 5 + 5 * 5
* 5 + 5 5 => 5 * (5 + 5) ← ペアが1つ
* 5 * 5 5 => 5 * 5 * 5
標準入力から整数 n が与えられるとき、括弧のペアの総数を求め、標準出力に出力してください。
ただし、nは15以下の正の整数とします。
================================================
いつものように，n が小さいときの解から規則性を見いだす
f = function(n) {
unit = factorial(2 * (n - 1))/factorial(n - 1)/factorial(n)
Sum = 0
for (i in 0:7) {
if (n >= 2 * i + 1)
Sum = Sum + choose(n, 2 * i + 1)*unit*i
}
Sum
}
f(15)
