BZPEER

preprint2024arXiv

Breaking Cycles, the Odd Versus the Even

In an award-winning expository article, V. Pozdnyakov and J.M. Steele gave a beautiful demonstration of the ramifications of a basic bijection for permutations. The aim of this note is to connect this correspondence to a seemingly unrelated problem concerning odd cycles and even cycles, arising in the combinatorial study of the Cayley continuants by E. Munarini and D. Torri. In extreme cases, one encounters two special classes of permutations of $2n$ elements with the same cardinality. A bijection of this appealing relation has been found by E. Sayag. A combinatorial study of permutations with only odd cycles has been carried out by M. Bóna, A. Mclennan and D. White. We find an intermediate structure which leads to a linkage between these two antipodal structures. A recursive setting reveals that everything boils down to only one trick -- breaking the cycles.

preprint2022arXiv

Cubic Equations Through the Looking Glass of Sylvester

One can hardly believe that there is still something to be said about cubic equations. To dodge this doubt, we will instead try and say something about Sylvester. He doubtless found a way of solving cubic equations. As mentioned by Rota, it was the only method in this vein that he could remember. We realize that in the generic case Sylvester's magnificent approach aimed at reduced cubic equations boils down to an easy identity expressing a cubic polynomial as a sum of two third powers of linear forms. This leads to Cardano's formula for cubic equations involving the third roots of unity.

preprint2015arXiv

Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences

Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of $P(x)^k Q(x)$ , for some Laurent polynomials $P(x)$ and $Q(x)$ in the variable $x$ with integer coefficients. Denoting such a sequence by $a_k$ , we obtain a general formula that determines the congruence class, modulo $p$ , of the indefinite sum $\sum_{k=0}^{rp -1} a_k$ , for {\it any} prime $p$ , and any positive integer $r$ , as a linear combination of sequences that satisfy linear recurrence (alias difference) equations with constant coefficients. This enables us (or rather, our computers) to automatically discover and prove congruence theorems for such partial sums. Moreover, we show that in many cases, the set of the residues is finite, regardless of the prime $p$ .

preprint2015arXiv

The Log-Behavior of $\sqrt[n]{p(n)}$ and $\sqrt[n]{p(n)/n}$

Let $p(n)$ denote the partition function. Desalvo and Pak proved the log-concavity of $p(n)$ for $n>25$ and the inequality $\frac{p(n-1)}{p(n)}\left(1+\frac{1}{n}\right)>\frac{p(n)}{p(n+1)}$ for $n>1$ . Let $r(n)=\sqrt[n]{p(n)/n}$ and $Δ$ be the difference operator respect to $n$ . Desalvo and Pak pointed out that their approach to proving the log-concavity of $p(n)$ may be employed to prove a conjecture of Sun on the log-convexity of $\{r(n)\}_{n\geq 61}$ , as long as one finds an appropriate estimate of $Δ^2 \log r(n-1)$ . In this paper, we obtain a lower bound for $Δ^2\log r(n-1)$ , leading to a proof of this conjecture. From the log-convexity of $\{r(n)\}_{n\geq61}$ and $\{\sqrt[n]{n}\}_{n\geq4}$ , we are led to a proof of another conjecture of Sun on the log-convexity of $\{\sqrt[n]{p(n)}\}_{n\geq27}$ . Furthermore, we show that $\lim\limits_{n \rightarrow +\infty}n^{\frac{5}{2}}Δ^2\log\sqrt[n]{p(n)}=3π/\sqrt{24}$ . Finally, by finding an upper bound of $Δ^2 \log\sqrt[n-1]{p(n-1)}$ , we prove an inequality on the ratio $\frac{\sqrt[n-1]{p(n-1)}}{\sqrt[n]{p(n)}}$ analogous to the above inequality on the ratio $\frac{p(n-1)}{p(n)}$ .

preprint2014arXiv

Automorphisms of the cycle prefix digraph

Cycle prefix digraphs have been proposed as an efficient model of symmetric interconnection networks for parallel architecture. It has been discovered that the cycle prefix networks have many attractive communication properties. In this paper, we determine the automorphism group of the cycle prefix digraphs. We show that the automorphism group of a cycle prefix digraph is isomorphic to the symmetric group on its underlying alphabet. Our method can be applied to other classes of graphs built on alphabets including the hypercube, the Kautz graph,and the de Bruijn graph.

preprint2014arXiv

Average Size of a Self-conjugate (s, t)-Core Partition

Armstrong, Hanusa and Jones conjectured that if $s,t$ are coprime integers, then the average size of an $(s,t)$ -core partition and the average size of a self-conjugate $(s,t)$ -core partition are both equal to $\frac{(s+t+1)(s-1)(t-1)}{24}$ . Stanley and Zanello showed that the average size of an $(s,s+1)$ -core partition equals $\binom{s+1}{3}/2$ . Based on a bijection of Ford, Mai and Sze between self-conjugate $(s,t)$ -core partitions and lattice paths in $\lfloor \frac{s}{2} \rfloor\times \lfloor \frac{t}{2}\rfloor$ rectangle, we obtain the average size of a self-conjugate $(s,t)$ -core partition as conjectured by Armstrong, Hanusa and Jones.

preprint2014arXiv

Context-free Grammars for Permutations and Increasing Trees

In this paper, we introduce the notion of a grammatical labeling to describe a recursive process of generating combinatorial objects based on a context-free grammar. For example, by labeling the ascents and descents of a Stirling permutation, we obtain a grammar for the second-order Eulerian polynomials. By using the grammar for $0$ - $1$ - $2$ increasing trees given by Dumont, we obtain a grammatical derivation of the generating function of the André polynomials obtained by Foata and Schützenberger, without solving a differential equation. We also find a grammar for the number $T(n,k)$ of permutations of $[n]=\{1,2,\ldots, n\}$ with $k$ exterior peaks, which was independently discovered by Ma. We demonstrate that Gessel's formula for the generating function of $T(n,k)$ can be deduced from this grammar. Moreover, by using grammars we show that the number of the permutations of $[n]$ with $k$ exterior peaks equals the number of increasing trees on $[n]$ with $2k+1$ vertices of even degree. A combinatorial proof of this fact is also presented.

preprint2014arXiv

Finite Differences of the Logarithm of the Partition Function

Let $p(n)$ denote the partition function. DeSalvo and Pak proved that $\frac{p(n-1)}{p(n)}\left(1+\frac{1}{n}\right)> \frac{p(n)}{p(n+1)}$ for $n\geq 2$ , as conjectured by Chen. Moreover, they conjectured that a sharper inequality $\frac{p(n-1)}{p(n)}\left( 1+\fracπ{\sqrt{24}n^{3/2}}\right) > \frac{p(n)}{p(n+1)}$ holds for $n\geq 45$ . In this paper, we prove the conjecture of Desalvo and Pak by giving an upper bound for $-Δ^{2} \log p(n-1)$ , where $Δ$ is the difference operator with respect to $n$ . We also show that for given $r\geq 1$ and sufficiently large $n$ , $(-1)^{r-1}Δ^{r} \log p(n)>0$ . This is analogous to the positivity of finite differences of the partition function. It was conjectured by Good and proved by Gupta that for given $r\geq 1$ , $Δ^{r} p(n)>0$ for sufficiently large $n$ .

preprint2014arXiv

Ramanujan-type Congruences for Overpartitions Modulo 16

Let $\overline{p}(n)$ denote the number of overpartitions of $n$ . Recently, Fortin-Jacob-Mathieu and Hirschhorn-Sellers independently obtained 2-, 3- and 4-dissections of the generating function for $\overline{p}(n)$ and derived a number of congruences for $\overline{p}(n)$ modulo $4$ , $8$ and $64$ including $\overline{p}(5n+2)\equiv 0 \pmod{4}$ , $\overline{p}(4n+3)\equiv 0 \pmod{8}$ and $\overline{p}(8n+7)\equiv 0 \pmod{64}$ . By employing dissection techniques, Yao and Xia obtained congruences for $\overline{p}(n)$ modulo $8, 16$ and $32$ , such as $\overline{p}(48n+26) \equiv 0 \pmod{8}$ , $\overline{p}(24n+17)\equiv 0 \pmod{16}$ and $\overline{p}(72n+69)\equiv 0 \pmod{32}$ . In this paper, we give a 16-dissection of the generating function for $\overline{p}(n)$ modulo 16 and we show that $\overline{p}(16n+14)\equiv0\pmod{16}$ for $n\ge 0$ . Moreover, by using the $2$ -adic expansion of the generating function of $\overline{p}(n)$ due to Mahlburg, we obtain that $\overline{p}(\ell^2n+r\ell)\equiv0\pmod{16}$ , where $n\ge 0$ , $\ell \equiv -1\pmod{8}$ is an odd prime and $r$ is a positive integer with $\ell \nmid r$ . In particular, for $\ell=7$ , we get $\overline{p}(49n+7)\equiv0\pmod{16}$ and $\overline{p}(49n+14)\equiv0\pmod{16}$ for $n\geq 0$ . We also find four congruence relations: $\overline{p}(4n)\equiv(-1)^n\overline{p}(n) \pmod{16}$ for $n\ge 0$ , $\overline{p}(4n)\equiv(-1)^n\overline{p}(n)\pmod{32}$ for $n$ being not a square of an odd positive integer, $\overline{p}(4n)\equiv(-1)^n\overline{p}(n)\pmod{64}$ for $n\not\equiv 1,2,5\pmod{8}$ and $\overline{p}(4n)\equiv(-1)^n\overline{p}(n)\pmod{128}$ for $n\equiv 0\pmod{4}$ .

