Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLabeled Ballot Paths and the Springer Numbers
289
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The Springer numbers are defined in connection with the irreducible root systems of type $B_n$, which also arise as the generalized Euler and class numbers introduced by Shanks. Combinatorial interpretations of the Springer numbers have been found by Purtill in terms of Andre signed permutations, and by Arnold in terms of snakes of type $B_n$. We introduce the inversion code of a snake of type $B_n$ and establish a bijection between labeled ballot paths of length n and snakes of type $B_n$. Moreover, we obtain the bivariate generating function for the number B(n,k) of labeled ballot paths starting at (0,0) and ending at (n,k). Using our bijection, we find a statistic $alpha$ such that the number of snakes $pi$ of type $B_n$ with $alpha(pi)=k$ equals B(n,k). We also show that our bijection specializes to a bijection between labeled Dyck paths of length 2n and alternating permutations on [2n].
rate research
Read More
A ballot permutation is a permutation {pi} such that in any prefix of {pi} the descent number is not more than the ascent number. In this article, we obtained a formula in close form for the multivariate generating function of {A(n,d,j)}, which denote the number of permutations of length n with d descents and j as the first letter. Besides, by a series of calculations with generatingfunctionology, we confirm a recent conjecture of Wang and Zhang for ballot permutations.
We study a polynomial sequence $C_n(x|q)$ defined as a solution of a $q$-difference equation. This sequence, evaluated at $q$-integers, interpolates Carlitz-Riordans $q$-ballot numbers. In the basis given by some kind of $q$-binomial coefficients, the coefficients are again some $q$-ballot numbers. We obtain in a combinatorial way another curious recurrence relation for these polynomials.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
The total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of cycles and paths.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
