Search

A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set $A^n$ of all words of length $n$ over a $k$-letter alphabet $A$. A universal word, or u-word, is a linear, i.e. non-circular, version of the notion of a u-cycle, and it is defined similarly. Removing some words in $A^n$ may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in $A^n$, or the case when $k=2$ and $n\leq 4$., Comment: 17 pages, 4 tables

Recently, Z. W. Sun introduced a sequence $(S_n)_{n\geq 0}$, where $S_n=\frac{\binom{6n}{3n} \binom{3n}{n}}{2(2n+1)\binom{2n}{n}}$, and found one congruence and two convergent series on $S_n$ by {\tt{Mathematica}}. Furthermore, he proposed some related conjectures. In this paper, we first give analytic proofs of his two convergent series and then confirm one of his conjectures by invoking series expansions of $\sin(t\arcsin(x))$ and $\cos(t\arcsin(x)).$, 7 pages, to appear in Utilitas Math

Recently, Z. W. Sun introduced a new kind of numbers $S_n$ and also posed a conjecture on ratio monotonicity of combinatorial sequences related to $S_n$. In this paper, by investigating some arithmetic properties of $S_n$, we give an affirmative answer to his conjecture. Our methods are based on a newly established criterion and interlacing method for log-convexity, and also the criterion for ratio log-concavity of a sequence due to Chen, Guo and Wang., draft, 16 pages. arXiv admin note: text overlap with arXiv:1512.01008

A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $(x,y)\in E$. A triangular grid graph is a subgraph of a tiling of the plane with equilateral triangles defined by a finite number of triangles, called cells. A subdivision of a triangular grid graph is replacing some of its cells by plane copies of the complete graph $K_4$. Inspired by a recent elegant result of Akrobotu et al., who classified word-representable triangulations of grid graphs related to convex polyominoes, we characterize word-representable subdivisions of triangular grid graphs. A key role in the characterization is played by smart orientations introduced by us in this paper. As a corollary to our main result, we obtain that any subdivision of boundary triangles in the Sierpi\'{n}ski gasket graph is word-representable.

In this paper, we confirm a conjecture of Laborde-Zubieta on the enumeration of corners in tree-like tableaux. Our proof is based on Aval, Boussicault and Nadeau's bijection between tree-like tableaux and permutation tableaux, and Corteel and Nadeau's bijection between permutation tableaux and permutations. This last bijection sends a corner in permutation tableaux to an ascent followed by a descent in permutations, this enables us to enumerate the number of corners in permutation tableaux, and thus to completely solve L.-Z.'s conjecture. Moreover, we give a bijection between corners and runs of size 1 in permutations, which gives an alternative proof of the enumeration of corners. Finally, we introduce an ($a$,$b$)-analogue of this enumeration, and explain the implications on the PASEP., Comment: 18 pages, 7 figures

Recently, Z. W. Sun put forward a series of conjectures on monotonicity of combinatorial sequences in the form of $\{z_n/z_{n-1}\}_{n=N}^\infty$ and $\{\sqrt[n+1]{z_{n+1}}/\sqrt[n]{z_n}\}_{n=N}^\infty$ for some positive integer $N$, where $\{z_n\}_{n=0}^\infty$ is a sequence of positive integers. Luca and St\u{a}nic\u{a}, Hou et al., Chen et al., Sun and Yang proved some of them. In this paper, we give an affirmative answer to monotonicity of another new kind of number conjectured by Z. W. Sun via interlacing method for log-convexity and log-concavity of a sequence, and we also use the criterion for log-concavity of a sequence in the form of $\{\sqrt[n]{z_n}\}_{n=1}^\infty$ due to Xia., Comment: draft,13 pages. arXiv admin note: text overlap with arXiv:1512.01010

A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $A$ may contain an arbitrary number of occurrences of a special `joker' symbol $\Diamond\notin A$, which can be substituted by any symbol from $A$. For example, $u=0\Diamond 011100$ is a linear partial word for the binary alphabet $A=\{0,1\}$ and for $n=3$ (e.g., the first three letters of $u$ yield the subwords $000$ and $010$). We present results on the existence and non-existence of linear and cyclic universal partial words in different situations (depending on the number of $\Diamond$s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer., Discrete Mathematics & Theoretical Computer Science ; Vol. 19 no. 1 ; 1365-8050