Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

Jang Soo Kim

doi:10.1007/s00026-013-0182-9

Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

Jang Soo Kim

University of Minnesota Twin Cities

Research output: Contribution to journal › Article › peer-review

Abstract

Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . ., n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.

Original language	English
Pages (from-to)	339-352
Number of pages	14
Journal	Annals of Combinatorics
Volume	17
Issue number	2
DOIs	https://doi.org/10.1007/s00026-013-0182-9
State	Published - Jun 2013
Externally published	Yes

Keywords

bijections
maximal decreasing subtrees
rooted trees

Access to Document

10.1007/s00026-013-0182-9

Cite this

@article{5d071b4b8d5c430d95a93aa3ee5c92b1,

title = "Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees",

abstract = "Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . ., n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.",

keywords = "bijections, maximal decreasing subtrees, rooted trees",

author = "Kim, \{Jang Soo\}",

year = "2013",

month = jun,

doi = "10.1007/s00026-013-0182-9",

language = "English",

volume = "17",

pages = "339--352",

journal = "Annals of Combinatorics",

issn = "0218-0006",

publisher = "Birkhauser Verlag Basel",

number = "2",

}

TY - JOUR

T1 - Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

AU - Kim, Jang Soo

PY - 2013/6

Y1 - 2013/6

N2 - Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . ., n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.

AB - Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . ., n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.

KW - bijections

KW - maximal decreasing subtrees

KW - rooted trees

UR - https://www.scopus.com/pages/publications/84878202118

U2 - 10.1007/s00026-013-0182-9

DO - 10.1007/s00026-013-0182-9

M3 - Article

AN - SCOPUS:84878202118

SN - 0218-0006

VL - 17

SP - 339

EP - 352

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 2

ER -

Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this