Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

The number of lines determined by a polygon

Given a polygon P in the Euclidean plane, what can be said about the number of lines in the plane which contain at least one edge of P? If P has n edges, it is easy to see that at most n lines contain an edge of P. Further, any convex polygon with n edges provides an example of such a situation. The question of interest here is what is the smallest number of lines, each containing one or more edges, which may be determined by a polygon with n edges? This number is not n and in fact does not even grow like some constant, of necessity less than one, times n. Rather, it grows like √2n. We are actually able to determine this minimum exactly for most values of n and to within one for all values of n.     

Triangulations of orientable surfaces by complete tripartite graphs

Orientable triangular embeddings of the complete tripartite graph K_n,n,n correspond to biembeddings of Latin squares. We show that if n is prime there are at least e^{nlnn-n(1+o(1))} nonisomorphic biembeddings of cyclic Latin squares of order n. If n=kp, where p is a large prime number, then the number of nonisomorphic biembeddings of cyclic Latin squares of order n is at least e^{plnp-p(1+lnk+o(1))}. Moreover, we prove that for every n there is a unique regular triangular embedding of K_n,n,n in an orientable surface.     

Partitions weighted by the parity of the crank

The ‘crank’ is a partition statistic which originally arose to give combinatorial interpretations for Ramanujan's famous partition congruences. In this paper, we establish an asymptotic formula and a family of Ramanujan type congruences satisfied by the number of partitions of n with even crank Me(n) minus the number of partitions of n with odd crank Mo(n). We also discuss the combinatorial implications of q-series identities involving Me(n)−Mo(n). Finally, we determine the exact values of Me(n)−Mo(n) in the case of partitions into distinct parts. These values are at most two, and zero for infinitely many n.     

Counting permutations by their alternating runs

We find a formula for the number of permutations of [n] that have exactly s runs up and down. The formula is at once terminating, asymptotic, and exact. The asymptotic series is valid for n→∞, uniformly for s?(1−?)n/logn (?>0).     

An infinite family of Legendrian torus knots distinguished by cube number

For a knot K the cube number is a knot invariant defined to be the smallest n for which there is a cube diagram of size n for K. There is also a Legendrian version of this invariant called the Legendrian cube number. We will show that the Legendrian cube number distinguishes the Legendrian left hand torus knots with maximal Thurston-Bennequin number and maximal rotation number from the Legendrian left hand torus knots with maximal Thurston-Bennequin number and minimal rotation number.     

Bounds for sorting by prefix reversal

For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) S_n. We show that $\text{?(n)?}\text{(5n+5)}\text{3}$, and that $\text{?(n)?}\text{17n}\text{16}$ for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey $\text{3n}\text{2?1}\text{?g(n)?2n+3}$.     

Generation of a random partition of a finite set by an urn model

A random partition of N_n = {1,…,n} may be generated by putting the elements of N_n at random into a stochastic number of cells. This representations is used to prove asymptotic results about the random partition for n → ∞.     

On the number of transversals in Cayley tables of cyclic groups

It is well known that if n is even, the addition table for the integers modulo n (which we denote by B_n) possesses no transversals. We show that if n is odd, then the number of transversals in B_n is at least exponential in n. Equivalently, for odd n, the number of diagonally cyclic latin squares of order n, the number of complete mappings or orthomorphisms of the cyclic group of order n, the number of magic juggling sequences of period n and the number of placements of n non-attacking semi-queens on an n×n toroidal chessboard are at least exponential in n. For all large n we show that there is a latin square of order n with at least (3.246)ⁿ transversals.We diagnose all possible sizes for the intersection of two transversals in B_n and use this result to complete the spectrum of possible sizes of homogeneous latin bitrades.We also briefly explore potential applications of our results in constructing random mutually orthogonal latin squares.     

On approximation of real numbers by algebraic numbers of bounded degree

