Source author record

Heesung Shin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AG math.AT

Catalog footprint

Research overview

17works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On Delannoy paths without peaks and valleys

A lattice path is called \emph{Delannoy} if its every step belongs to $\left\{N, E, D\right\}$ , where $N=(0,1)$ , $E=(1,0)$ , and $D=(1,1)$ steps. \emph{Peak}, \emph{valley}, and \emph{deep valley} mean $NE$ , $EN$ , and $EENN$ on the lattice path, respectively. In this paper, we find a bijection between $\mathcal{P}_{n,m}(NE, EN)$ and a specific subset of ${\mathcal{P}_{n,m}}(D, EENN)$ , where $\mathcal{P}_{n,m}(NE, EN)$ is the set of Delannoy paths from the origin to the points $(n,m)$ without peaks and valleys and ${\mathcal{P}_{n,m}}(D, EENN)$ is the set of Delannoy lattice paths from the origin to the points $(n,m)$ without diagonal steps and deep valleys. We also enumerate the number of Delannoy paths without peaks and valleys on the restricted region $\left\{ (x,y) \in \mathbb{Z}^2 : y \ge k x \right\}$ for a positive integer $k$ .

preprint2020arXiv

More bijections for Entringer and Arnold families

The Euler number $E_n$ (resp. Entringer number $E_{n,k}$ ) enumerates the alternating (down-up) permutations of $\{1,\dots,n\}$ (resp. starting with $k$ ). The Springer number $S_n$ (resp. Arnold number $S_{n,k}$ ) enumerates the type $B$ alternating permutations (resp. starting with $k$ ). In this paper, using bijections we first derive the counterparts in {\em André permutations} and {\em Simsun permutations} for the Entringer numbers $(E_{n,k})$ , and then the counterparts in {\em signed André permutations} and {\em type $B$ increasing 1-2 trees} for the Arnold numbers $(S_{n,k})$ .

preprint2018arXiv

Refined enumeration of vertices among all rooted ordered $d$ -trees

In this paper we enumerate the cardinalities for the set of all vertices of outdegree $\ge k$ at level $\ge \ell$ among all rooted ordered $d$ -trees with $n$ edges. Our results unite and generalize several previous works in the literature.

preprint2017arXiv

Enumerations of vertices among all rooted ordered trees with levels and degrees

In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree $k$ at level $\ell$ , (ii) non-first-children of degree $k$ at level $\ell-1$ , (iii) leaves having $k-1$ elder siblings at level $\ell$ , and (iv) non-leaves of outdegree $k$ at level $\ell-1$ . Our results unite and generalize several previous works in the literature.

preprint2015arXiv

Symmetric unimodal expansions of excedances in colored permutations

We consider several generalizations of the classical $γ$ -positivity of Eulerian polynomials (and their derangement analogues) using generating functions and combinatorial theory of continued fractions. For the symmetric group, we prove an expansion formula for inversions and excedances as well as a similar expansion for derangements. We also prove the $γ$ -positivity for Eulerian polynomials for derangements of type $B$ . More general expansion formulae are also given for Eulerian polynomials for $r$ -colored derangements. Our results answer and generalize several recent open problems in the literature.

preprint2013arXiv

A refined enumeration of $p$ -ary labeled trees

Let $\mathcal{T}^{(p)}_n$ be the set of $p$ -ary labeled trees on $\{1,2,\dots,n\}$ . A maximal decreasing subtree of an $p$ -ary labeled tree is defined by the maximal $p$ -ary subtree from the root with all edges being decreasing. In this paper, we study a new refinement $\mathcal{T}^{(p)}_{n,k}$ of $\mathcal{T}^{(p)}_n$ , which is the set of $p$ -ary labeled trees whose maximal decreasing subtree has $k$ vertices.

preprint2012arXiv

A refinement for ordered labeled trees

