cp's OEIS Frontend

A185423 Ordered forests of k increasing plane unary-binary trees with n nodes.

%I A185423 #30 Feb 11 2025 08:15:24
%S A185423 1,1,2,3,6,6,9,30,36,24,39,150,270,240,120,189,918,1980,2520,1800,720,
%T A185423 1107,6174,16254,25200,25200,15120,5040,7281,47070,142884,266616,
%U A185423 327600,272160,141120,40320,54351,394470,1369710,2948400,4331880
%N A185423 Ordered forests of k increasing plane unary-binary trees with n nodes.
%C A185423 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.
%F A185423 TABLE ENTRIES
%F A185423 (1)... T(n,k) = Sum_{j = 0..k} (-1)^j*binomial(k,j)*P(n,j),
%F A185423 where P(n,x) are the polynomials described in A185415.
%F A185423 Compare (1) with the formula for the number of ordered set partitions
%F A185423 (2)... A019538(n,k) = Sum_{j = 0..k} (-1)^j*binomial(k,j)*j^n.
%F A185423 RECURRENCE RELATION
%F A185423 (3)... T(n+1,k) = k*(T(n,k-1) + T(n,k) + T(n,k+1))
%F A185423 GENERATING FUNCTION
%F A185423 Let E(t) = 1/2 + (sqrt(3)/2)*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635.
%F A185423 The e.g.f. for the present triangle is
%F A185423 (4)... 1/(1 + x*(1 - E(t))) = Sum {n >= 0} R(n,x)*t^n/n!
%F A185423 = 1 + x*t + (x + 2*x^2)*t^2/2! + (3*x + 6*x^2 + 6*x^3)*t^3/3! + ....
%F A185423 ROW POLYNOMIALS
%F A185423 The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by
%F A185423 (5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.
%F A185423 By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity
%F A185423 (6)... (-i*sqrt(3))^(n-1)*OB(n,x)/x = R(n,y)/y,
%F A185423 where i = sqrt(-1) and x = (sqrt(3)*i/3)*y + (-1/2+sqrt(3)*i/6).
%F A185423 RELATIONS WITH OTHER SEQUENCES
%F A185423 Column 1: A080635.
%F A185423 A185422(n,k) = T(n,k)/k!.
%F A185423 Setting y = 0 in (6) gives
%F A185423 (7)... A080635(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} k!*Stirling2(n,k) * (-1/2+sqrt(3)*i/6)^(k-1).
%F A185423 The row polynomials have their zeros on the vertical line Re(z) = -1/2 in the complex plane (this follows from the above connection with the ordered Bell polynomials, which have negative real zeros). - _Peter Bala_, Oct 23 2023
%e A185423 Triangle begins
%e A185423 n\k|....1......2......3......4......5......6......7
%e A185423 ===================================================
%e A185423 ..1|....1
%e A185423 ..2|....1......2
%e A185423 ..3|....3......6......6
%e A185423 ..4|....9.....30.....36.....24
%e A185423 ..5|...39....150....270....240....120
%e A185423 ..6|..189....918...1980...2520...1800....720
%e A185423 ..7|.1107...6174..16254..25200..25200..15120...5040
%e A185423 ..
%e A185423 Examples of recurrence relation:
%e A185423 T(5,3) = 270 = 3*(T(4,2) + T(4,3) + T(4,4)) = 3*(30+36+24);
%e A185423 T(6,1) = 1*(T(5,0) + T(5,1) + T(5,2)) = 39+150.
%e A185423 Examples of ordered forests:
%e A185423 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.
%e A185423 ......... ......... ...3.....
%e A185423 .2...3... .3...2... ...|.....
%e A185423 ..\./.... ..\./.... ...2.....
%e A185423 ...1...4. ...1...4. ...|.....
%e A185423 ......... ......... ...1...4.
%e A185423 .
%e A185423 ......... ......... ...4.....
%e A185423 .2...4... .4...2... ...|.....
%e A185423 ..\./.... ..\./.... ...2.....
%e A185423 ...1...3. ...1...3. ...|.....
%e A185423 ......... ......... ...1...3.
%e A185423 .
%e A185423 ......... ......... ...4.....
%e A185423 .3...4... .4...3... ...|.....
%e A185423 ..\./.... ..\./.... ...3.....
%e A185423 ...1...2. ...1...2. ...|.....
%e A185423 ......... ......... ...1...2.
%e A185423 .
%e A185423 ......... ......... ...4.....
%e A185423 .3...4... .4...3... ...|.....
%e A185423 ..\./.... ..\./.... ...3.....
%e A185423 ...2...1. ...2...1. ...|.....
%e A185423 ......... ......... ...2...1.
%e A185423 .
%e A185423 ......... ......... ..........
%e A185423 ..2..4... ..3..4... ..4...3...
%e A185423 ..|..|... ..|..|... ..|...|...
%e A185423 ..1..3... ..1..2... ..1...2...
%e A185423 ......... ......... ..........
%p A185423 #A185423
%p A185423 P := proc(n,x)
%p A185423 description 'polynomial sequence P(n,x) A185415'
%p A185423 if n = 0 return 1
%p A185423 else
%p A185423 return x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
%p A185423 end proc:
%p A185423 with combinat:
%p A185423 T:=(n,k) -> add ((-1)^(k-j)*binomial(k,j)*P(n,j),j = 0..k):
%p A185423 for n from 1 to 10 do
%p A185423 seq(T(n,k),k = 1..n);
%p A185423 end do;
%o A185423 (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))))}
%Y A185423 Cf. A019538, A080635, A185421, A185422.
%K A185423 nonn,easy,tabl
%O A185423 1,3
%A A185423 _Peter Bala_, Jan 28 2011