preprint2014arXiv

Ramanujan-type Congruences for Overpartitions Modulo 5

Let $\overline{p}(n)$ denote the number of overpartitions of $n$ . Hirschhorn and Sellers showed that $\overline{p}(4n+3)\equiv 0 \pmod{8}$ for $n\geq 0$ . They also conjectured that $\overline{p}(40n+35)\equiv 0 \pmod{40}$ for $n\geq 0$ . Chen and Xia proved this conjecture by using the $(p,k)$ -parametrization of theta functions given by Alaca, Alaca and Williams. In this paper, we show that $\overline{p}(5n)\equiv (-1)^{n}\overline{p}(4\cdot 5n) \pmod{5}$ for $n \geq 0$ and $\overline{p}(n)\equiv (-1)^{n}\overline{p}(4n)\pmod{8}$ for $n \geq 0$ by using the relation of the generating function of $\overline{p}(5n)$ modulo $5$ found by Treneer and the $2$ -adic expansion of the generating function of $\overline{p}(n)$ due to Mahlburg. As a consequence, we deduce that $\overline{p}(4^k(40n+35))\equiv 0 \pmod{40}$ for $n,k\geq 0$ . Furthermore, applying the Hecke operator on $ϕ(q)^3$ and the fact that $ϕ(q)^3$ is a Hecke eigenform, we obtain an infinite family of congrences $\overline{p}(4^k \cdot5\ell^2n)\equiv 0 \pmod{5}$ , where $k\ge 0$ and $\ell$ is a prime such that $\ell\equiv3 \pmod{5}$ and $\left(\frac{-n}{\ell}\right)=-1$ . Moreover, we show that $\overline{p}(5^{2}n)\equiv \overline{p}(5^{4}n) \pmod{5}$ for $n \ge 0$ . So we are led to the congruences $\overline{p}\big(4^k5^{2i+3}(5n\pm1)\big)\equiv 0 \pmod{5}$ for $n, k, i\ge 0$ . In this way, we obtain various Ramanujan-type congruences for $\overline{p}(n)$ modulo $5$ such as $\overline{p}(45(3n+1))\equiv 0 \pmod{5}$ and $\overline{p}(125(5n\pm 1))\equiv 0 \pmod{5}$ for $n\geq 0$ .

preprint2014arXiv

Vacillating Hecke Tableaux and Linked Partitions

We introduce the structure of vacillating Hecke tableaux, and establish a one-to-one correspondence between vacillating Hecke tableaux and linked partitions by using the Hecke insertion algorithm developed by Buch, Kresch, Shimozono, Tamvakis and Yong. Linked partitions arise in free probability theory. Motivated by the Hecke insertion algorithm, we define a Hecke diagram as a Young diagram possibly with a marked corner. A vacillating Hecke tableau is defined as a sequence of Hecke diagrams subject to certain addition and deletion of rook strips. The notion of a rook strip was introduced by Buch in the study of the Littlewood-Richardson rule for stable Grothendieck polynomials. A rook strip is a skew Young diagram with at most one square in each row and column. We show that the crossing number and the nesting number of a linked partition can be determined by the maximal number of rows and the maximal number of columns of the diagrams in the corresponding vacillating Hecke tableau. The proof relies on a theorem due to Thomas and Yong concerning the lengths of the longest strictly increasing and the longest strictly decreasing subsequences in a word. This implies that the crossing number and the nesting number have a symmetric joint distribution over linked partitions, confirming a conjecture of de Mier. We also prove a conjecture of Kim which states that the crossing number and the nesting number have a symmetric joint distribution over the front representations of partitions.

preprint2014arXiv

Zigzag Stacks and m-Regular Linear Stacks

The contact map of a protein fold is a graph that represents the patterns of contacts in the fold. It is known that the contact map can be decomposed into stacks and queues. RNA secondary structures are special stacks in which the degree of each vertex is at most one and each arc has length at least two. Waterman and Smith derived a formula for the number of RNA secondary structures of length $n$ with exactly $k$ arcs. Höner zu Siederdissen et al. developed a folding algorithm for extended RNA secondary structures in which each vertex has maximum degree two. An equation for the generating function of extended RNA secondary structures was obtained by Müller and Nebel by using a context-free grammar approach, which leads to an asymptotic formula. In this paper, we consider $m$ -regular linear stacks, where each arc has length at least $m$ and the degree of each vertex is bounded by two. Extended RNA secondary structures are exactly $2$ -regular linear stacks. For any $m\geq 2$ , we obtain an equation for the generating function of the $m$ -regular linear stacks. For given $m$ , we can deduce a recurrence relation and an asymptotic formula for the number of $m$ -regular linear stacks on $n$ vertices. To establish the equation, we use the reduction operation of Chen, Deng and Du to transform an $m$ -regular linear stack to an $m$ -reduced zigzag (or alternating) stack. Then we find an equation for $m$ -reduced zigzag stacks leading to an equation for $m$ -regular linear stacks.

preprint2013arXiv

Combinatorial Proof of the Inversion Formula on the Kazhdan-Lusztig R-Polynomials

Let $W$ be a Coxeter group, and for $u,v\in W$ , let $R_{u,v}(q)$ be the Kazhdan-Lusztig $R$ -polynomial indexed by $u$ and $v$ . In this paper, we present a combinatorial proof of the inversion formula on $R$ -polynomials due to Kazhdan and Lusztig. This problem was raised by Brenti. Based on Dyer's combinatorial interpretation of the $R$ -polynomials in terms of increasing Bruhat paths, we reformulate the inversion formula in terms of $V$ -paths. By a $V$ -path from $u$ to $v$ with bottom $w$ we mean a pair $(Δ_1,Δ_2)$ of Bruhat paths such that $Δ_1$ is a decreasing path from $u$ to $w$ and $Δ_2$ is an increasing path from $w$ to $v$ . We find a reflection principle on $V$ -paths, which leads to a combinatorial proof of the inversion formula. Moreover, we give two applications of the reflection principle. First, we restrict this involution to $V$ -paths from $u$ to $v$ with maximal length. This provides a direct interpretation for the equi-distribution property that any nontrivial interval $[u,v]$ has as many elements of even length as elements of odd length. This property was obtained by Verma in his derivation of the Möbius function of the Bruhat order. Second, using the reflection principle for the symmetric group, we obtain a refinement of the inversion formula by restricting the summation to permutations ending with a given element.

preprint2013arXiv

Infinitely Log-monotonic Combinatorial Sequences

We introduce the notion of infinitely log-monotonic sequences. By establishing a connection between completely monotonic functions and infinitely log-monotonic sequences, we show that the sequences of the Bernoulli numbers, the Catalan numbers and the central binomial coefficients are infinitely log-monotonic. In particular, if a sequence $\{a_n\}_{n\geq 0}$ is log-monotonic of order two, then it is ratio log-concave in the sense that the sequence $\{a_{n+1}/a_{n}\}_{n\geq 0}$ is log-concave. Furthermore, we prove that if a sequence $\{a_n\}_{n\geq k}$ is ratio log-concave, then the sequence $\{\sqrt[n]{a_n}\}_{n\geq k}$ is strictly log-concave subject to a certain initial condition. As consequences, we show that the sequences of the derangement numbers, the Motzkin numbers, the Fine numbers, the central Delannoy numbers, the numbers of tree-like polyhexes and the Domb numbers are ratio log-concave. For the case of the Domb numbers $D_n$ , we confirm a conjecture of Sun on the log-concavity of the sequence $\{\sqrt[n]{D_n}\}_{n\geq 1}$ .

preprint2013arXiv

Linked Partitions and Permutation Tableaux

Linked partitions are introduced by Dykema in the study of transforms in free probability theory, whereas permutation tableaux are introduced by Steingrímsson and Williams in the study of totally positive Grassmannian cells. Let $[n]=\{1,2,\ldots,n\}$ . Let $L(n,k)$ denote the set of linked partitions of $[n]$ with $k$ blocks, let $P(n,k)$ denote the set of permutations of $[n]$ with $k$ descents, and let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. Steingrímsson and Williams found a bijection between the set of permutation tableaux of length $n$ with $k$ rows and the set of permutations of $[n]$ with $k$ weak excedances. Corteel and Nadeau gave a bijection from the set of permutation tableaux of length $n$ with $k$ columns to the set of permutations of $[n]$ with $k$ descents. In this paper, we establish a bijection between $L(n,k)$ and $P(n,k-1)$ and a bijection between $L(n,k)$ and $T(n,k)$ . Restricting the latter bijection to noncrossing linked partitions, we find that the corresponding permutation tableaux can be characterized by pattern avoidance.

