A271207 Number of set partitions of [n] avoiding triples (t,t+1,t+2) having t+i in block b+i for some b.

1, 1, 2, 4, 10, 28, 89, 315, 1233, 5285, 24583, 123062, 658335, 3741625, 22483415, 142264589, 944652336, 6562959239, 47583055191, 359196368057, 2817394708454, 22919157785777, 193045807856919, 1681025045594032, 15112573721911697, 140088106892677440

Offset

0,3

Links

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

Wikipedia, Partition of a set

Example

a(4) = 10: 1234, 123|4, 124|3, 12|34, 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4.

Maple

b:= proc(n, i, t, m) option remember; `if`(n=0, 1, add(`if`(
     t and j=i+1, 0, b(n-1, j, is(j=i+1), max(m, j))), j=1..m+1))
    end:
a:= n-> b(n, 1, false, 0):
seq(a(n), n=0..30);

Mathematica

b[n_, i_, t_, m_] := b[n, i, t, m] = If[n == 0, 1, Sum[If[t && j == i + 1, 0, b[n - 1, j, j == i + 1, Max[m, j]]], {j, 1, m + 1}]];
a[n_] := b[n, 1, False, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 27 2018, translated from Maple *)

Crossrefs

Column k=0 of A271206.

Sequence in context: A149832 A229046 A363110 * A091175 A090594 A361912

Adjacent sequences: A271204 A271205 A271206 * A271208 A271209 A271210

Keyword

nonn

Author

Alois P. Heinz, Apr 01 2016

Status

approved