Let $\mathcal{O}_n$ be the set of ordered labeled trees on ${0,...,n}$ . A maximal decreasing subtree of an ordered labeled tree is defined by the maximal ordered subtree from the root with all edges being decreasing. In this paper, we study a new refinement $\mathcal{O}_{n,k}$ of $\mathcal{O}_n$ , which is the set of ordered labeled trees whose maximal decreasing subtree has $k+1$ vertices.

preprint2012arXiv

Annular noncrossing permutations and minimal transitive factorizations

We give two combinatorial proofs of Goulden and Jackson's formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type $B$ .

preprint2012arXiv

On the enumeration of rooted trees with fixed size of maximal decreasing trees

Let $\T_{n}$ be the set of rooted labeled trees on $\set{0,...,n}$ . A maximal decreasing subtree of a rooted labeled tree is defined by the maximal subtree from the root with all edges being decreasing. In this paper, we study a new refinement $\T_{n,k}$ of $\T_n$, which is the set of rooted labeled trees whose maximal decreasing subtree has $k+1$ vertices.

preprint2012arXiv

Signed a-polynomials of graphs and Poincaré polynomials of real toric manifolds

Recently, Choi and Park introduced an invariant of a finite simple graph, called signed a-number, arising from computing certain topological invariants of some specific kinds of real toric manifolds. They also found the signed a-numbers of path graphs, cycle graphs, complete graphs, and star graphs. We introduce a signed a-polynomial which is a generalization of the signed a-number and gives a-, b-, and c-numbers. The signed a-polynomial of a graph $G$ is related to the Poincaré polynomial $P_{M(G)}(z)$ , which is the generating function for the Betti numbers of the real toric manifold $M(G)$ . We give the generating functions for the signed a-polynomials of not only path graphs, cycle graphs, complete graphs, and star graphs, but also complete bipartite graphs and complete multipartite graphs. As a consequence, we find the Euler characteristic number and the Betti numbers of the real toric manifold $M(G)$ for complete multipartite graphs $G$ .

preprint2012arXiv

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

This paper was motivated by a conjecture of Brändén (European J. Combin. \textbf{29} (2008), no.~2, 514--531) about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a $(p,q)$ -analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The $(p,q)$ -analogue unifies and generalizes our recent results (European J. Combin. \textbf{31} (2010), no.~7, 1689--1705.) and that of Josuat-Vergès (European J. Combin. \textbf{31} (2010), no.~7, 1892--1906).

preprint2010arXiv

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set $\set{1,2,\ldots,n}$ , the local direction of each edge $(i\,j)$ is from $i$ to $j$ if $i<j$ . For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence $λ= 1^{e_1}2^{e_2} \ldots$ of a tree on the vertex set $\set{1,2,\ldots,n}$ is a partition of $n-1$ . We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a $q$ -multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.

preprint2010arXiv

A refined bijection between alternating permutations and 0-1-2 increasing trees

We construct a refined bijection $ϕ$ between alternating permutations and 0-1-2 increasing trees with degree at most 2. It satisfies that the first element of alternating permutation $π$ is equal to the first vertex in $ϕ(π)$ in the postorder.

preprint2010arXiv

Bijections for Entringer families

André proved that the number of alternating permutations on $\{1, 2, \dots, n\}$ is equal to the Euler number $E_n$ . A refinement of André's result was given by Entringer, who proved that counting alternating permutations according to the first element gives rise to Seidel's triangle $(E_{n,k})$ for computing the Euler numbers. In a series of papers, using generating function method and induction, Poupard gave several further combinatorial interpretations for $E_{n,k}$ both in alternating permutations and increasing trees. Kuznetsov, Pak, and Postnikov have given more combinatorial interpretations of $E_{n,k}$ in the model of trees. The aim of this paper is to provide bijections between the different models for $E_{n,k}$ as well as some new interpretations. In particular, we give the first explicit one-to-one correspondence between Entringer's alternating permutation model and Poupard's increasing tree model.

preprint2010arXiv

The $q$ -tangent and $q$ -secant numbers via continued fractions

