|
%I #35 Jul 14 2022 14:52:48
%S 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,
%T 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,
%U 70,28,84,168,280,56,14,140,140,28,1,1,9,9,36,9,72,84,9,72,36,252,126,36
%N 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.
%C 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.
%C 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
%C 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
%D R. P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, Cambridge, 1999; Theorem 5.3.10.
%H Alois P. Heinz, <a href="/A125181/b125181.txt">Rows n = 1..26, flattened</a>
%H Germain Kreweras, <a href="https://doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, Discrete Math. 1 333-350 (1972).
%F Row n has A000041(n) terms (equal to the number of partitions of n).
%F Row sums yield the Catalan numbers (A000108).
%F 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_
%e 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.
%e Triangle begins:
%e 1
%e 1 1
%e 1 3 1
%e 1 4 2 6 1
%e 1 5 5 10 10 10 1
%e 1 6 6 15 3 30 20 5 30 15 1
%e 1 7 7 21 7 42 35 21 21 105 35 35 70 21 1
%e Row 4 counts the following non-crossing set partitions:
%e {{1234}} {{1}{234}} {{12}{34}} {{1}{2}{34}} {{1}{2}{3}{4}}
%e {{123}{4}} {{14}{23}} {{1}{23}{4}}
%e {{124}{3}} {{12}{3}{4}}
%e {{134}{2}} {{1}{24}{3}}
%e {{13}{2}{4}}
%e {{14}{2}{3}}
%p 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
%p # second Maple program:
%p b:= proc(n, i, k) `if`(n=0, [k!], `if`(i<1, [],
%p [seq(map(x->x*j!, b(n-i*j, i-1, k-j))[], j=0..n/i)]))
%p end:
%p T:= proc(n) local l, m;
%p l:= b(n, n, n+1); m:=nops(l);
%p seq(n!/l[m-i], i=0..m-1)
%p end:
%p seq(T(n), n=1..10); # _Alois P. Heinz_, May 25 2013
%t 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_ *)
%t 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 *)
%o (SageMath)
%o def C(p):
%o n = sum(p); l = n - len(p) + 1
%o def f(x): return factorial(len(list(filter(lambda y: y == x, p))))
%o return factorial(n) // (factorial(l) * prod(f(x) for x in set(p)))
%o def row(n): return list(C(p) for p in Partitions(n))
%o for n in range(1, 9): print(row(n)) # _Peter Luschny_, Jul 14 2022
%Y Other orderings are A134264 and A306438.
%Y Cf. A000041, A000108, A000110, A001263, A016098, A091867, A124794, A134264.
%K nonn,look,tabf
%O 1,5
%A _Emeric Deutsch_, Nov 23 2006
|
