$n = 4$ のときは以下の 14 通り。


親は複数の子を持ちうるので、親から子に向かって構築する方法はめんどくさい。
根には親がなく、根ではないノードは親が唯一に決まるので、子から親に向かって構築する方法を採用する。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> par;

// ノード v の親を何にするか悩んでいる。
// これまでで最も若い親の番号は p.
void f(int v, int p) {
  if(v == 0) {
    for(int i=0; i<=n; ++i) { if(i) { putchar(' '); } printf("%d", par[i]); } putchar('\n');
    return;
  }
  for(int u=min(p, v-1); u>=0; --u) { // v の親を u にする。
    par[v] = u;
    f(v-1, min(p, u));
  }
}

int main(void) {
  scanf("%d", &n);
  par.assign(n+1, -1); // v の親が u のとき、par[v] = u とする。
  f(n, n);
  return 0;
}
      

ちなみに、パターン数はカタラン数になる。

(ΦωΦ)＜つづく