Source author record

Zhicong Lin

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

20works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Proof of a Conjecture on Young Tableaux with Walls

Banderier, Marchal, and Wallner considered Young tableaux with walls, which are similar to standard Young tableaux, except that local decreases are allowed at some walls. In this work, we prove a conjecture of Fuchs and Yu concerning the enumeration of two classes of three-row Young tableaux with walls. Combining with the work by Chang, Fuchs, Liu, Wallner, and Yu leads to the verification of a conjecture on tree-child networks proposed by Pons and Batle. This conjecture was regarded as a specific and challenging problem in the Phylogenetics community until it was finally resolved by the present work.

preprint2022arXiv

Combinatorics of Integer Partitions With Prescribed Perimeter

We prove that the number of even parts and the number of times that parts are repeated have the same distribution over integer partitions with a fixed perimeter. This refines Straub's analog of Euler's Odd-Distinct partition theorem. We generalize the two concerned statistics to these of the part-difference less than $d$ and the parts not congruent to $1$ modulo $d+1$ and prove a distribution inequality, that has a similar flavor as Alder's ex-conjecture, over partitions with a prescribed perimeter. Both of our results are proved analytically and combinatorially.

preprint2021arXiv

A decomposition of ballot permutations, pattern avoidance and Gessel walks

A permutation whose any prefix has no more descents than ascents is called a ballot permutation. In this paper, we present a decomposition of ballot permutations that enables us to construct a bijection between ballot permutations and odd order permutations, which proves a set-valued extension of a conjecture due to Spiro using the statistic of peak values. This bijection also preserves the neighbors of the largest letter in permutations and thus resolves a refinement of Spiro' s conjecture proposed by Wang and Zhang. Our decomposition can be extended to well-labelled positive paths, a class of generalized ballot permutations arising from polytope theory, that were enumerated by Bernardi, Duplantier and Nadeau. We will also investigate the enumerative aspect of ballot permutations avoiding a single pattern of length 3 and establish a connection between 213-avoiding ballot permutations and Gessel walks.

preprint2020arXiv

$k$ -arrangements, statistics and patterns

The $k$ -arrangements are permutations whose fixed points are $k$ -colored. We prove enumerative results related to statistics and patterns on $k$ -arrangements, confirming several conjectures by Blitvić and Steingrímsson. In particular, one of their conjectures regarding the equdistribution of the number of descents over the derangement form and the permutation form of $k$ -arrangements is strengthened in two interesting ways. Moreover, as one application of the so-called Decrease Value Theorem, we calculate the generating function for a symmetric pair of Eulerian statistics over permutations arising in our study.

preprint2020arXiv

Around the $q$ -binomial-Eulerian polynomials

We find a combinatorial interpretation of Shareshian and Wachs' $q$ -binomial-Eulerian polynomials, which leads to an alternative proof of their $q$ - $γ$ -positivity using group actions. Motivated by the sign-balance identity of Désarménien--Foata--Loday for the $(\mathrm{des}, \mathrm{inv})$ -Eulerian polynomials, we further investigate the sign-balance of the $q$ -binomial-Eulerian polynomials. We show the unimodality of the resulting signed binomial-Eulerian polynomials by exploiting their continued fraction expansion and making use of a new quadratic recursion for the $q$ -binomial-Eulerian polynomials. We finally use the method of continued fractions to derive a new $(p,q)$ -extension of the $γ$ -positivity of binomial-Eulerian polynomials which involves crossings and nestings of permutations.

preprint2020arXiv

On $\underline{12}0$ -avoiding inversion and ascent sequences

Recently, Yan and the first named author investigated systematically the enumeration of inversion or ascent sequences avoiding vincular patterns of length $3$ , where two of the three letters are required to be adjacent. They established many connections with familiar combinatorial families and proposed several interesting conjectures. The objective of this paper is to address two of their conjectures concerning the enumeration of $\underline{12}0$ -avoiding inversion or ascent sequences.

preprint2020arXiv

Plateaux on generalized Stirling permutations and partial $γ$ -positivity

We prove that the enumerative polynomials of generalized Stirling permutations by the statistics of plateaux, descents and ascents are partial $γ$ -positive. Specialization of our result to the Jacobi-Stirling permutations confirms a recent partial $γ$ -positivity conjecture due to Ma, Yeh and the second named author. Our partial $γ$ -positivity expansion, as well as a combinatorial interpretation for the corresponding $γ$ -coefficients, are obtained via the machine of context-free grammars and a group action on generalized Stirling permutations. Besides, we also provide an alternative approach to the partial $γ$ -positivity from the stability of certain multivariate polynomials.

preprint2020arXiv

Refined restricted inversion sequences

