This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2017 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A185423 Ordered forests of k increasing plane unary-binary trees with n nodes. 6
 1, 1, 2, 3, 6, 6, 9, 30, 36, 24, 39, 150, 270, 240, 120, 189, 918, 1980, 2520, 1800, 720, 1107, 6174, 16254, 25200, 25200, 15120, 5040, 7281, 47070, 142884, 266616, 327600, 272160, 141120, 40320, 54351, 394470, 1369710, 2948400, 4331880 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing. A080635 enumerates increasing plane (ordered) unary-binary trees with n nodes with labels drawn from the set {1,2,...,n}. The entry T(n,k) of the present table counts ordered forests of k increasing plane unary-binary trees with n nodes. See below for an example. See A185421 for the corresponding table in the non-plane case. See A185422 for the table for unordered forests of increasing plane unary-binary trees. LINKS FORMULA TABLE ENTRIES (1)... T(n,k) = Sum_{j=0..k} (-1)^j*binomial(k,j)*P(n,j), where P(n,x) are the polynomials described in A185415. Compare (1) with the formula for the number of ordered set partitions (2)... A019538(n,k) = Sum_{j=0..k} (-1)^j*binomial(k,j)*j^n. RECURRENCE RELATION (3)... T(n+1,k) = k*(T(n,k-1) + T(n,k) + T(n,k+1)) GENERATING FUNCTION Let E(t) = 1/2 + (sqrt(3)/2)*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635. The e.g.f. for the present triangle is (4)... 1/(1+x*(1-E(t)) = Sum {n>=0} R(n,x)*t^n/n! = 1 + x*t + (x+2*x^2)*t^2/2! + (3*x+6*x^2+6*x^3)*t^3/3! + .... ROW POLYNOMIALS The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by (5)... OB(n,x) = Sum_{k=1..n} k!*Stirling2(n,k)*x^k. By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity (6)... (-i*sqrt(3))^(n-1)*OB(n,x)/x = R(n,y)/y, where i = sqrt(-1) and x = (sqrt(3)*i/3)*y + (-1/2+sqrt(3)*i/6). RELATIONS WITH OTHER SEQUENCES Column 1: A080635. A185422(n,k) = T(n,k)/k!. Setting y = 0 in (6) gives (7)... A080635(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} k!*Stirling2(n,k) * (-1/2+sqrt(3)*i/6)^(k-1). EXAMPLE Triangle begins n\k|....1......2......3......4......5......6......7 =================================================== ..1|....1 ..2|....1......2 ..3|....3......6......6 ..4|....9.....30.....36.....24 ..5|...39....150....270....240....120 ..6|..189....918...1980...2520...1800....720 ..7|.1107...6174..16254..25200..25200..15120...5040 .. Examples of recurrence relation: T(5,3) = 270 = 3*(T(4,2) + T(4,3) + T(4,4)) = 3*(30+36+24); T(6,1) = 1*(T(5,0) + T(5,1) + T(5,2)) = 39+150. Examples of ordered forests: T(4,2) = 30. The 15 unordered forests consisting of two plane increasing unary-binary trees on 4 nodes are shown below. We can order the trees in a forest in two ways giving rise to 30 ordered forests. ......... ......... ...3..... .2...3... .3...2... ...|..... ..\./.... ..\./.... ...2..... ...1...4. ...1...4. ...|..... ......... ......... ...1...4. . ......... ......... ...4..... .2...4... .4...2... ...|..... ..\./.... ..\./.... ...2..... ...1...3. ...1...3. ...|..... ......... ......... ...1...3. . ......... ......... ...4..... .3...4... .4...3... ...|..... ..\./.... ..\./.... ...3..... ...1...2. ...1...2. ...|..... ......... ......... ...1...2. . ......... ......... ...4..... .3...4... .4...3... ...|..... ..\./.... ..\./.... ...3..... ...2...1. ...2...1. ...|..... ......... ......... ...2...1. . ......... ......... .......... ..2..4... ..3..4... ..4...3... ..|..|... ..|..|... ..|...|... ..1..3... ..1..2... ..1...2... ......... ......... .......... MAPLE P := proc(n, x) description 'polynomial sequence P(n, x) A185415' if n = 0 return 1 else return x*(P(n-1, x-1)-P(n-1, x)+P(n-1, x+1)) end proc: with combinat: T:=(n, k) -> add ((-1)^(k-j)*binomial(k, j)*P(n, j), j = 0..k): for n from 1 to 10 do seq(T(n, k), k = 1..n); end do; PROG (PARI) {T(n, k)=if(n<1|k<1|k>n, 0, if(n==1, if(k==1, 1, 0), k*(T(n-1, k-1)+T(n-1, k)+T(n-1, k+1))))} CROSSREFS Cf. A019538, A080635, A185421, A185422. Sequence in context: A187326 A056907 A039799 * A144583 A155215 A119319 Adjacent sequences:  A185420 A185421 A185422 * A185424 A185425 A185426 KEYWORD nonn,easy,tabl AUTHOR Peter Bala, Jan 28 2011 STATUS approved

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

Last modified December 9 21:09 EST 2018. Contains 318023 sequences. (Running on oeis4.)