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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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. 5
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

Row n has A000041(n) terms (=number of partitions of n). Row sums yield the Catalan numbers (A000108).

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

FORMULA

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

1;

1, 1;

1, 3, 1;

1, 4, 2,  6,  1;

1, 5, 5, 10, 10, 10, 1;

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

CROSSREFS

Cf. A000041, A000108.

Sequence in context: A134557 A219842 A134264 * A157076 A049999 A126015

Adjacent sequences:  A125178 A125179 A125180 * A125182 A125183 A125184

KEYWORD

nonn,look,tabf

AUTHOR

Emeric Deutsch, Nov 23 2006

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified September 17 21:42 EDT 2014. Contains 246885 sequences.