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

Author

Alois P. Heinz, Apr 03 2016

Keywords

• nonn

Examples

			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.
		

Links

• Wikipedia, Partition of a set

Crossrefs

Cf. A000110, A185983, A271270, A271273.

Programs

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 *)

Formula

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