preprint2013arXiv

On Permutations with Bounded Drop Size

The maximum drop size of a permutation $π$ of $[n]=\{1,2,\ldots, n\}$ is defined to be the maximum value of $i-π(i)$ . Chung, Claesson, Dukes and Graham obtained polynomials $P_k(x)$ that can be used to determine the number of permutations of $[n]$ with $d$ descents and maximum drop size not larger than $k$ . Furthermore, Chung and Graham gave combinatorial interpretations of the coefficients of $Q_k(x)=x^k P_k(x)$ and $R_{n,k}(x)=Q_k(x)(1+x+\cdots+x^k)^{n-k}$ , and raised the question of finding a bijective proof of the symmetry property of $R_{n,k}(x)$ . In this paper, we establish a bijection $φ$ on $A_{n,k}$ , where $A_{n,k}$ is the set of permutations of $[n]$ and maximum drop size not larger than $k$ . The map $φ$ remains to be a bijection between certain subsets of $A_{n,k}$ . %related to the symmetry property. This provides an answer to the question of Chung and Graham. The second result of this paper is a proof of a conjecture of Hyatt concerning the unimodality of polynomials in connection with the number of signed permutations of $[n]$ with $d$ type $B$ descents and the type $B$ maximum drop size not greater than $k$ .

preprint2013arXiv

On the Positive Moments of Ranks of Partitions

By introducing $k$ -marked Durfee symbols, Andrews found a combinatorial interpretation of $2k$ -th symmetrized moment $η_{2k}(n)$ of ranks of partitions of $n$ in terms of $(k+1)$ -marked Durfee symbols of $n$ . In this paper, we consider the $k$ -th symmetrized positive moment $\barη_k(n)$ of ranks of partitions of $n$ which is defined as the truncated sum over positive ranks of partitions of $n$ . As combintorial interpretations of $\barη_{2k}(n)$ and $\barη_{2k-1}(n)$ , we show that for fixed $k$ and $i$ with $1\leq i\leq k+1$ , $\barη_{2k-1}(n)$ equals the number of $(k+1)$ -marked Durfee symbols of $n$ with the $i$ -th rank being zero and $\barη_{2k}(n)$ equals the number of $(k+1)$ -marked Durfee symbols of $n$ with the $i$ -th rank being positive. The interpretations of $\barη_{2k-1}(n)$ and $\barη_{2k}(n)$ also imply the interpretation of $η_{2k}(n)$ given by Andrews since $η_{2k}(n)$ equals $\barη_{2k-1}(n)$ plus twice of $\barη_{2k}(n)$ . Moreover, we obtain the generating functions of $\barη_{2k}(n)$ and $\barη_{2k-1}(n)$ .

preprint2013arXiv

Ordered Partitions Avoiding a Permutation of Length 3

An ordered partition of $[n]=\{1, 2, \ldots, n\}$ is a partition whose blocks are endowed with a linear order. Let $\mathcal{OP}_{n,k}$ be set of ordered partitions of $[n]$ with $k$ blocks and $\mathcal{OP}_{n,k}(σ)$ be set of ordered partitions in $\mathcal{OP}_{n,k}$ that avoid a pattern $σ$ . Recently, Godbole, Goyt, Herdan and Pudwell obtained formulas for the number of ordered partitions of $[n]$ with 3 blocks and the number of ordered partitions of $[n]$ with $n-1$ blocks avoiding a permutation pattern of length 3. They showed that $|\mathcal{OP}_{n,k}(σ)|=|\mathcal{OP}_{n,k}(123)|$ for any permutation $σ$ of length 3, and raised the question concerning the enumeration of $\mathcal{OP}_{n,k}(123)$ . They also conjectured that the number of ordered partitions of $[2n]$ with blocks of size 2 avoiding a permutation pattern of length 3 satisfied a second order linear recurrence relation. In answer to the question of Godbole, et al., we obtain the generating function for $|\mathcal{OP}_{n,k}(123)|$ and we prove the conjecture on the recurrence relation.

preprint2013arXiv

Proof of a Conjecture of Hirschhorn and Sellers on Overpartitions

Let $\bar{p}(n)$ denote the number of overpartitions of $n$ . It was conjectured by Hirschhorn and Sellers that $\bar{p}(40n+35)\equiv 0\ ({\rm mod\} 40)$ for $n\geq 0$ . Employing 2-dissection formulas of quotients of theta functions due to Ramanujan, and Hirschhorn and Sellers, we obtain a generating function for $\bar{p}(40n+35)$ modulo 5. Using the $(p, k)$ -parametrization of theta functions given by Alaca, Alaca and Williams, we give a proof of the congruence $\bar{p}(40n+35)\equiv 0\ ({\rm mod\} 5)$. Combining this congruence and the congruence $\bar{p}(4n+3)\equiv 0\ ({\rm mod\} 8)$ obtained by Hirschhorn and Sellers, and Fortin, Jacob and Mathieu, we give a proof of the conjecture of Hirschhorn and Sellers.

preprint2013arXiv

Proof of the Andrews-Dyson-Rhoades Conjecture on the spt-Crank

The notion of the spt-crank of a vector partition, or an $S$ -partition, was introduced by Andrews, Garvan and Liang. Let $N_S(m,n)$ denote the number of $S$ -partitions of $n$ with spt-crank $m$ . Andrews, Dyson and Rhoades conjectured that $\{N_S(m,n)\}_m$ is unimodal for any $n$ , and they showed that this conjecture is equivalent to an inequality between the rank and the crank of ordinary partitions. They obtained an asymptotic formula for the difference between the rank and the crank of ordinary partitions, which implies $N_S(m,n)\geq N_S(m+1,n)$ for sufficiently large $n$ and fixed $m$ . In this paper, we introduce a representation of an ordinary partition, called the $m$ -Durfee rectangle symbol, which is a rectangular generalization of the Durfee symbol introduced by Andrews. We give a proof of the conjecture of Andrews, Dyson and Rhoades by considering two cases. For $m\geq 1$ , we construct an injection from the set of ordinary partitions of $n$ such that $m$ appears in the rank-set to the set of ordinary partitions of $n$ with rank not less than $-m$ . The case for $m=0$ requires five more injections. We also show that this conjecture implies an inequality between the positive rank and crank moments obtained by Andrews, Chan and Kim.

preprint2013arXiv

Ramanujan-type Congruences for Broken 2-Diamond Partitions Modulo 3

The notion of broken $k$ -diamond partitions was introduced by Andrews and Paule. Let $Δ_k(n)$ denote the number of broken k-diamond partitions of $n$ . They also posed three conjectures on the congruences of $Δ_2(n)$ modulo 2, 5 and 25. Hirschhorn and sellers proved the conjectures for modulo 2, and Chan proved cases of modulo 5. For the case of modulo 3, Radu and Sellers obtained an infinite family of congruences for $Δ_2(n)$ . In this paper, we obtain two infinite families of congruences for $Δ_2(n)$ modulo 3 based on a formula of Radu and Sellers, the 3-dissection formula of the generating function of triangular number due to Berndt, and the properties of the $U$ -operator, the $V$ -operator, the Hecke operator and the Hecke eigenform. For example, we find that $Δ_2(243n+142)\equiv Δ_2(243n+223)\equiv0\pmod{3}$ . The infinite family of Radu and Sellers and the two infinite families derived in this paper have two congruences in common, namely, $Δ_2(27n+16)\equivΔ_2(27n+25)\equiv0 \pmod{3}$ .

preprint2013arXiv

s-Inversion Sequences and P-Partitions of Type B

Given a sequence $s=(s_1,s_2,\ldots)$ of positive integers, the inversion sequences with respect to $s$ , or $s$ -inversion sequences, were introduced by Savage and Schuster in their study of lecture hall polytopes. A sequence $(e_1,e_2,\ldots,e_n)$ of nonnegative integers is called an $s$ -inversion sequence of length $n$ if $0\leq e_i < s_i$ for $1\leq i\leq n$ . Let I(n) be the set of $s$ -inversion sequences of length $n$ for $s=(1,4,3,8,5,12,\ldots)$ , that is, $s_{2i}=4i$ and $s_{2i-1}=2i-1$ for $i\geq1$ , and let $P_n$ be the set of signed permutations on $\{1^2,2^2,\ldots,n^2\}$ . Savage and Visontai conjectured that when $n=2k$ , the ascent number over $I_n$ is equidistributed with the descent number over $P_k$ . For a positive integer $n$ , we use type $B$ $P$ -partitions to give a characterization of signed permutations over which the descent number is equidistributed with the ascent number over $I_n$ . When $n$ is even, this confirms the conjecture of Savage and Visontai. Moreover, let $I'_n$ be the set of $s$ -inversion sequences of length $n$ for $s=(2,2,6,4,10,6,\ldots)$ , that is, $s_{2i}=2i$ and $s_{2i-1}=4i-2$ for $i\geq1$ . We find a set of signed permutations over which the descent number is equidistributed with the ascent number over $I'_n$ .

