Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We count the number of vertices with given outdegree in plane trees and k-ary trees, and get the following results: the total number of vertices of outdegree i among all plane trees with n edges is \({2n-i-1 \atopwithdelims ()n-1}\); the total number of vertices of degree i among all plane trees with n edges is twice this number; and the total number of vertices of outdegree i among all k-ary trees with n edges is \({k\atopwithdelims ()i}{kn\atopwithdelims ()n-i}\). For all these results we give bijective proofs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Deutsch, E., Shapiro, L.: A survey of the Fine numbers. Discrete Math. 241, 241–265 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  2. Du, R.R.X., He, J., Yun, X.: Counting vertices in plane and k-ary trees with given outdegree. arXiv:1501.07468 [math.CO]

  3. Erdélyi, A., Etherington, I.M.H.: Some problems of non-associative combinations (2). Edinb. Math. Notes 32, 7–12 (1940)

    Article  MathSciNet  MATH  Google Scholar 

  4. Etherington, I.M.H.: Some problems of non-associative combinations (1). Edinb. Math. Notes 32, 1–6 (1940)

    Article  MathSciNet  MATH  Google Scholar 

  5. Eu, S., Liu, S., Yeh, Y.: Odd or even on plane trees. Discrete Math. 281, 189–196 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Eu, S., Seo, S., Shin, H.: Enumerations of vertices among all rooted ordered trees with levels and degrees. Discrete Math. 340(9), 2123–2129 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  7. Knuth, D.E.: The Art of Computer Programming. Fundamental Algorithms, vol. 1. Addison-Wesley, Reading (1968)

    MATH  Google Scholar 

  8. Raney, G.N.: Functional composition patterns and power series reversion. Trans. Am. Math. Soc. 94, 441–451 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  9. Sloane, N.J.A.: Online Encyclopedia of Integer Sequence, published electronically at http://oeis.org

  10. Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)

    Book  MATH  Google Scholar 

Download references

Acknowledgements

This work is partially supported by National Natural Science Foundation of China (No. 11871223) and the Science and Technology Commission of Shanghai Municipality (No. 18ZR1411700 and No. 18dz2271000).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Shanghai Key Laboratory of PMMP, East China Normal University, 500 Dongchuan Road, Shanghai, 200241, People’s Republic of China

    Rosena R. X. Du, Jia He & Xueli Yun

Authors
  1. Rosena R. X. Du
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Jia He
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Xueli Yun
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Rosena R. X. Du.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Du, R.R.X., He, J. & Yun, X. Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees. Graphs and Combinatorics 35, 221–229 (2019). https://doi.org/10.1007/s00373-018-1975-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-018-1975-8

Keywords

Mathematics Subject Classification