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

Links

Table of n, a(n) for n=1..105.

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

Wikipedia, Noncrossing partition.

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

Example

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

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}]

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.

Sequence in context: A147861 A167271 A156348 * A343746 A227990 A101614

Adjacent sequences: A306434 A306435 A306436 * A306438 A306439 A306440

Keyword

nonn,tabl

Author

Gus Wiseman, Feb 15 2019

Status

approved