preprint2013arXiv

The spt-Crank for Ordinary Partitions

The spt-function $spt(n)$ was introduced by Andrews as the weighted counting of partitions of $n$ with respect to the number of occurrences of the smallest part. Andrews, Garvan and Liang defined the spt-crank of an $S$ -partition which leads to combinatorial interpretations of the congruences of $spt(n)$ mod 5 and 7. Let $N_S(m,n)$ denote the net number of $S$ -partitions of $n$ with spt-crank $m$ . Andrews, Garvan and Liang showed that $N_S(m,n)$ is nonnegative for all integers $m$ and positive integers $n$ , and they asked the question of finding a combinatorial interpretation of $N_S(m,n)$ . In this paper, we introduce the structure of doubly marked partitions and define the spt-crank of a doubly marked partition. We show that $N_S(m,n)$ can be interpreted as the number of doubly marked partitions of $n$ with spt-crank $m$ . Moreover, we establish a bijection between marked partitions of $n$ and doubly marked partitions of $n$ . A marked partition is defined by Andrews, Dyson and Rhoades as a partition with exactly one of the smallest parts marked. They consider it a challenge to find a definition of the spt-crank of a marked partition so that the set of marked partitions of $5n+4$ and $7n+5$ can be divided into five and seven equinumerous classes. The definition of spt-crank for doubly marked partitions and the bijection between the marked partitions and doubly marked partitions leads to a solution to the problem of Andrews, Dyson and Rhoades.

preprint2013arXiv

Zeta Functions and the Log-behavior of Combinatorial Sequences

In this paper, we use the Riemann zeta function $ζ(x)$ and the Bessel zeta function $ζ_μ(x)$ to study the log-behavior of combinatorial sequences. We prove that $ζ(x)$ is log-convex for $x>1$ . As a consequence, we deduce that the sequence $\{|B_{2n}|/(2n)!\}_{n\geq 1}$ is log-convex, where $B_n$ is the $n$ -th Bernoulli number. We introduce the function $θ(x)=(2ζ(x)Γ(x+1))^{\frac{1}{x}}$ , where $Γ(x)$ is the gamma function, and we show that $\log θ(x)$ is strictly increasing for $x\geq 6$ . This confirms a conjecture of Sun stating that the sequence $\{\sqrt[n] {|B_{2n}}|\}_{n\geq 1}$ is strictly increasing. Amdeberhan, Moll and Vignat defined the numbers $a_n(μ)=2^{2n+1}(n+1)!(μ+1)_nζ_μ(2n)$ and conjectured that the sequence $\{a_n(μ)\}_{n\geq 1}$ is log-convex for $μ=0$ and $μ=1$ . By proving that $ζ_μ(x)$ is log-convex for $x>1$ and $μ>-1$ , we show that the sequence $\{a_n(μ)\}_{n\geq 1}$ is log-convex for any $μ>-1$ . We introduce another function $θ_μ(x)$ involving $ζ_μ(x)$ and the gamma function $Γ(x)$ and we show that $\log θ_μ(x)$ is strictly increasing for $x>8e(μ+2)^2$ . This implies that $\sqrt[n]{a_n(μ)}<\sqrt[n+1]{a_{n+1}(μ)}$ for $n> 4e(μ+2)^2$ . Based on Dobinski's formula, we prove that $\sqrt[n]{B_n}<\sqrt[n+1]{B_{n+1}}$ for $n\geq 1$ , where $B_n$ is the $n$ -th Bell number. This confirms another conjecture of Sun. We also establish a connection between the increasing property of $\{\sqrt[n]{B_n}\}_{n\geq 1}$ and Hölder's inequality in probability theory.

preprint2012arXiv

An Overpartition Analogue of Bressoud's Theorem of Rogers-Ramanujan Type

For $k\geq i\geq 1$ , let $B_{k,i}(n)$ denote the number of partitions of $n$ such that part 1 appears at most $i-1$ times, two consecutive integers l and $l+1$ appear at most $k-1$ times and if l and $l+1$ appear exactly $k-1$ times then the total sum of the parts l and $l+1$ is congruent to $i-1$ modulo 2. Let $A_{k,i}(n)$ denote the number of partitions with parts not congruent to $i$ , $2k-i$ and $2k$ modulo $2k$ . Bressoud's theorem states that $A_{k,i}(n)=B_{k,i}(n)$ . Corteel, Lovejoy, and Mallet found an overpartition analogue of Bressoud's theorem for $i=1$ , that is, for partitions not containing nonoverlined part 1. We obtain an overpartition analogue of Bressoud's theorem in the general case. For $k\geq i\geq 1$ , let $D_{k,i}(n)$ denote the number of overpartitions of $n$ such that the nonoverlined part 1 appears at most $i-1$ times, for any integer $l$ , $l$ and nonoverlined $l+1$ appear at most $k-1$ times and if the parts $l$ and the nonoverlined part $l+1$ appear exactly $k-1$ times then the total sum of the parts $l$ and nonoverlined part $l+1$ is congruent to the number of overlined parts that are less than $l+1$ plus $i-1$ modulo 2. Let $C_{k,i}(n)$ denote the number of overpartitions with the nonoverlined parts not congruent to $\pm i$ and $2k-1$ modulo $2k-1$ . We show that $C_{k,i}(n)=D_{k,i}(n)$ . This relation can also be considered as a Rogers-Ramanujan-Gordon type theorem for overpartitions.

preprint2012arXiv

Branden's Conjectures on the Boros-Moll Polynomials

We prove two conjectures of Brändén on the real-rootedness of polynomials $Q_n(x)$ and $R_n(x)$ which are related to the Boros-Moll polynomials $P_n(x)$ . In fact, we show that both $Q_n(x)$ and $R_n(x)$ form Sturm sequences. The first conjecture implies the 2-log-concavity of $P_n(x)$ , and the second conjecture implies the 3-log-concavity of $P_n(x)$ .

preprint2012arXiv

Congruences of Multipartition Functions Modulo Powers of Primes

Let $p_r(n)$ denote the number of $r$ -component multipartitions of $n$ , and let $S_{γ,λ}$ be the space spanned by $η(24z)^γϕ(24z)$ , where $η(z)$ is the Dedekind's eta function and $ϕ(z)$ is a holomorphic modular form in $M_λ({\rm SL}_2(\mathbb{Z}))$ . In this paper, we show that the generating function of $p_r(\frac{m^k n +r}{24})$ with respect to $n$ is congruent to a function in the space $S_{γ,λ}$ modulo $m^k$ . As special cases, this relation leads to many well known congruences including the Ramanujan congruences of $p(n)$ modulo $5,7,11$ and Gandhi's congruences of $p_2(n)$ modulo 5 and $p_{8}(n)$ modulo 11. Furthermore, using the invariance property of $S_{γ,λ}$ under the Hecke operator $T_{\ell^2}$ , we obtain two classes of congruences pertaining to the $m^k$ -adic property of $p_r(n)$ .

preprint2012arXiv

Context-free Grammars and Multivariate Stable Polynomials over Stirling Permutations

Recently, Haglund and Visontai established the stability of the multivariate Eulerian polynomials as the generating polynomials of the Stirling permutations, which serves as a unification of some results of Bóna, Brenti, Janson, Kuba, and Panholzer concerning Stirling permutations. Let $B_n(x)$ be the generating polynomials of the descent statistic over Legendre-Stirling permutations, and let $T_n(x)=2^nC_n(x/2)$ , where $C_n(x)$ are the second-order Eulerian polynomials. Haglund and Visontai proposed the problems of finding multivariate stable refinements of the polynomials $B_n(x)$ and $T_n(x)$ . We obtain context-free grammars leading to multivariate stable refinements of the polynomials $B_n(x)$ and $T_n(x)$ . Moreover, the grammars enable us to obtain combinatorial interpretations of the multivariate polynomials in terms of Legendre-Stirling permutations and marked Stirling permutations. Such stable multivariate polynomials provide solutions to two problems posed by Haglund and Visontai.

preprint2012arXiv

Decomposition of Triply Rooted Trees

In this paper, we give a decomposition of triply rooted trees into three doubly rooted trees. This leads to a combinatorial interpretation of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory, and proved by Younsi by using the Hurwitz identity on multivariate Abel polynomials. We also give a bijection between the set of functions from $[n+1]$ to $[n]$ and the set of triply rooted trees on $[n]$ , which leads to the refined enumeration of functions from $[n+1]$ to $[n]$ with respect to the number of elements in the orbit of $n+1$ and the number of periodic points.

preprint2012arXiv

Disposition Polynomials and Plane Trees

