A125181 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n whose ascent lengths form the k-th partition of the integer n; the partitions of n are ordered in the "Mathematica" ordering.

1, 1, 1, 1, 3, 1, 1, 4, 2, 6, 1, 1, 5, 5, 10, 10, 10, 1, 1, 6, 6, 15, 3, 30, 20, 5, 30, 15, 1, 1, 7, 7, 21, 7, 42, 35, 21, 21, 105, 35, 35, 70, 21, 1, 1, 8, 8, 28, 8, 56, 56, 4, 56, 28, 168, 70, 28, 84, 168, 280, 56, 14, 140, 140, 28, 1, 1, 9, 9, 36, 9, 72, 84, 9, 72, 36, 252, 126, 36

Offset: 1

Author

Emeric Deutsch, Nov 23 2006

Keywords

• nonn
• look
• tabf

Comments

Equivalently, T(n,k) is the number of ordered trees with n edges whose node degrees form the k-th partition of the integer n.

Also the number of non-crossing set partitions whose block sizes are the parts of the n-th integer partition in graded Mathematica ordering. - Gus Wiseman, Feb 15 2019

For relations to Lagrange inversion through shifted reciprocals of a function, refined Narayana numbers, non-crossing partitions, trees, and other lattice paths, see A134264 and A091867. - Tom Copeland, Nov 01 2014

Examples

			Example: T(5,3)=5 because the 3rd partition of 5 is [3,2] and we have (UU)DD(UUU)DDD, (UUU)DDD(UU)DD, (UU)D(UUU)DDDD, (UUU)D(UU)DDDD and (UUU)DD(UU)DDD; here U=(1,1), D=(1,-1) and the ascents are shown between parentheses.
Triangle begins:
  1
  1   1
  1   3   1
  1   4   2   6   1
  1   5   5  10  10  10   1
  1   6   6  15   3  30  20   5  30  15   1
  1   7   7  21   7  42  35  21  21 105  35  35  70  21   1
Row 4 counts the following non-crossing set partitions:
  {{1234}}  {{1}{234}}  {{12}{34}}  {{1}{2}{34}}  {{1}{2}{3}{4}}
            {{123}{4}}  {{14}{23}}  {{1}{23}{4}}
            {{124}{3}}              {{12}{3}{4}}
            {{134}{2}}              {{1}{24}{3}}
                                    {{13}{2}{4}}
                                    {{14}{2}{3}}
		

References

• R. P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, Cambridge, 1999; Theorem 5.3.10.

Links

• Alois P. Heinz, Rows n = 1..26, flattened
• Germain Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 333-350 (1972).

Crossrefs

Other orderings are A134264 and A306438.

Cf. A000041, A000108, A000110, A001263, A016098, A091867, A124794, A134264.

Programs

Maple

with(combinat): for n from 1 to 9 do p:=partition(n): for q from 1 to numbpart(n) do m:=convert(p[numbpart(n)+1-q],multiset): k:=nops(p[numbpart(n)+1-q]): s[n,q]:=n!/(n-k+1)!/product(m[j][2]!,j=1..nops(m)) od: od: for n from 1 to 9 do seq(s[n,q],q=1..numbpart(n)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, i, k) `if`(n=0, [k!], `if`(i<1, [],
      [seq(map(x->x*j!, b(n-i*j, i-1, k-j))[], j=0..n/i)]))
    end:
T:= proc(n) local l, m;
      l:= b(n, n, n+1); m:=nops(l);
      seq(n!/l[m-i], i=0..m-1)
    end:
seq(T(n), n=1..10);  # Alois P. Heinz, May 25 2013

Mathematica

b[n_, i_, k_] := b[n, i, k] = If[n == 0, {k!}, If[i<1, {}, Flatten @ Table[Map[#*j! &, b[n-i*j, i-1, k-j]], {j, 0, n/i}]]]; T[n_] := Module[{l, m}, l = b[n, n, n+1]; m = Length[l]; Table[n!/l[[m-i]], {i, 0, m-1}]]; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)
Table[Binomial[Total[y],Length[y]-1]*(Length[y]-1)!/Product[Count[y,i]!,{i,Max@@y}],{y,Join@@Table[IntegerPartitions[n],{n,1,8}]}] (* Gus Wiseman, Feb 15 2019 *)

SageMath

def C(p):
    n = sum(p); l = n - len(p) + 1
    def f(x): return factorial(len(list(filter(lambda y: y == x, p))))
    return factorial(n) // (factorial(l) * prod(f(x) for x in set(p)))
def row(n): return list(C(p) for p in Partitions(n))
for n in range(1, 9): print(row(n))  # Peter Luschny, Jul 14 2022

Formula

Row n has A000041(n) terms (equal to the number of partitions of n).

Row sums yield the Catalan numbers (A000108).

Given a partition p = [a(1)^e(1), ..., a(j)^e(j)] into k parts (e(1) +...+ e(j) = k), the number of Dyck paths whose ascent lengths yield the partition p is n!/[(n-k+1)!e(1)!e(2)! ... e(j)! ]. - Franklin T. Adams-Watters