It is well known that the $(-1)$ -evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). Recently, two distinct $q$ -analogues of the latter result have been discovered by Foata and Han, and Josuat-Vergès, respectively. In this paper, we will prove some general continued fractions expansions formulae, which permits us to give a unified treatment of Josuat-Vergès' two formulae and also to derive a new $q$ -analogue of the aforementioned formulae. Our approach is based on a $(p,q)$ -analogue of tangent and secant numbers via continued fractions and also the generating function of permutations with respect to the quintuple statistic consisting of fixed point number, weak excedance number, crossing number, nesting number and inversion number. We also give a combinatorial proof of Josuat-Vergès' formulae by using a new linear model of derangements.

preprint2009arXiv

An involution for symmetry of hook length and part length of partitions

A {\em pointed partition} of $n$ is a pair $(λ, v)$ where $λ\vdash n$ and $v$ is a cell in its Ferrers diagram. We construct an involution on pointed partitions of $n$ exchanging "hook length" and "part length". This gives a bijective proof of a recent result of Bessenrodt and Han.

preprint2005arXiv

A Generalized Enumeration of Labeled Trees and Reverse Prüfer Algorithm

A {\em leader} of a tree $T$ on $[n]$ is a vertex which has no smaller descendants in $T$ . Gessel and Seo showed $$\sum_{T \in \mathcal{T}_n}u^\text{(# of leaders in $T$)} c^\text{(degree of 1 in $T$)}=u P_{n-1}(1,u,cu),$$ which is a generalization of Cayley formula, where $\mathcal{T}_n$ is the set of trees on $[n]$ and $P_n(a,b,c)=c\prod_{i=1}^{n-1}(ia+(n-i)b+c).$ Using a variation of Prüfer code which is called a {\em RP-code}, we give a simple bijective proof of Gessel and Seo's formula.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Heesung Shin

Research overview

Is this your work?

17 publications

On Delannoy paths without peaks and valleys

More bijections for Entringer and Arnold families

Refined enumeration of vertices among all rooted ordered $d$ -trees

Enumerations of vertices among all rooted ordered trees with levels and degrees

Symmetric unimodal expansions of excedances in colored permutations

A refined enumeration of $p$ -ary labeled trees

A refinement for ordered labeled trees

Annular noncrossing permutations and minimal transitive factorizations

On the enumeration of rooted trees with fixed size of maximal decreasing trees

Signed a-polynomials of graphs and Poincaré polynomials of real toric manifolds

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

A bijective enumeration of labeled trees with given indegree sequence

A refined bijection between alternating permutations and 0-1-2 increasing trees

Bijections for Entringer families

The $q$ -tangent and $q$ -secant numbers via continued fractions

An involution for symmetry of hook length and part length of partitions

A Generalized Enumeration of Labeled Trees and Reverse Prüfer Algorithm

See the researcher in context

Building this map preview

Heesung Shin

Research overview

Is this your work?

17 publications

On Delannoy paths without peaks and valleys

More bijections for Entringer and Arnold families

Refined enumeration of vertices among all rooted ordered ddd-trees

Enumerations of vertices among all rooted ordered trees with levels and degrees

Symmetric unimodal expansions of excedances in colored permutations

A refined enumeration of ppp-ary labeled trees

A refinement for ordered labeled trees

Annular noncrossing permutations and minimal transitive factorizations

On the enumeration of rooted trees with fixed size of maximal decreasing trees

Signed a-polynomials of graphs and Poincaré polynomials of real toric manifolds

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

A bijective enumeration of labeled trees with given indegree sequence

A refined bijection between alternating permutations and 0-1-2 increasing trees

Bijections for Entringer families

The qqq-tangent and qqq-secant numbers via continued fractions

An involution for symmetry of hook length and part length of partitions

A Generalized Enumeration of Labeled Trees and Reverse Prüfer Algorithm

See the researcher in context

Building this map preview

Refined enumeration of vertices among all rooted ordered $d$ -trees

A refined enumeration of $p$ -ary labeled trees

The $q$ -tangent and $q$ -secant numbers via continued fractions