login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 way exemplified by [6], [5,1], [4,2], [4,1,1], [3,3], [3,2,1], [3,1,1,1], [2,2,2], [2,2,1,1], [2,1,1,1,1], [1,1,1,1,1,1] (the "Mathematica" ordering). 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. 8

%I

%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 way exemplified by [6], [5,1], [4,2], [4,1,1], [3,3], [3,2,1], [3,1,1,1], [2,2,2], [2,2,1,1], [2,1,1,1,1], [1,1,1,1,1,1] (the "Mathematica" ordering). 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 Row n has A000041(n) terms (=number of partitions of n). Row sums yield the Catalan numbers (A000108).

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

%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 starts:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 4, 2, 6, 1;

%e 1, 5, 5, 10, 10, 10, 1;

%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_ *)

%Y Cf. A000041, A000108.

%Y Cf. A134264, A091867.

%K nonn,look,tabf

%O 1,5

%A _Emeric Deutsch_, Nov 23 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 14:53 EST 2018. Contains 299380 sequences. (Running on oeis4.)