|
| |
|
|
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.
|
|
14
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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:
|
|
|
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))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
