OFFSET
1,5
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
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).
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
EXAMPLE
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}}
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 *)
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Emeric Deutsch, Nov 23 2006
STATUS
approved