カウントゲームで先手が勝つのは何通り？

カウントゲームで先手が勝つのは何通り？

締め切りが 2017/11/14 10:00 AM なので，その 1 分後に投稿されるように予約

某SNSにおいて、チャットでAIと対戦できる「カウントゲーム」があります。
ある数からスタートし、交互に最大3つまでの数をカウントダウンしていき、最後に「0」を言った方が負け、というゲームです。

例えば、AとBが対戦し、Aが15からスタートして、以下のように進むとBの負けとなります。
A「15, 14」
B「13, 12」
A「11, 10, 9」
B「8」
A「7」
B「6, 5, 4」
A「3, 2, 1」
B「0」

なお、自分から負けるために、「1, 0」のように言うことはないものとします。
（相手が「1」まで言って、最後に「0」だけを言って負ける）

標準入力から整数 n が与えられたとき、Aが n からスタートし、最後にBが「0」を言うパターンが何通りあるか求め、標準出力に出力してください。
なお、n は1≦n≦50を満たすものとします。

例えば、n = 5のとき、以下の7通りがあります。


【入出力サンプル】
標準入力
5

標準出力
7

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

整数分割法＋同じものが複数あるときの並べ替えの個数の問題

initDiv = function(length, max) {
    ary = NULL
    repeat {
        if (length <= max) {
            ary = c(ary, length)
            return(ary)
        } else {
            ary = c(ary, max)
            length = length - max
        }
    }
}

nextDiv = function(ary) {
    repeat { # 1でない要素を後ろから探す
        sum = 0
        for (pos in length(ary):1) {
            a = ary[pos]
            sum = sum + a
            if (a != 1) {
                break
            }
        }
        if (ary[1] == 1) { # 全て1
            return(FALSE)
        }
        ary = ary[1:pos]
        ary[pos] = ary[pos] - 1
        max = ary[pos]
        sum = sum - max
        pos = pos + 1
        repeat {
            if (sum <= max) {
                ary[pos] = sum
                return(ary)
            } else {
                ary[pos] = max
                sum = sum - max
            }
            pos = pos + 1
        }
    }
}

check = function(d) {
    n = length(d)
    if (n %% 2 == 0) { # 先手が勝つためには奇数回
        return(0)
    } else { # 同じものが複数あるときの並べ替えの個数
        res = factorial(n)
        for (i in table(d)) {
            res = res/factorial(i)
        }
        return(res)
    }
}

f = function(length) {
    count = 0
    d = initDiv(length, 3)
    count = count+check(d)
    repeat {
        d = nextDiv(d)
        count = count+check(d)
        if (d[1] == 1) { # 毎回 1 ずつというのが最終
            break
        }
    }
    options(scipen=100)
    cat(count)
}

# f(scan(file("stdin", "r")))
f(5) # 7
f(6) # 12
f(15) # 2884
f(25) # 1277879
f(50) # 5281115313321