A306437 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.

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

Offset: 1

Author

Gus Wiseman, Feb 15 2019

Keywords

• nonn
• tabl

Examples

			Triangle begins:
  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   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 132  55  22   0   6   0   0   0   0   0   1
Row 6 counts the following non-crossing set partitions (empty columns not shown):
  {{1}{2}{3}{4}{5}{6}}  {{12}{34}{56}}  {{123}{456}}  {{123456}}
                        {{12}{36}{45}}  {{126}{345}}
                        {{14}{23}{56}}  {{156}{234}}
                        {{16}{23}{45}}
                        {{16}{25}{34}}
		

Links

• Germain Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 333-350 (1972).
• Wikipedia, Noncrossing partition.

Crossrefs

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

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

Programs

Maple

T:= (n, k)-> `if`(irem(n, k)=0, binomial(n, n/k)/(n-n/k+1), 0):
seq(seq(T(n,k), k=1..n), n=1..14);  # Alois P. Heinz, Feb 16 2019

Mathematica

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

Formula

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