We define the disposition polynomial $R_{m}(x_1, x_2, ..., x_n)$ as $\prod_{k=0}^{m-1}(x_1+x_2+...+x_n+k)$ . When $m=n-1$ , this polynomial becomes the generating function of plane trees with respect to certain statistics as given by Guo and Zeng. When $x_i=1$ for $1\leq i\leq n$ , $R_{m}(x_1, x_2, ..., x_n)$ reduces to the rising factorial $n(n+1)... (n+m-1)$ . Guo and Zeng asked the question of finding a combinatorial proof of the formula for the generating function of plane trees with respect to the number of younger children and the number of elder children. We find a combinatorial interpretation of the disposition polynomials in terms of the number of right-to-left minima of each linear order in a disposition. Then we establish a bijection between plane trees on $n$ vertices and dispositions from ${1, 2,..., n-1}$ to ${1, 2,..., n}$ in the spirit of the Prüfer correspondence. It gives an answer to the question of Guo and Zeng, and it also provides an answer to another question of Guo and Zeng concerning an identity on the plane tree expansion of a polynomial introduced by Gessel and Seo.

preprint2012arXiv

Euler's Partition Theorem with Upper Bounds on Multiplicities

We show that the number of partitions of n with alternating sum k such that the multiplicity of each part is bounded by 2m+1 equals the number of partitions of n with k odd parts such that the multiplicity of each even part is bounded by m. The first proof relies on two formulas with two parameters that are related to the four-parameter formulas of Boulet. We also give a combinatorial proof of this result by using Sylvester's bijection, which implies a stronger partition theorem. For m=0, our result reduces to Bessenrodt's refinement of Euler's Theorem. If the alternating sum and the number of odd parts are not taken into account, we are led to a connection to a generalization of Euler's theorem, which can be deduced from a theorem of Andrews on equivalent upper bound sequences of multiplicities. Analogously, we show that the number of partitions of n with alternating sum k such that the multiplicity of each even part is bounded by 2m+1 equals the number of partitions of n with k odd parts such that the multiplicity of each even part is also bounded by 2m+1. We provide a combinatorial proof as well.

preprint2012arXiv

On 021-Avoiding Ascent Sequences

Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of $(\bf{2+2})$ -free posets. An ascent sequence of length $n$ is a nonnegative integer sequence $x=x_{1}x_{2}... x_{n}$ such that $x_{1}=0$ and $x_{i}\leq \asc(x_{1}x_{2}...x_{i-1})+1$ for all $1<i\leq n$ , where $\asc(x_{1}x_{2}...x_{i-1})$ is the number of ascents in the sequence $x_{1}x_{2}... x_{i-1}$ . We let $\cA_n$ stand for the set of such sequences and use $\cA_n(p)$ for the subset of sequences avoiding a pattern $p$ . Similarly, we let $S_{n}(τ)$ be the set of $τ$ -avoiding permutations in the symmetric group $S_{n}$ . Duncan and Steingr\'ımsson have shown that the ascent statistic has the same distribution over $\cA_n(021)$ as over $S_n(132)$ . Furthermore, they conjectured that the pair $(\asc, \rlm)$ is equidistributed over $\cA_n(021)$ and $S_n(132)$ where $\rlm$ is the right-to-left minima statistic. We prove this conjecture by constructing a bistatistic-preserving bijection.

preprint2012arXiv

On Pattern Avoiding Alternating Permutations

An alternating permutation of length $n$ is a permutation $π=π_1 π_2 ... π_n$ such that $π_1 < π_2 > π_3 < π_4 > ...$ . Let $A_n$ denote set of alternating permutations of ${1,2,..., n}$ , and let $A_n(σ)$ be set of alternating permutations in $A_n$ that avoid a pattern $σ$ . Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$ , $A_{2n}(2143)$ and $A_{2n+1}(2143)$ , and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bóna, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.

preprint2012arXiv

On the Number of Partitions with Designated Summands

Andrews, Lewis and Lovejoy introduced the partition function PD(n) as the number of partitions of $n$ with designated summands, where we assume that among parts with equal size, exactly one is designated. They proved that PD(3n+2) is divisible by 3. We obtain a Ramanujan type identity for the generating function of PD(3n+2) which implies the congruence of Andrews, Lewis and Lovejoy. For PD(3n), Andrews, Lewis and Lovejoy showed that the generating function can be expressed as an infinite product of powers of $(1-q^{2n+1})$ times a function $F(q^2)$ . We find an explicit formula for $F(q^2)$ , which leads to a formula for the generating function of PD(3n). We also obtain a formula for the generating function of PD(3n+1). Our proofs rely on Chan's identity on Ramanujan's cubic continued fraction and some identities on cubic theta functions. By introducing a rank for the partitions with designed summands, we give a combinatorial interpretation of the congruence of Andrews, Lewis and Lovejoy.

preprint2012arXiv

Proof of Lassalle's Positivity Conjecture on Schur Functions

In the study of Zeilberger's conjecture on an integer sequence related to the Catalan numbers, Lassalle proposed the following conjecture. Let $(t)_n$ denote the rising factorial, and let $Λ_{\mathbb{R}}$ denote the algebra of symmetric functions with real coefficients. If $φ$ is the homomorphism from $Λ_{\mathbb{R}}$ to $\mathbb{R}$ defined by $φ(h_n)={1}/{((t)_nn!)}$ for some $t>0$ , then for any Schur function $s_λ$ , the value $φ(s_λ)$ is positive. In this paper, we provide an affirmative answer to Lassalle's conjecture by using the Laguerre-Pólya-Schur theory of multiplier sequences.

preprint2012arXiv

The Sorting Index and Permutation Codes

In the combinatorial study of the coefficients of a bivariate polynomial that generalizes both the length and the reflection length generating functions for finite Coxeter groups, Petersen introduced a new Mahonian statistic $sor$ , called the sorting index. Petersen proved that the pairs of statistics $(sor,cyc)$ and $(inv,rl\textrm{-}min)$ have the same joint distribution over the symmetric group, and asked for a combinatorial proof of this fact. In answer to the question of Petersen, we observe a connection between the sorting index and the B-code of a permutation defined by Foata and Han, and we show that the bijection of Foata and Han serves the purpose of mapping $(inv,rl\textrm{-}min)$ to $(sor,cyc)$ . We also give a type $B$ analogue of the Foata-Han bijection, and we derive the quidistribution of $(inv_B,{\rm Lmap_B},{\rm Rmil_B})$ and $(sor_B,{\rm Lmap_B},{\rm Cyc_B})$ over signed permutations. So we get a combinatorial interpretation of Petersen's equidistribution of $(inv_B,nmin_B)$ and $(sor_B,l_B')$ . Moreover, we show that the six pairs of set-valued statistics $\rm (Cyc_B,Rmil_B)$ , $\rm(Cyc_B,Lmap_B)$ , $\rm(Rmil_B,Lmap_B)$ , $\rm(Lmap_B,Rmil_B)$ , $\rm(Lmap_B,Cyc_B)$ and $\rm(Rmil_B,Cyc_B)$ are equidistributed over signed permutations. For Coxeter groups of type $D$ , Petersen showed that the two statistics $inv_D$ and $sor_D$ are equidistributed. We introduce two statistics $nmin_D$ and $\tilde{l}_D'$ for elements of $D_n$ and we prove that the two pairs of statistics $(inv_D,nmin_D)$ and $(sor_D,\tilde{l}_D')$ are equidistributed.

preprint2011arXiv

Combinatorial Telescoping for an Identity of Andrews on Parity in Partitions

Following the method of combinatorial telescoping for alternating sums given by Chen, Hou and Mu, we present a combinatorial telescoping approach to partition identities on sums of positive terms. By giving a classification of the combinatorial objects corresponding to a sum of positive terms, we establish bijections that lead a telescoping relation. We illustrate this idea by giving a combinatorial telescoping relation for a classical identity of MacMahon. Recently, Andrews posed a problem of finding a combinatorial proof of an identity on the q-little Jacobi polynomials which was derived based on a recurrence relation. We find a combinatorial classification of certain triples of partitions and a sequence of bijections. By the method of cancelation, we see that there exists an involution for a recurrence relation that implies the identity of Andrews.

preprint2011arXiv

Equivalence Classes of Full-Dimensional 0/1-Polytopes with Many Vertices

Let $Q_n$ denote the $n$ -dimensional hypercube with the vertex set $V_n=\{0,1}^n$. A 0/1-polytope of $Q_n$ is a convex hull of a subset of $V_n$ . This paper is concerned with the enumeration of equivalence classes of full-dimensional 0/1-polytopes under the symmetries of the hypercube. With the aid of a computer program, Aichholzer completed the enumeration of equivalence classes of full-dimensional 0/1-polytopes for $Q_4$ , $Q_5$ , and those of $Q_6$ up to 12 vertices. In this paper, we present a method to compute the number of equivalence classes of full-dimensional 0/1-polytopes of $Q_n$ with more than $2^{n-3}$ vertices. As an application, we finish the counting of equivalence classes of full-dimensional 0/1-polytopes of $Q_6$ with more than 12 vertices.