Dirichlet proved that for any real irrational number ξ there exist infinitely many rational numbers p/q such that |ξ−p/q|<q⁻². The correct generalization to the case of approximation by algebraic numbers of degree ?n, n>2, is still unknown. Here we prove a result which improves all previous estimates concerning this problem for n>2.     

Enumeration of words by their number of mistakes

Consider all words in {1,…,n}. A fixed set of words is labeled as the set of “mistakes”. A generating function for the number of words with m₁1's,…,m_nn's and k mistakes is given. This generalizes a result of Gessel who considered the case where all the mistakes are two-lettered. A similar result has been independently obtained by Goulden and Jackson.     

On approximation by polynomials increasing to the right of the interval

We obtain sufficient conditions on a real valued function ?, continuous on [0, + ∞), to insure that, for some nonnegative integer n, there is a nonnegative number r(n) so that for any r ? r(n), the polynomial of best approximation to ? on [0, r] from π_n is increasing and nonnegative on [r, + ∞). Here, π_n denotes the set of all real polynomials of degree n or less. The proofs of Theorems 1 and 2 use only properties of Lagrange interpolation while that of Theorem 3 employs results on the location of interpolation points in Chebyshev approximation.     

Permutation groups generated by cycles of fixed length

Combinatorial conditions on a set of cycles of fixed degree inS _n are studied, so that they generateA _n orS _n . It is shown thatA _n orS _n is so generated if and only if a graph associated with the set of cycles is connected, provided two of the cycles satisfy certain, not too restrictive, criteria. As a corollary, the minimum number of cycles of degreem ≧ 2 that generateA _n or S_n is determined.     

Approximation of convex bodies by polytopes with uniformly bounded valences

Given any convex bodyK in Euclideann-spaceR ⁿ and any number ?>0, does there always exist a polytopeP(K, ?)?R ⁿ such that the number of vertices of a facet ofP and the number of facets meeting in a common vertex are bounded by a constant depending on the dimensiond only and such that the Hausdorff-distance ? (K, P) ofK andP is less than ?? This question of Ewald posed at the Durham symposium in 1975 is answered in the affirmative.     

Covering all triples on n marks by disjoint Steiner systems

Let q be a number all whose prime factors divide integers of the form 2^s ? 1, s odd. If n = q + 2, the (₃ⁿ) triples on n marks can be partitioned into q sets, each forming a Steiner triple system.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

Characterization of the trace by monotonicity inequalities

Let ?be a positive linear functional on the algebra of n × n complex matrices and p be a number greater than 1. The main result of the paper says that if for any pair A, B of positive semi-definite n × n matrices with A ? B the inequality ?(A^p) ? ?(B^p) holds true, then ?is a nonnegative scalar multiple of the trace.     

Simultaneous approximation to algebraic numbers by elements of a number field

A special case of the main result is as follows. Given a number fieldK a number ?>0 and real or complex algebraic numbers ξ₁,...,ξ _n with 1, ξ₁,...,ξ _n linearly independent overK, there are only finitely many α=(α₁,...,α _n ) with components inK and with |ξ₁,...,α₁| whereH(α) is a suitably defined height.     

Approximating reals by sums of rationals

We consider the question of approximating any real number α by sums of n rational numbers with denominators 1?q₁,q₂,…,qn?N. This leads to inquiries on approximating a real number by rational numbers with a prescribed number of prime factors in the denominator as well as by rational numbers with smooth denominator.     

Approximation of curves by polygons

Let A be a smooth curve in a Euclidean space E given by an arc length parametrization f: [0, 1] → E. Let π_n = {0 = t₀ ≤ t₁ ≤ … ≤ t_n = 1} be a partition of [0, 1] and let P_n be the polygon with vertices f(t₀), f(t₁),…, f(t_n). Let L(A) and L(P_n) denote the lengths of A and P_n, respectively. The paper investigates the behavior of n² |L(A) ? L(P_n)| when the partition π_n is induced by the sequence nθ(mod 1) for some irrational number θ. It turns out that this behavior depends on the partial quotients of the continued fraction expansion of θ.