A271272 Number of set partitions of [n] into m blocks such that for each pair of distinct cyclically consecutive blocks (b,c) = (b,(b mod m)+1) at least one pair of numbers (i,j) = (i,(i mod n)+1) exists with i member of b and j member of c.

1, 1, 2, 5, 13, 36, 110, 374, 1404, 5750, 25419, 120325, 606210, 3234618, 18202851, 107647893, 666903189, 4316424771, 29116689197, 204259773724, 1487336089532, 11221857590608, 87591879539120, 706286859093554, 5875489876724901, 50364717424939105, 444367708336858660

Offset

0,3

Links

Table of n, a(n) for n=0..26.

Wikipedia, Partition of a set

Formula

a(n) = A000110(n) - A271273(n).

Example

A000110(4) - a(4) = 15 - 13 = 2: 13|2|4, 1|24|3.
A000110(5) - a(5) = 52 - 36 = 16: 124|3|5, 12|35|4, 134|2|5, 135|2|4, 13|25|4, 13|2|45, 13|2|4|5, 14|23|5, 1|235|4, 14|2|3|5, 15|24|3, 1|245|3, 1|24|3|5, 1|25|34, 1|25|3|4, 1|2|35|4.

Maple

b:= proc(n, i, m, l) option remember; `if`(n=0,
     `if`(l=[] or {l[]}={1} or i=m and {subsop(1=1, l)[]}=
      {1}, 1, 0), add(b(n-1, j, max(m, j), `if`(l=[], [1],
     `if`(j=m+1, subsop(1=0, `if`(j=i+1, [l[], 1], [l[], 0])),
     `if`(j=i+1 or j=1 and i=m, subsop(j=1, l), l)))), j=1..m+1))
    end:
a:= n-> b(n, 0$2, []):
seq(a(n), n=0..18);

Mathematica

b[n_, i_, m_, l_] := b[n, i, m, l] = If[n==0, If[l=={} || Union[l]=={1} || i==m && Union @ ReplacePart[l, 1 -> 1] == {1}, 1, 0], Sum[b[n-1, j, Max[m, j], If[l=={}, {1}, If[j==m+1, ReplacePart[If[j==i+1, Append[l, 1], Append[l, 0]], 1 -> 0], If[j==i+1 || j==1 && i==m, ReplacePart[l, j -> 1], l]]]], {j, 1, m+1}]]; a[n_] := b[n, 0, 0, {}]; Table[a[n], {n, 0, 18} ] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

Crossrefs

Cf. A000110, A185983, A271270, A271273.

Sequence in context: A066723 A000994 A266546 * A148296 A148297 A148298

Adjacent sequences: A271269 A271270 A271271 * A271273 A271274 A271275

Keyword

nonn

Author

Alois P. Heinz, Apr 03 2016

Status

approved