preprint2011arXiv

Extended Zeilberger's Algorithm for Identities on Bernoulli and Euler Polynomials

We present a computer algebra approach to proving identities on Bernoulli polynomials and Euler polynomials by using the extended Zeilberger's algorithm given by Chen, Hou and Mu. The key idea is to use the contour integral definitions of the Bernoulli and Euler numbers to establish recurrence relations on the integrands. Such recurrence relations have certain parameter free properties which lead to the required identities without computing the integrals.

preprint2011arXiv

On Han's Hook Length Formulas for Trees

Recently, Han obtained two hook length formulas for binary trees and asked for combinatorial proofs. One of Han's formulas has been generalized to k-ary trees by Yang. Sagan has found a probabilistic proof of Yang's extension. We give combinatorial proofs of Yang's formula for k-ary trees and the other formula of Han for binary trees. Our bijections are based on the structure of k-ary trees with staircase labelings.

preprint2011arXiv

Oscillating Rim Hook Tableaux and Colored Matchings

Motivated by the question of finding a type B analogue of the bijection between oscillating tableaux and matchings, we find a correspondence between oscillating m-rim hook tableaux and m-colored matchings, where m is a positive integer. An oscillating m-rim hook tableau is defined as a sequence $(λ^0,λ^1,...,λ^{2n})$ of Young diagrams starting with the empty shape and ending with the empty shape such that $λ^{i}$ is obtained from $λ^{i-1}$ by adding an m-rim hook or by deleting an m-rim hook. Our bijection relies on the generalized Schensted algorithm due to White. An oscillating 2-rim hook tableau is also called an oscillating domino tableau. When we restrict our attention to two column oscillating domino tableaux of length 2n, we are led to a bijection between such tableaux and noncrossing 2-colored matchings on $\{1, 2,..., 2n\}$ , which are counted by the product $C_nC_{n+1}$ of two consecutive Catalan numbers. A 2-colored matching is noncrossing if there are no two arcs of the same color that are intersecting. We show that oscillating domino tableaux with at most two columns are in one-to-one correspondence with Dyck path packings. A Dyck path packing of length 2n is a pair (D, E), where D is a Dyck path of length 2n, and E is a dispersed Dyck path of length 2n that is weakly covered by D. So we deduce that Dyck path packings of length 2n are counted by $C_nC_{n+1}$ .

preprint2011arXiv

The Abel-Zeilberger Algorithm

We use both Abel's lemma on summation by parts and Zeilberger's algorithm to find recurrence relations for definite summations. The role of Abel's lemma can be extended to the case of linear difference operators with polynomial coefficients. This approach can be used to verify and discover identities involving harmonic numbers and derangement numbers. As examples, we use the Abel-Zeilberger algorithm to prove the Paule-Schneider identities, the Apery-Schmidt-Strehl identity, Calkin's identity and some identities involving Fibonacci numbers.

preprint2011arXiv

The Rogers-Ramanujan-Gordon Theorem for Overpartitions

Let $B_{k,i}(n)$ be the number of partitions of $n$ with certain difference condition and let $A_{k,i}(n)$ be the number of partitions of $n$ with certain congruence condition. The Rogers-Ramanujan-Gordon theorem states that $B_{k,i}(n)=A_{k,i}(n)$ . Lovejoy obtained an overpartition analogue of the Rogers-Ramanujan-Gordon theorem for the cases $i=1$ and $i=k$ . We find an overpartition analogue of the Rogers-Ramanujan-Gordon theorem in the general case. Let $D_{k,i}(n)$ be the number of overpartitions of $n$ satisfying certain difference condition and $C_{k,i}(n)$ be the number of overpartitions of $n$ whose non-overlined parts satisfy certain congruences condition. We show that $C_{k,i}(n)=D_{k,i}(n)$ . By using a function introduced by Andrews, we obtain a recurrence relation which implies that the generating function of $D_{k,i}(n)$ equals the generating function of $C_{k,i}(n)$ . We also find a generating function formula of $D_{k,i}(n)$ by using Gordon marking representations of overpartitions, which can be considered as an overpartition analogue of an identity of Andrews for ordinary partitions.

preprint2010arXiv

2-Log-concavity of the Boros-Moll Polynomials

The Boros-Moll polynomials $P_m(a)$ arise in the evaluation of a quartic integral. It has been conjectured by Boros and Moll that these polynomials are infinitely log-concave. In this paper, we show that $P_m(a)$ is 2-log-concave for any $m\geq 2$ . Let $d_i(m)$ be the coefficient of $a^i$ in $P_m(a)$ . We also show that the sequence $\{i (i+1)(d_i^{\,2}(m)-d_{i-1}(m)d_{i+1}(m))\}_{1\leq i \leq m}$ is log-concave. This leads another proof of Moll's minimum conjecture.

preprint2010arXiv

A Bijection between Atomic Partitions and Unsplitable Partitions

In the study of the algebra $\mathrm{NCSym}$ of symmetric functions in noncommutative variables, Bergeron and Zabrocki found a free generating set consisting of power sum symmetric functions indexed by atomic partitions. On the other hand, Bergeron, Reutenauer, Rosas, and Zabrocki studied another free generating set of $\mathrm{NCSym}$ consisting of monomial symmetric functions indexed by unsplitable partitions. Can and Sagan raised the question of finding a bijection between atomic partitions and unsplitable partitions. In this paper, we provide such a bijection.

preprint2010arXiv

An Iterated Map for the Lebesgue Identity

We present a simple iteration for the Lebesgue identity on partitions, which leads to a refinement involving the alternating sums of partitions.

preprint2010arXiv

Anti-lecture Hall Compositions and Overpartitions

We show that the number of anti-lecture hall compositions of n with the first entry not exceeding k-2 equals the number of overpartitions of n with non-overlined parts not congruent to $0,\pm 1$ modulo k. This identity can be considered as a refined version of the anti-lecture hall theorem of Corteel and Savage. To prove this result, we find two Rogers-Ramanujan type identities for overpartition which are analogous to the Rogers-Ramanjan type identities due to Andrews. When k is odd, we give an alternative proof by using a generalized Rogers-Ramanujan identity due to Andrews, a bijection of Corteel and Savage and a refined version of a bijection also due to Corteel and Savage.

preprint2010arXiv

Arithmetic Properties of Overpartition Pairs

Bringmann and Lovejoy introduced a rank for overpartition pairs and investigated its role in congruence properties of $\bar{pp}(n)$ , the number of overpartition pairs of n. In particular, they applied the theory of Klein forms to show that there exist many Ramanujan-type congruences for the number $\bar{pp}(n)$ . In this paper, we shall derive two Ramanujan-type identities and some explicit congruences for $\bar{pp}(n)$ . Moreover, we find three ranks as combinatorial interpretations of the fact that $\bar{pp}(n)$ is divisible by three for any n. We also construct infinite families of congruences for $\bar{pp}(n)$ modulo 3, 5, and 9.

preprint2010arXiv

Congruences for Bipartitions with Odd Parts Distinct

Hirschhorn and Sellers studied arithmetic properties of the number of partitions with odd parts distinct. In another direction, Hammond and Lewis investigated arithmetic properties of the number of bipartitions. In this paper, we consider the number of bipartitions with odd parts distinct. Let this number be denoted by $pod_{-2}(n)$ . We obtain two Ramanujan type identities for $pod_{-2}(n)$ , which imply that $pod_{-2}(2n+1)$ is even and $pod_{-2}(3n+2)$ is divisible by 3. Furthermore, we show that for any $α\geq 1$ and $n\geq 0$ , $pod_{-2}(3^{2α+1}n+\frac{23\times 3^{2α}-7}{8})$ is a multiple of 3 and $pod_{-2}(5^{α+1}n+\frac{11\times 5^α+1}{4})$ is divisible by 5. We also find combinatorial interpretations for the two congruences modulo 2 and 3.

preprint2010arXiv

Han's Bijection via Permutation Codes

We show that Han's bijection when restricted to permutations can be carried out in terms of the cyclic major code and the cyclic inversion code. In other words, it maps a permutation $π$ with a cyclic major code $(s_1, s_2, ..., s_n)$ to a permutation $σ$ with a cyclic inversion code $(s_1,s_2, ..., s_n)$ . We also show that the fixed points of Han's map can be characterized by the strong fixed points of Foata's second fundamental transformation. The notion of strong fixed points is related to partial Foata maps introduced by Björner and Wachs.

preprint2010arXiv

Interlacing Log-concavity of the Boros-Moll Polynomials

We introduce the notion of interlacing log-concavity of a polynomial sequence $\{P_m(x)\}_{m\geq 0}$ , where $P_m(x)$ is a polynomial of degree m with positive coefficients $a_{i}(m)$ . This sequence of polynomials is said to be interlacing log-concave if the ratios of consecutive coefficients of $P_m(x)$ interlace the ratios of consecutive coefficients of $P_{m+1}(x)$ for any $m\geq 0$ . Interlacing log-concavity is stronger than the log-concavity. We show that the Boros-Moll polynomials are interlacing log-concave. Furthermore we give a sufficient condition for interlacing log-concavity which implies that some classical combinatorial polynomials are interlacing log-concave.