Recently, the study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck independently. Motivated by their works and a double Eulerian equidistribution due to Foata (1977), we investigate several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by {\em Catalan}, {\em Large Schröder}, {\em Baxter} and {\em Euler} numbers. One of the two highlights of our results is a fascinating bijection between $000$ -avoiding inversion sequences and Simsun permutations, which together with Foata's V- and S-codes, provide a proof of a restriced double Eulerian equdistribution. The other one is a refinement of a conjecture due to Martinez and Savage that the cardinality of $\I_n(\geq,\geq,>)$ is the $n$ -th Baxter number, which is proved via the so-called {\em obstinate kernel method} developed by Bousquet-Mélou.

preprint2020arXiv

Refined Wilf-equivalences by Comtet statistics

We launch a systematic study of the refined Wilf-equivalences by the statistics $\mathsf{comp}$ and $\mathsf{iar}$ , where $\mathsf{comp}(π)$ and $\mathsf{iar}(π)$ are the number of components and the length of the initial ascending run of a permutation $π$ , respectively. As Comtet was the first one to consider the statistic $\mathsf{comp}$ in his book {\em Analyse combinatoire}, any statistic equidistributed with $\mathsf{comp}$ over a class of permutations is called by us a {\em Comtet statistic} over such class. This work is motivated by a triple equidistribution result of Rubey on $321$ -avoiding permutations, and a recent result of the first and third authors that $\mathsf{iar}$ is a Comtet statistic over separable permutations. Some highlights of our results are: (1) Bijective proofs of the symmetry of the double Comtet distribution $(\mathsf{comp},\mathsf{iar})$ over several Catalan and Schröder classes, preserving the values of the left-to-right maxima. (2) A complete classification of $\mathsf{comp}$ - and $\mathsf{iar}$ -Wilf-equivalences for length $3$ patterns and pairs of length $3$ patterns. Calculations of the $(\mathsf{des},\mathsf{iar},\mathsf{comp})$ generating functions over these pattern avoiding classes and separable permutations. (3) A further refinement by the Comtet statistic $\mathsf{iar}$ , of Wang's recent descent-double descent-Wilf equivalence between separable permutations and $(2413,4213)$ -avoiding permutations.

preprint2020arXiv

Signed Euler-Mahonian identities

