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

%I #32 May 09 2023 16:59:50

%S 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,

%T 159,267,295,97,32,1,1,93,556,1184,1339,694,242,28,3,1,346,2195,5366,

%U 6620,4436,1762,371,48,2,1,1356,9413,25400,34991,27497,12977,3650,634,53,3

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

%C 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.

%H Alois P. Heinz, <a href="/A185983/b185983.txt">Rows n = 0..60, flattened</a>

%H T. Mansour and A. O. Munagi, <a href="http://dx.doi.org/10.1016/j.ejc.2009.07.001">Block-connected set partitions</a>, European J. Combin., 31 (2010), 887-902.

%e 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.

%e For a(5,1) = 1, the set partition is 13/25/4.

%e For a(6,6) = 3, the set partitions are 135/246, 14/25/36, 1/2/3/4/5/6.

%e Triangle begins:

%e 1;

%e 1, 0;

%e 1, 0, 1;

%e 1, 0, 3, 1;

%e 1, 0, 8, 4, 2;

%e 1, 1, 20, 15, 14, 1;

%e 1, 6, 53, 61, 68, 11, 3;

%e ...

%p b:= proc(n, i, m, t) option remember; `if`(n=0, x^(t+

%p `if`(i=m and m<>1, 1, 0)), add(expand(b(n-1, j,

%p max(m, j), `if`(j=m+1, 0, t+`if`(j=1 and i=m

%p and j<>m, 1, 0)))*`if`(j=i+1, x, 1)), j=1..m+1))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1, 0$2)):

%p seq(T(n), n=0..12); # _Alois P. Heinz_, Mar 30 2016

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 1, 0, 0] ];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, May 19 2016, after _Alois P. Heinz_ *)

%Y Cf. A185982. Row sums are A000110.

%Y T(n,n) = A032741(n) if n>0. - _Alois P. Heinz_, Oct 14 2011

%Y T(2n,n) gives A362944.

%Y Cf. A271272, A271273.

%K nonn,tabl

%O 0,9

%A _Brian Drake_, Feb 08 2011

%E More terms from _Alois P. Heinz_, Oct 14 2011