preprint2010arXiv

Involutions for Rogers-Ramanujan-Gordon Type Identities with Parity Restrictions

We find involutions for three Rogers-Ramanujan-Gordon type identities obtained by Andrews on the generating functions for partitions with part difference and parity restrictions.

preprint2010arXiv

Labeled Ballot Paths and the Springer Numbers

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 Arnol'd 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 $α$ such that the number of snakes $π$ of type $B_n$ with $α(π)=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].

preprint2010arXiv

Lattice Polynomials, 12312-Avoiding Partial Matchings and Even Trees

The lattice polynomials $L_{i,j}(x)$ are introduced by Hough and Shapiro as a weighted count of certain lattice paths from the origin to the point $(i,j)$ . In particular, $L_{2n, n}(x)$ reduces to the generating function of the numbers $T_{n,k}={1\over n}{n-1+k\choose n-1}{2n-k\choose n+1}$ , which can be viewed as a refinement of the $3$ -Catalan numbers $T_n=\frac{1}{2n+1}{3n\choose n}$ . In this paper, we establish a correspondence between $12312$ -avoiding partial matchings and lattice paths, and we show that the weighted count of such partial matchings with respect to the number of crossings in a more general sense coincides with the lattice polynomials $L_{i,j}(x)$ . We also introduce a statistic on even trees, called the $r$ -index, and show that the number of even trees with $2n$ edges and with $r$ -index $k$ equal to $T_{n,k}$ .

preprint2010arXiv

Minimal Permutations and 2-Regular Skew Tableaux

Bouvel and Pergola introduced the notion of minimal permutations in the study of the whole genome duplication-random loss model for genome rearrangements. Let $\mathcal{F}_d(n)$ denote the set of minimal permutations of length $n$ with $d$ descents, and let $f_d(n)= |\mathcal{F}_d(n)|$ . They derived that $f_{n-2}(n)=2^{n}-(n-1)n-2$ and $f_n(2n)=C_n$ , where $C_n$ is the $n$ -th Catalan number. Mansour and Yan proved that $f_{n+1}(2n+1)=2^{n-2}nC_{n+1}$ . In this paper, we consider the problem of counting minimal permutations in $\mathcal{F}_d(n)$ with a prescribed set of ascents. We show that such structures are in one-to-one correspondence with a class of skew Young tableaux, which we call $2$ -regular skew tableaux. Using the determinantal formula for the number of skew Young tableaux of a given shape, we find an explicit formula for $f_{n-3}(n)$ . Furthermore, by using the Knuth equivalence, we give a combinatorial interpretation of a formula for a refinement of the number $f_{n+1}(2n+1)$ .

preprint2010arXiv

Noncrossing Linked Partitions and Large (3,2)-Motzkin Paths

Noncrossing linked partitions arise in the study of certain transforms in free probability theory. We explore the connection between noncrossing linked partitions and colored Motzkin paths. A (3,2)-Motzkin path can be viewed as a colored Motzkin path in the sense that there are three types of level steps and two types of down steps. A large (3,2)-Motzkin path is defined to be a (3,2)-Motzkin path for which there are only two types of level steps on the x-axis. We establish a one-to-one correspondence between the set of noncrossing linked partitions of [n+1] and the set of large (3,2)-Motzkin paths of length n. In this setting, we get a simple explanation of the well-known relation between the large and the little Schroder numbers.

preprint2010arXiv

On Stanley's Partition Function

Stanley defined a partition function t(n) as the number of partitions $λ$ of n such that the number of odd parts of $λ$ is congruent to the number of odd parts of the conjugate partition $λ'$ modulo 4. We show that t(n) equals the number of partitions of n with an even number of hooks of even length. We derive a closed-form formula for the generating function for the numbers p(n)-t(n). As a consequence, we see that t(n) has the same parity as the ordinary partition function p(n) for any n. A simple combinatorial explanation of this fact is also provided.

preprint2010arXiv

Partially 2-Colored Permutations and the Boros-Moll Polynomials

We find a combinatorial setting for the coefficients of the Boros-Moll polynomials $P_m(a)$ in terms of partially 2-colored permutations. Using this model, we give a combinatorial proof of a recurrence relation on the coefficients of $P_m(a)$ . This approach enables us to give a combinatorial interpretation of the log-concavity of $P_m(a)$ which was conjectured by Moll and confirmed by Kauers and Paule.

preprint2010arXiv

Partition Identities for Ramanujan's Third Order Mock Theta Functions

We find two involutions on partitions that lead to partition identities for Ramanujan's third order mock theta functions $ϕ(-q)$ and $ψ(-q)$ . We also give an involution for Fine's partition identity on the mock theta function f(q). The two classical identities of Ramanujan on third order mock theta functions are consequences of these partition identities. Our combinatorial constructions also apply to Andrews' generalizations of Ramanujan's identities.

preprint2010arXiv

Partitions and Partial Matchings Avoiding Neighbor Patterns

We obtain the generating functions for partial matchings avoiding neighbor alignments and for partial matchings avoiding neighbor alignments and left nestings. We show that there is a bijection between partial matchings avoiding three neighbor patterns (neighbor alignments, left nestings and right nestings) and set partitions avoiding right nestings via an intermediate structure of integer compositions. Such integer compositions are known to be in one-to-one correspondence with self-modified ascent sequences or $3\bar{1}52\bar{4}$ -avoiding permutations, as shown by Bousquet-Mélou, Claesson, Dukes and Kitaev.

preprint2010arXiv

Permutation Tableaux and the Dashed Permutation Pattern 32-1

We give a solution to a problem posed by Corteel and Nadeau concerning permutation tableaux of length n and the number of occurrences of the dashed pattern 32--1 in permutations on [n]. We introduce the inversion number of a permutation tableau. For a permutation tableau T and the permutation $π$ obtained from T by the bijection of Corteel and Nadeau, we show that the inversion number of T equals the number of occurrences of the dashed pattern 32--1 in the reverse complement of $π$ . We also show that permutation tableaux without inversions coincide with L-Bell tableaux introduced by Corteel and Nadeau.

preprint2010arXiv

q-Hook Length Formulas for Signed Labeled Forests

A signed labeled forest is defined as a (plane) forest labeled by {1,2,..., n} along with minus signs associated to some vertices. Signed labeled forests can be viewed as an extension of signed permutations. We define the inversion number, the flag major index and the R-major index on signed labeled forests. They can be considered as type B analogues of the indices for labeled forests introduced by Bjorner and Wachs. The flag major index for signed labeled forests is based on the flag major index on signed permutations introduced by Adin and Roichman, whereas the R-major index for signed labeled forests is based on the R-major index that we introduce for signed permutations, which is closely related to the major defined by Reiner. We obtain q-hook length formulas by q-counting signed labelings of a given forest with respect to the above indices, from which we see that these three indices are equidistributed for signed labeled forests. Our formulas for the major indices and the inversion number are type B analogues of the formula due to Bjorner and Wachs. We also give a type D analogue with respect to the inversion number of even-signed labeled forests.

preprint2010arXiv

Ratio Monotonicity of Polynomials Derived from Nondecreasing Sequences

The ratio monotonicity of a polynomial is a stronger property than log-concavity. Let P(x) be a polynomial with nonnegative and nondecreasing coefficients. We prove the ratio monotone property of P(x+1), which leads to the log-concavity of P(x+c) for any $c\geq 1$ due to Llamas and Mart\'ınez-Bernal. As a consequence, we obtain the ratio monotonicity of the Boros-Moll polynomials obtained by Chen and Xia without resorting to the recurrence relations of the coefficients.

preprint2010arXiv

The 2-log-convexity of the Apery Numbers

We present an approach to proving the 2-log-convexity of sequences satisfying three-term recurrence relations. We show that the Apery numbers, the Cohen-Rhin numbers, the Motzkin numbers, the Fine numbers, the Franel numbers of order 3 and 4 and the large Schroder numbers are all 2-log-convex. Numerical evidence suggests that all these sequences are k-log-convex for any $k\geq 1$ possibly except for a constant number of terms at the beginning.

preprint2010arXiv

The Generating Function for the Dirichlet Series $L_m(s)$

