A261961 Number of ordered set partitions of {1,2,...,n} such that no part has the same size as any of its two immediate predecessors.

1, 1, 1, 7, 9, 31, 403, 1597, 7913, 68551, 539691, 4359037, 48419715, 560648557, 4985097601, 59798395027, 869794249513, 11143895125527, 159575614945315, 2593765421983597, 38615447492264219, 642012651525487501, 11768461266053785921, 220201814964135821967

Offset: 0

Author

Alois P. Heinz, Sep 06 2015

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..250

Crossrefs

Column k=2 of A261959.

Cf. A261962.

Programs

Maple

b:= proc(n, i, j) option remember; `if`(n=0, 1, add(
      `if`(k=i or k=j, 0, (t-> binomial(n, k)*b(t,
      `if`(k>t, 0, k), `if`(i>t, 0, i)))(n-k)), k=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..30);

Mathematica

b[n_, i_, j_] := b[n, i, j] = If[n == 0, 1, Sum[If[k == i || k == j, 0, Function[t, Binomial[n, k]*b[t, If[k > t, 0, k], If[i > t, 0, i]]][n - k]], {k, 1, n}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 24 2018, translated from Maple *)