A007857 Number of independent sets in rooted plane trees on n nodes.

1, 2, 8, 37, 184, 959, 5172, 28641, 162008, 932503, 5445934, 32197334, 192357788, 1159603592, 7045356104, 43098733353, 265240985112, 1641100253735, 10202295895890, 63696629668980, 399216722146770, 2510833297584165

Offset: 1

Author

Martin Klazar

Keywords

• nonn

Comments

Equals the main diagonal of square array A130523. - Paul D. Hanna, Jun 06 2007

From Petros Hadjicostas, Aug 06 2020: (Start)

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

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.

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.

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)

Links

• M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics, 18(2) (1997), 195-210.
• M. Klazar, Addendum Twelve Countings with Rooted Plane Trees, European Journal of Combinatorics, 18(6) (1997), 739-740.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A000108, A001764, A007226, A130523.

Programs

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

Formula

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

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

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

Extensions

More terms from Paul Barry, Nov 05 2006