login
Regular triangle read by rows where T(n,k) is the number of non-crossing set partitions of {1, ..., n} in which all blocks have size k.
3

%I #19 Feb 16 2019 18:52:15

%S 1,1,1,1,0,1,1,2,0,1,1,0,0,0,1,1,5,3,0,0,1,1,0,0,0,0,0,1,1,14,0,4,0,0,

%T 0,1,1,0,12,0,0,0,0,0,1,1,42,0,0,5,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,

%U 132,55,22,0,6,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,429,0,0,0,0,7,0,0,0,0,0,0,1

%N Regular triangle read by rows where T(n,k) is the number of non-crossing set partitions of {1, ..., n} in which all blocks have size k.

%H Germain Kreweras, <a href="https://doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, Discrete Math. 1 333-350 (1972).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Noncrossing_partition">Noncrossing partition</a>.

%F If d|n, then T(n, d) = binomial(n, n/d)/(n - n/d + 1); otherwise T(n, k) = 0 [Theorem 1 of Kreweras].

%e Triangle begins:

%e 1

%e 1 1

%e 1 0 1

%e 1 2 0 1

%e 1 0 0 0 1

%e 1 5 3 0 0 1

%e 1 0 0 0 0 0 1

%e 1 14 0 4 0 0 0 1

%e 1 0 12 0 0 0 0 0 1

%e 1 42 0 0 5 0 0 0 0 1

%e 1 0 0 0 0 0 0 0 0 0 1

%e 1 132 55 22 0 6 0 0 0 0 0 1

%e Row 6 counts the following non-crossing set partitions (empty columns not shown):

%e {{1}{2}{3}{4}{5}{6}} {{12}{34}{56}} {{123}{456}} {{123456}}

%e {{12}{36}{45}} {{126}{345}}

%e {{14}{23}{56}} {{156}{234}}

%e {{16}{23}{45}}

%e {{16}{25}{34}}

%p T:= (n, k)-> `if`(irem(n, k)=0, binomial(n, n/k)/(n-n/k+1), 0):

%p seq(seq(T(n,k), k=1..n), n=1..14); # _Alois P. Heinz_, Feb 16 2019

%t Table[Table[If[Divisible[n,d],d/n*Binomial[n,n/d-1],0],{d,n}],{n,15}]

%Y Row sums are A194560. Column k=2 is A126120. Trisection of column k=3 is A001764.

%Y Cf. A000108, A000110, A000296, A001006, A001263, A001610, A016098, A038041, A061095, A125181, A134264.

%K nonn,tabl

%O 1,8

%A _Gus Wiseman_, Feb 15 2019