The Dirichlet series $L_m(s)$ are of fundamental importance in number theory. Shanks defined the generalized Euler and class numbers in connection with these Dirichlet series, denoted by $\{s_{m,n}\}_{n\geq 0}$ . We obtain a formula for the exponential generating function $s_m(x)$ of $s_{m,n}$ , where m is an arbitrary positive integer. In particular, for m>1, say, $m=bu^2$ , where b is square-free and u>1, we prove that $s_m(x)$ can be expressed as a linear combination of the four functions $w(b,t)\sec (btx)(\pm \cos ((b-p)tx)\pm \sin (ptx))$ , where p is an integer satisfying $0\leq p\leq b$ , $t|u^2$ and $w(b,t)=K_bt/u$ with $K_b$ being a constant depending on b. Moreover, the Dirichlet series $L_m(s)$ can be easily computed from the generating function formula for $s_m(x)$ . Finally, we show that the main ingredient in the formula for $s_{m,n}$ has a combinatorial interpretation in terms of the m-signed permutations defined by Ehrenborg and Readdy. In principle, this answers a question posed by Shanks concerning a combinatorial interpretation for the numbers $s_{m,n}$ .

preprint2010arXiv

The Method of Combinatorial Telescoping

We present a method for proving q-series identities by combinatorial telescoping, in the sense that one can transform a bijection or a classification of combinatorial objects into a telescoping relation. We shall illustrate this method by giving a combinatorial proof of Watson's identity which implies the Rogers-Ramanujan identities.

preprint2009arXiv

An Operator Approach to the Al-Salam-Carlitz Polynomials

We present an operator approach to Rogers-type formulas and Mehler's formulas for the Al-Salam-Carlitz polynomials $U_n(x,y,a;q)$ . By using the q-exponential operator, we obtain a Rogers-type formula which leads to a linearization formula. With the aid of a bivariate augmentation operator, we get a simple derivation of Mehler's formula due to by Al-Salam and Carlitz, which requires a terminating condition on a ${}_3ϕ_2$ series. By means of the Cauchy companion augmentation operator, we obtain Mehler's formula in a similar form, but it does not need the terminating condition. We also give several identities on the generating functions for products of the Al-Salam-Carlitz polynomials which are extensions of formulas for Rogers-Szegö polynomials.

preprint2009arXiv

Random $k$ -noncrossing RNA Structures

In this paper we derive polynomial time algorithms that generate random $k$ -noncrossing matchings and $k$ -noncrossing RNA structures with uniform probability. Our approach employs the bijection between $k$ -noncrossing matchings and oscillating tableaux and the $P$ -recursiveness of the cardinalities of $k$ -noncrossing matchings. The main idea is to consider the tableaux sequences as paths of stochastic processes over shapes and to derive their transition probabilities.

preprint2009arXiv

The Ratio Monotonicity of the Boros-Moll Polynomials

In their study of a quartic integral, Boros and Moll discovered a special class of Jacobi polynomials, which we call the Boros-Moll polynomials. Kauers and Paule proved the conjecture of Moll that these polynomials are log-concave. In this paper, we show that the Boros-Moll polynomials possess the ratio monotone property which implies the log-concavity and the spiral property. We conclude with a conjecture which is stronger than Moll's conjecture on the $\infty$ -log-concavity.

preprint2007arXiv

Crossings and nesting in tangled-diagrams

A tangled-diagram over $[n]=\{1,...,n\}$ is a graph of degree less than two whose vertices $1,...,n$ are arranged in a horizontal line and whose arcs are drawn in the upper halfplane with a particular notion of crossings and nestings. Generalizing the construction of Chen {\it et.al.} we prove a bijection between generalized vacillating tableaux with less than $k$ rows and $k$ -noncrossing tangled-diagrams and study their crossings and nestings. We show that the number of $k$ -noncrossing and $k$ -nonnesting tangled-diagrams are equal and enumerate tangled-diagrams.

preprint1994arXiv

Restricted routing and wide diameter of the cycle prefix network

The cycle prefix network is a Cayley coset digraph based on sequences over an alphabet which has been proposed as a vertex symmetric communication network. This network has been shown to have many remarkable communication properties such as a large number of vertices for a given degree and diameter, simple shortest path routing, Hamiltonicity, optimal connectivity, and others. These considerations for designing symmetric and directed interconnection networks are well justified in practice and have been widely recognized in the research community. Among the important properties of a good network, efficient routing is probably one of the most important. In this paper, we further study routing schemes in the cycle prefix network. We confirm an observation first made from computer experiments regarding the diameter change when certain links are removed in the original network, and we completely determine the wide diameter of the network. The wide diameter of a network is now perceived to be even more important than the diameter. We show by construction that the wide diameter of the cycle prefix network is very close to the ordinary diameter. This means that routing in parallel in this network costs little extra time compared to ordinary single path routing.

William Y. C. Chen

Research overview

Is this your work?

71 publications

Breaking Cycles, the Odd Versus the Even

Cubic Equations Through the Looking Glass of Sylvester

Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences

The Log-Behavior of p(n)n\sqrt[n]{p(n)}np(n)​ and p(n)/nn\sqrt[n]{p(n)/n}np(n)/n​

Automorphisms of the cycle prefix digraph

Average Size of a Self-conjugate (s, t)-Core Partition

Context-free Grammars for Permutations and Increasing Trees

Finite Differences of the Logarithm of the Partition Function

Ramanujan-type Congruences for Overpartitions Modulo 16

Ramanujan-type Congruences for Overpartitions Modulo 5

Vacillating Hecke Tableaux and Linked Partitions

Zigzag Stacks and m-Regular Linear Stacks

Combinatorial Proof of the Inversion Formula on the Kazhdan-Lusztig R-Polynomials

Infinitely Log-monotonic Combinatorial Sequences

Linked Partitions and Permutation Tableaux

On Permutations with Bounded Drop Size

On the Positive Moments of Ranks of Partitions

Ordered Partitions Avoiding a Permutation of Length 3

Proof of a Conjecture of Hirschhorn and Sellers on Overpartitions

Proof of the Andrews-Dyson-Rhoades Conjecture on the spt-Crank

Ramanujan-type Congruences for Broken 2-Diamond Partitions Modulo 3

s-Inversion Sequences and P-Partitions of Type B

The spt-Crank for Ordinary Partitions

Zeta Functions and the Log-behavior of Combinatorial Sequences

An Overpartition Analogue of Bressoud's Theorem of Rogers-Ramanujan Type

Branden's Conjectures on the Boros-Moll Polynomials

Congruences of Multipartition Functions Modulo Powers of Primes

Context-free Grammars and Multivariate Stable Polynomials over Stirling Permutations

Decomposition of Triply Rooted Trees

Disposition Polynomials and Plane Trees

Euler's Partition Theorem with Upper Bounds on Multiplicities

On 021-Avoiding Ascent Sequences

On Pattern Avoiding Alternating Permutations

On the Number of Partitions with Designated Summands

Proof of Lassalle's Positivity Conjecture on Schur Functions

The Sorting Index and Permutation Codes

Combinatorial Telescoping for an Identity of Andrews on Parity in Partitions

Equivalence Classes of Full-Dimensional 0/1-Polytopes with Many Vertices

Extended Zeilberger's Algorithm for Identities on Bernoulli and Euler Polynomials

On Han's Hook Length Formulas for Trees

Oscillating Rim Hook Tableaux and Colored Matchings

The Abel-Zeilberger Algorithm

The Rogers-Ramanujan-Gordon Theorem for Overpartitions

2-Log-concavity of the Boros-Moll Polynomials

A Bijection between Atomic Partitions and Unsplitable Partitions

An Iterated Map for the Lebesgue Identity

Anti-lecture Hall Compositions and Overpartitions

Arithmetic Properties of Overpartition Pairs

Congruences for Bipartitions with Odd Parts Distinct

Han's Bijection via Permutation Codes

Interlacing Log-concavity of the Boros-Moll Polynomials

Involutions for Rogers-Ramanujan-Gordon Type Identities with Parity Restrictions

Labeled Ballot Paths and the Springer Numbers

Lattice Polynomials, 12312-Avoiding Partial Matchings and Even Trees

Minimal Permutations and 2-Regular Skew Tableaux

Noncrossing Linked Partitions and Large (3,2)-Motzkin Paths

On Stanley's Partition Function

Partially 2-Colored Permutations and the Boros-Moll Polynomials

Partition Identities for Ramanujan's Third Order Mock Theta Functions

Partitions and Partial Matchings Avoiding Neighbor Patterns

Permutation Tableaux and the Dashed Permutation Pattern 32-1

q-Hook Length Formulas for Signed Labeled Forests

Ratio Monotonicity of Polynomials Derived from Nondecreasing Sequences

The 2-log-convexity of the Apery Numbers

The Generating Function for the Dirichlet Series Lm(s)L_m(s)Lm​(s)

The Method of Combinatorial Telescoping

An Operator Approach to the Al-Salam-Carlitz Polynomials

Random kkk-noncrossing RNA Structures

The Ratio Monotonicity of the Boros-Moll Polynomials

Crossings and nesting in tangled-diagrams

Restricted routing and wide diameter of the cycle prefix network

See the researcher in context

Building this map preview

The Log-Behavior of $\sqrt[n]{p(n)}$ and $\sqrt[n]{p(n)/n}$

The Generating Function for the Dirichlet Series $L_m(s)$

Random $k$ -noncrossing RNA Structures