서지주요정보
A refinement of numbers for trees and parking functions = 수형도와 주차 함수의 개수에 대한 세분화
서명 / 저자 A refinement of numbers for trees and parking functions = 수형도와 주차 함수의 개수에 대한 세분화 / Hee-Sung Shin.
저자명 Shin, Hee-Sung ; 신희성
발행사항 [대전 : 한국과학기술원, 2007].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8018551

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 07010

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

A $\emph{leader}$ of a tree $T$ is a vertex which has no smaller descendants in $T$. Gessel and Seo showed that $\displaystyle\sum_{T \in T_n}u^{(\# of leaders in T)}c^{(degree of 1 in T)} = u P_{n-1}(1,u,cu),$ which is a generalization of Cayley's formula, where $T_n$ is the set of trees on $[n]$ and $P_n(a,b,c) = c \displaystyle\prod_{i=1}^{n-1}(ia+(n-i)b+c).$ Using a variation of the Pr$\ddot{u}$fer code which is called an $\em{RP-code}$, we give a simple bijective proof of Gessel and Seo's formula. A car in a parking function is called $\emph{lucky}$ if it succeeds to park in its preferred space. Gessel and Seo also showed that $\displaystyle\sum_{P \in PF_n} u^{(\# of lucky cars in P)} = P_n(1,u,u),$ but this proof was not combinatorial. We construct the bijection $\varphi$ from forests to parking functions and give a bijective proof of it. We generalize it further using the bijection $\varphi$.

수형도의 $\emph{리더}v$는 수형도 안에서 점 $v$의 후손들이 모두 $v$보다 크다. 게셀과 서승현은 케일리의 공식의 일반화인 $\displaystyle\sum_{T \in T_n}u^{(T에서 리더의 개수)}c^{(T에서 1의 등급)} = u P_{n-1}(1,u,cu)$ 을 보였다. 여기서 $T_n$은 n개의 점으로 이루어진 수형도들의 집합이고, $P_n(a,b,c) = c\displaystyle\prod_{i=1}^{n-1}(ia+(n-i)b+c)$ 이다. $\emph{RP-부호}$라고 부르는 프뤼퍼 부호의 변형을 이용하여, 게셀과 서승현의 공식의 간단한 전단사적 증명을 보인다. 주차함수에서 어떤 차가 그 차가 원하는 곳에 주차한다면, 그 차는 $\emph{운 좋다}$고 한다. 게셀과 서승현은 $\displaystyle\sum_{P \in PF_n} u^{(P에서 운 좋은 차의 개수)} = P_n(1,u,u)$ 을 보였지만, 이것은 조합론적인 증명은 아니었다. 수형도와 주차함수의 일대일대응 함수 $\varphi$를 만들고, 공식의 전단사적 증명을 보인다. 또한 일대일대응 함수 $\varphi$로 공식을 일반화한다.

서지기타정보

서지기타정보
청구기호 {DMA 07010
형태사항 v, 42 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 신희성
지도교수의 영문표기 : Dong-Su Kim
지도교수의 한글표기 : 김동수
수록잡지명 : "A generalized enumeration of labeled trees and reverse pr\\\"ufer algorithm". Journal of combinatorial theory, series A, (2007)
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 Reference : p. 41-42
주제 refinement, numbers, trees, parking functions
세분화, 개수, 수형도, 주차 함수
QR CODE qr code