A relationship between signed Eulerian polynomials and the classical Eulerian polynomials on $\mathfrak{S}_n$ was given by Désarménien and Foata in 1992, and a refined version, called signed Euler-Mahonian identity, together with a bijective proof were proposed by Wachs in the same year. By generalizing this bijection, in this paper we extend the above results to the Coxeter groups of types $B_n$ , $D_n$ , and the complex reflection group $G(r,1,n)$ , where the `sign' is taken to be any one-dimensional character. Some obtained identities can be further restricted on some particular set of permutations. We also derive some new interesting sign-balance polynomials for types $B_n$ and $D_n$ .

preprint2016arXiv

A sextuple equidistribution arising in Pattern Avoidance

We construct an intriguing bijection between $021$ -avoiding inversion sequences and $(2413,4213)$ -avoiding permutations, which proves a sextuple equidistribution involving double Eulerian statistics. Two interesting applications of this result are also presented. Moreover, this result inspires us to characterize all permutation classes that avoid two patterns of length $4$ whose descent polynomial equals that of separable permutations.

preprint2015arXiv

The $γ$ -positivity of basic Eulerian polynomials via group actions

We provide combinatorial interpretation for the $γ$ -coefficients of the basic Eulerian polynomials that enumerate permutations by the excedance statistic and the major index as well as the corresponding $γ$ -coefficients for derangements. Our results refine the classical $γ$ -positivity results for the Eulerian polynomials and the derangement polynomials. The main tools are Brändén's modified Foata--Strehl action on permutations and the recent triple statistic (des, rix,aid) equidistibuted with (exc, fix, maj).

preprint2013arXiv

Graph homomorphisms between trees

In this paper we study several problems concerning the number of homomorphisms of trees. We give an algorithm for the number of homomorphisms from a tree to any graph by the Transfer-matrix method. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization of Bollobás and Tyomkyn's result concerning the number of walks in trees. Some other highlights of the paper are the following. Denote by $\hom(H,G)$ the number of homomorphisms from a graph $H$ to a graph $G$ . For any tree $T_m$ on $m$ vertices we give a general lower bound for $\hom(T_m,G)$ by certain entropies of Markov chains defined on the graph $G$ . As a particular case, we show that for any graph $G$ , $\exp(H_λ(G))λ^{m-1}\leq\hom(T_m,G),$ where $λ$ is the largest eigenvalue of the adjacency matrix of $G$ and $H_λ(G)$ is a certain constant depending only on $G$ which we call the spectral entropy of $G$ . In the particular case when $G$ is the path $P_n$ on $n$ vertices, we prove that $\hom(P_m,P_n)\leq \hom(T_m,P_n)\leq \hom(S_m,P_n),$ where $T_m$ is any tree on $m$ vertices, and $P_m$ and $S_m$ denote the path and star on $m$ vertices, respectively. We also show that if $T_m$ is any fixed tree and $\hom(T_m,P_n)>\hom(T_m,T_n),$ for some tree $T_n$ on $n$ vertices, then $T_n$ must be the tree obtained from a path $P_{n-1}$ by attaching a pendant vertex to the second vertex of $P_{n-1}$ . All the results together enable us to show that $$ |\End(P_m)|\leq|\End(T_m)|\leq|\End(S_m)|, $$ where $\End(T_m)$ is the set of all endomorphisms of $T_m$ (homomorphisms from $T_m$ to itself).

preprint2013arXiv

On some colored Eulerian quasisymmetric functions

Recently, Hyatt introduced some colored Eulerian quasisymmetric function to study the joint distribution of excedance number and major index on colored permutation groups. We show how Hyatt's generating function formula for the fixed point colored Eulerian quasisymmetric functions can be deduced from the Decrease value theorem of Foata and Han. Using this generating function formula, we prove two symmetric function generalizations of the Chung-Graham-Knuth symmetrical Eulerian identity for some flag Eulerian quasisymmetric functions, which are specialized to the flag excedance numbers. Combinatorial proofs of those symmetrical identities are also constructed. We also study some other properties of the flag Eulerian quasisymmetric functions. In particular, we confirm a recent conjecture of Mongelli [Journal of Combinatorial Theory, Series A, 120 (2013) 1216--1234] about the unimodality of the generating function of the flag excedances over the type B derangements. Moreover, colored versions of the hook factorization and admissible inversions of permutations are found, as well as a new recurrence formula for the $(\maj-\exc,\fexc)$- $q$ -Eulerian polynomials. We introduce a colored analog of Rawlings major index on colored permutations and obtain an interpretation of the colored Eulerian quasisymmetric functions as sums of some fundamental quasisymmetric functions related with them, by applying Stanley's $P$ -partition theory and a decomposition of the Chromatic quasisymmetric functions due to Shareshian and Wachs.

preprint2013arXiv

On some generalized $q$ -Eulerian polynomials

The $(q,r)$ -Eulerian polynomials are the $(\maj-$$\exc,\fix,\exc)$ enumerative polynomials of permutations. Using Shareshian and Wachs' exponential generating function of these Eulerian polynomials, Chung and Graham proved two symmetrical $q$ -Eulerian identities and asked for bijective proofs. We provide such proofs using Foata and Han's three-variable statistic $(\inv-$$\lec,\pix,\lec)$. We also prove a new recurrence formula for the $(q,r)$ -Eulerian polynomials and study a $q$ -analogue of Chung and Graham's restricted descent polynomials. In particular, we obtain a generalized symmetrical identity for these restricted $q$ -Eulerian polynomials with a combinatorial proof.

preprint2013arXiv

On the descent polynomial of signed multipermutations

Motivated by a conjecture of Savage and Visontai about the equidistribution of the descent statistic on signed permutations of the multiset $\{1,1,2,2,\ldots,n,n\}$ and the ascent statistic on $(1,4,3,8,\ldots,2n-1,4n)$ -inversion sequences, we investigate the descent polynomial of the signed permutations of a general multiset. We obtain a factorial generating function formula for a $q$ -analog of these descent polynomials and apply it to show that they have only real roots. Two different proofs of the conjecture of Savage and Visontai are provided.

preprint2013arXiv

Positivity properties of Jacobi-Stirling numbers and generalized Ramanujan polynomials

Generalizing recent results of Egge and Mongelli, we show that each diagonal sequence of the Jacobi-Stirling numbers $\js(n,k;z)$ and $\JS(n,k;z)$ is a Pólya frequency sequence if and only if $z\in [-1, 1]$ and study the $z$ -total positivity properties of these numbers. Moreover, the polynomial sequences $$\biggl\{\sum_{k=0}^n\JS(n,k;z)y^k\biggr\}_{n\geq 0}\quad \text{and} \quad \biggl\{\sum_{k=0}^n\js(n,k;z)y^k\biggr\}_{n\geq 0}$$ are proved to be strongly $\{z,y\}$ -log-convex. In the same vein, we extend a recent result of Chen et al. about the Ramanujan polynomials to Chapoton's generalized Ramanujan polynomials. Finally, bridging the Ramanujan polynomials and a sequence arising from the Lambert $W$ function, we obtain a neat proof of the unimodality of the latter sequence, which was proved previously by Kalugin and Jeffrey.

preprint2012arXiv

A symmetrical q-Eulerian identity

We find a $q$ -analog of the following symmetrical identity involving binomial coefficients $\binom{n}{m}$ and Eulerian numbers $A_{n,m}$ , due to Chung, Graham and Knuth [{\it J. Comb.}, {\bf 1} (2010), 29--38]: {equation*} \sum_{k\geq 0}\binom{a+b}{k}A_{k,a-1}=\sum_{k\geq 0}\binom{a+b}{k}A_{k,b-1}. {equation*} We give two proofs, using generating function and bijections, respectively.

preprint2012arXiv

Jacobi-Stirling polynomials and $P$ -partitions

We investigate the diagonal generating function of the Jacobi-Stirling numbers of the second kind $ \JS(n+k,n;z)$ by generalizing the analogous results for the Stirling and Legendre-Stirling numbers. More precisely, letting $\JS(n+k,n;z)=p_{k,0}(n)+p_{k,1}(n)z+...+p_{k,k}(n)z^k$, we show that $(1-t)^{3k-i+1}\sum_{n\geq0}p_{k,i}(n)t^n$ is a polynomial in $t$ with nonnegative integral coefficients and provide combinatorial interpretations of the coefficients by using Stanley's theory of $P$ -partitions.

preprint2011arXiv

On the number of congruence classes of paths

Let $P_n$ denote the undirected path of length $n-1$ . The cardinality of the set of congruence classes induced by the graph homomorphisms from $P_n$ onto $P_k$ is determined. This settles an open problem of Michels and Knauer (Disc. Math., 309\ (2009)\ 5352-5359). Our result is based on a new proven formula of the number of homomorphisms between paths.

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.

Zhicong Lin

Research overview

Is this your work?

20 publications

Proof of a Conjecture on Young Tableaux with Walls

Combinatorics of Integer Partitions With Prescribed Perimeter

A decomposition of ballot permutations, pattern avoidance and Gessel walks

$k$ -arrangements, statistics and patterns

Around the $q$ -binomial-Eulerian polynomials

On $\underline{12}0$ -avoiding inversion and ascent sequences

Plateaux on generalized Stirling permutations and partial $γ$ -positivity

Refined restricted inversion sequences

Refined Wilf-equivalences by Comtet statistics

Signed Euler-Mahonian identities

A sextuple equidistribution arising in Pattern Avoidance

The $γ$ -positivity of basic Eulerian polynomials via group actions

Graph homomorphisms between trees

On some colored Eulerian quasisymmetric functions

On some generalized $q$ -Eulerian polynomials

On the descent polynomial of signed multipermutations

Positivity properties of Jacobi-Stirling numbers and generalized Ramanujan polynomials

A symmetrical q-Eulerian identity

Jacobi-Stirling polynomials and $P$ -partitions

On the number of congruence classes of paths

See the researcher in context

Building this map preview

Zhicong Lin

Research overview

Is this your work?

20 publications

Proof of a Conjecture on Young Tableaux with Walls

Combinatorics of Integer Partitions With Prescribed Perimeter

A decomposition of ballot permutations, pattern avoidance and Gessel walks

kkk-arrangements, statistics and patterns

Around the qqq-binomial-Eulerian polynomials

On 12‾0\underline{12}012​0-avoiding inversion and ascent sequences

Plateaux on generalized Stirling permutations and partial γγγ-positivity

Refined restricted inversion sequences

Refined Wilf-equivalences by Comtet statistics

Signed Euler-Mahonian identities

A sextuple equidistribution arising in Pattern Avoidance

The γγγ-positivity of basic Eulerian polynomials via group actions

Graph homomorphisms between trees

On some colored Eulerian quasisymmetric functions

On some generalized qqq-Eulerian polynomials

On the descent polynomial of signed multipermutations

Positivity properties of Jacobi-Stirling numbers and generalized Ramanujan polynomials

A symmetrical q-Eulerian identity

Jacobi-Stirling polynomials and PPP-partitions

On the number of congruence classes of paths

See the researcher in context

Building this map preview

$k$ -arrangements, statistics and patterns

Around the $q$ -binomial-Eulerian polynomials

On $\underline{12}0$ -avoiding inversion and ascent sequences

Plateaux on generalized Stirling permutations and partial $γ$ -positivity

The $γ$ -positivity of basic Eulerian polynomials via group actions

On some generalized $q$ -Eulerian polynomials

Jacobi-Stirling polynomials and $P$ -partitions