集合写真できれいに写る配置は何通り？

集合写真できれいに写る配置は何通り？

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

設問
みんなで集合写真を撮るときの並び方の配置を考えます。
人数が少なければ一列に並ぶこともありますが、横に長くなると図のように複数列に並ぶことがあります。

複数列に並ぶときは、互い違いに並ばないと全員の顔が見えないので、
前の人の間から顔が見えるように並びます。
また、隣の人とは間を空けずに並ぶものとし、後ろに行けば行くほど人数が少なくなるものとします。
標準入力から人数 n が与えられたとき、n人が並ぶときの並び方が何通りあるかを求め、
標準出力に出力してください。
（個人は区別せず、その配置だけを考えます。）
なお、n は 1≦n≦200を満たす整数とします。
例えば、n=6 のとき、以下の8通りがあります。

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

標準出力
8
==================================================================

これは，整数列大辞典の A001524 であるが，そこに書いてあるアルゴリズムの説明が不完全（？）で，私には解を導くことができなかった。

n が小さい場合について，順次列挙していくと，規則性が浮かび上がった。
R(n,r) は，n 人を並べるとき，最下段が r 人になる並び方の総数
R(n1, n1)=1，R(1,1)=r(6,3)=R(10,4)=1 などの自明な解と，規則的な関係が見られる。

規則をプログラムしたものの，R ではいつものとおり計算時間オーバーなので（私のシステムでは制限時間内），Python 3 でやってみても，やはり時間オーバー。
全く同じものを「Python3 ではなくて，Python  だよ！」と，だましたら，パスした。なんだこりゃ。

R プログラム

f = function(N) {
  n = 200
  a = matrix(0, n, n)
  for (i in 1:n) {
    a[i, i] = 1
  }
  tri.max = 19
  tri = integer(tri.max)
  for (i in 1:tri.max) {
    x = i*(i+1)/2
    tri[i] = x
    a[x, i] = 1
  }
  a[4, 3] = 2
  a[5, 3] = 1
  a[5 ,4] = 3
  begin = 3
  for (i in 6:N) {
    begin = begin + (i %in% tri)
    end = i-1
    for (j in begin:end) {
      top = i-j
      temp = 0
      for (k in top:1) {
        mul = i-top-k
        if (mul > 0) {
          temp = temp+a[top, k] * mul
        }
      }
      #cat(i, j, "\n")
      a[i, j] = temp
    }
  }
  options(scipen=100)
  cat(sum(a[N,]))
}

# f(scan(file("stdin", "r")))

f(4) # 3
f(6) # 8
f(10) # 38
f(100) # 970174745
system.time(f(200)) # 56220326505673、0.126 s

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

Python プログラム

import scipy as sp

def f(N):
  n = 200
  a = sp.reshape(sp.zeros(n*n), (n, n))
  for i in range(n):
    a[i, i] = 1
  tri_max = 19
  tri = sp.zeros(tri_max)
  for i in range(1, tri_max+1):
    tri[i-1] = i*(i+1)/2 - 1
  for i in range(tri_max):
    a[tri[i], i] = 1
  a[3, 2] = 2
  a[4, 2] = 1
  a[4 ,3] = 3
  begin = 2
  for i in range(5, N):
    if i in tri:
      begin += 1
    end = i-1
    for j in range(begin, end+1):
      top = i-j-1
      x = 0
      for k in range(top, -1, -1):
        mul = i-top-k-1
        if mul > 0:
          x += a[top, k] * mul
      a[i, j] = x
  ans = 0
  for i in range(N):
    ans += a[N-1, i]
  print(int(ans))

f(int(input()))

#f(6) # 8
#f(4) # 3
#f(10) # 38
#f(100) # 970174745
#f(200) # 56220326505673 Python 3 より Python 2 が速い？ 0.91s