A185983 Triangle read by rows: number of set partitions of n elements with k circular connectors.

1, 1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 8, 4, 2, 1, 1, 20, 15, 14, 1, 1, 6, 53, 61, 68, 11, 3, 1, 25, 159, 267, 295, 97, 32, 1, 1, 93, 556, 1184, 1339, 694, 242, 28, 3, 1, 346, 2195, 5366, 6620, 4436, 1762, 371, 48, 2, 1, 1356, 9413, 25400, 34991, 27497, 12977, 3650, 634, 53, 3

Offset: 0

Author

Brian Drake, Feb 08 2011

Keywords

• nonn
• tabl

Comments

A pair (a,a+1) in a set partition with m blocks is a circular connector if a is in block i and a+1 is in block (i mod m)+1 for some i. In addition, (n,1) is considered a circular connector if n is in block m.

Examples

			For a(4,2) = 8, the set partitions are 1/234, 134/2, 124/3, 123/4, 12/34, 14/23, 1/24/3, and 13/2/4.
For a(5,1) = 1, the set partition is 13/25/4.
For a(6,6) = 3, the set partitions are 135/246, 14/25/36, 1/2/3/4/5/6.
Triangle begins:
  1;
  1, 0;
  1, 0,  1;
  1, 0,  3,  1;
  1, 0,  8,  4,  2;
  1, 1, 20, 15, 14,  1;
  1, 6, 53, 61, 68, 11, 3;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..60, flattened
• T. Mansour and A. O. Munagi, Block-connected set partitions, European J. Combin., 31 (2010), 887-902.

Crossrefs

Cf. A185982. Row sums are A000110.

T(n,n) = A032741(n) if n>0. - Alois P. Heinz, Oct 14 2011

T(2n,n) gives A362944.

Cf. A271272, A271273.

Programs

Maple

b:= proc(n, i, m, t) option remember; `if`(n=0, x^(t+
     `if`(i=m and m<>1, 1, 0)), add(expand(b(n-1, j,
      max(m, j), `if`(j=m+1, 0, t+`if`(j=1 and i=m
      and j<>m, 1, 0)))*`if`(j=i+1, x, 1)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Mar 30 2016

Mathematica

b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, x^(t + If[i == m && m != 1, 1, 0]), Sum[Expand[b[n - 1, j, Max[m, j], If[j == m + 1, 0, t + If[j == 1 && i == m && j != m, 1, 0]]]*If[j == i + 1, x, 1]], {j, 1, m + 1}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 1, 0, 0] ];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 19 2016, after Alois P. Heinz *)

Extensions

More terms from Alois P. Heinz, Oct 14 2011