A classic proof of a recurrence for a very classical sequence

DOI10.1006/JCTA.1997.2814MaRDI QIDQ1374205zbMATH OpenOpenAlexFDO

Authors Doron Zeilberger, Dominique Foata

Publication date 2 December 1997

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9805015

zbMATH Keywords

bijection Schröder numbers well-weighted trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05)

Abstract: By practicing the philosophy of our beloved late master, Marco Schutzenberger, to whose memory this article is dedicated, we give an insightful bijective proof of the three-term recurrence satisfied by the Hipparchus-Schroeder numbers 1,1,3,11,45,197,903, ...

Review text

The Schröder numbers \(s(n)\) satisfy the recurrence \(3(2n-1)s(n)= (n+1)s(n+1)+ (n-2)s(n- 1)\), \(n\geq 2\), with \(s(1)= s(2)=1\). The authors give a direct combinatorial proof of the recurrence by establishing a bijection from the set \(\{1,2,3\}\times\text{PT}(n)\) onto the disjoint union \(\text{LT}(n+ 1)\dot\cup\text{IT}(n- 1)\) where \(\text{PT}(n)\), \(\text{LT}(n)\), \(\text{IT}(n)\) are the sets of pointed, leaf-pointed and interior pointed well-weighted trees with \(n\) leaves respectively.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: A classic proof of a recurrence for a very classical sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374205)