|
%I #42 Aug 06 2020 10:14:21
%S 1,2,8,37,184,959,5172,28641,162008,932503,5445934,32197334,192357788,
%T 1159603592,7045356104,43098733353,265240985112,1641100253735,
%U 10202295895890,63696629668980,399216722146770,2510833297584165
%N Number of independent sets in rooted plane trees on n nodes.
%C Equals the main diagonal of square array A130523. - _Paul D. Hanna_, Jun 06 2007
%C From _Petros Hadjicostas_, Aug 06 2020: (Start)
%C To prove _R. J. Mathar_'s conjecture, let b(n) = A007226(n-1) = (2*/n)*binomial(3*(n-1), n-1) and c(n) = A000108(n-1) = binomial(2*(n-1), n-1)/n. Since a(n) = b(n) - c(n), it is enough to prove that each of the sequences (b(n): n >= 1) and (c(n): n >= 1) satisfies the same recurrence as (a(n): n >= 1).
%C For simplicity, denote the recurrence by f(n,0)*a(n) + f(n,1)*a(n-1) + f(n,2)*a(n-2) + f(n,3)*a(n-3) = 0. Let g(n) = 2*n*(2*n - 3)/(3*(3*n - 4)*(3*n - 5)) and h(n) = n/(2*(2*n - 3)). Then we can easily show that b(n-i) = b(n)* Product_{j=0..i-1} g(n-j) and c(n-i) = c(n)*Product_{j=0..i-1} h(n-j) for i >= 1.
%C Using a CAS (e.g. PARI), one can show that f(n,0) + f(n,1)*g(n) + f(n,2)*g(n)*g(n-1) + f(n,3)*g(n)*g(n-1)*g(n-2) = 0. Multiplying both sides by b(n), we get f(n,0)*b(n) + f(n,1)*b(n-1) + f(n,2)*b(n-2) + f(n,3)*b(n-3) = 0.
%C Again, using a CAS, one can show that f(n,0) + f(n,1)*h(n) + f(n,2)*h(n)*h(n-1) + f(n,3)*h(n)*h(n-1)*h(n-2) = 0. Multiplying both sides by c(n), we get f(n,0)*c(n) + f(n,1)*c(n-1) + f(n,2)*c(n-2) + f(n,3)*c(n-3) = 0. (End)
%H M. Klazar, <a href="https://doi.org/10.1006/eujc.1995.0095">Twelve countings with rooted plane trees</a>, European Journal of Combinatorics, 18(2) (1997), 195-210.
%H M. Klazar, <a href="https://doi.org/10.1006/eujc.1997.0160">Addendum Twelve Countings with Rooted Plane Trees</a>, European Journal of Combinatorics, 18(6) (1997), 739-740.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F a(n+1) = (2/(n+1))*C(3*n, n) - (1/(n+1))*C(2*n, n) = A007226(n) - A000108(n). - _Paul Barry_, Nov 05 2006
%F G.f.: A(x) = x/(1 - x*C(x)*F(x) - x*F(x)^2), where C(x) is g.f. of the Catalan numbers (A000108) (i.e., C(x) = 1 + x*C(x)^2) and F(x) is the g.f. of ternary numbers (A001764) (i.e., F(x) = 1 + x*F(x)^3). - _Paul D. Hanna_, Jun 06 2007
%F Conjecture: 2*n*(n - 1)*(2*n - 3)*(44*n - 69)*a(n) + (n - 1)*(176*n^3 - 9591*n^2 + 38703*n - 40640)*a(n-1) + (-17479*n^4 + 218005*n^3 - 959616*n^2 + 1797890*n - 1221920)*a(n-2) + 6*(3*n - 10)*(2*n - 7)*(3*n - 11)*(517*n - 1198)*a(n-3) = 0 for n >= 4. - _R. J. Mathar_, Nov 26 2012
%o (PARI) {a(n)=my(A000108, A001764); A000108=Ser(vector(n+1, r, binomial(2*r-2, r-1)/r)); A001764=Ser(vector(n+1, r, binomial(3*r-3, r-1)/(2*r-1))); polcoeff(x/(1-x*A000108*A001764-x*A001764^2 +x*O(x^n)), n)} \\ _Paul D. Hanna_, Jun 06 2007
%Y Cf. A000108, A001764, A007226, A130523.
%K nonn
%O 1,2
%A _Martin Klazar_
%E More terms from _Paul Barry_, Nov 05 2006
|
