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 → ∞.     

Sorting by insertion of leading elements

Consider the operation on permutations consisting of removing the leading element and inserting it somewhere in the string. The number of such operations required to sort a permutation σ of {1,…,n} into increasing order is n - k, where k is the largest integer such that the last k entries of σ form an increasing sequence. There is a deterministic version of the problem, in which the leading element is always inserted into the position equal to its value, and the process ends when 1 reaches the front. The permutation requiring the greatest number of steps to termination is 23…n1, and it requires 2ⁿ⁻¹ − 1 steps.     

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.     

On representations by determinants of P(n) and Pm(n)

P(n) and P_m(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For P_m(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and P_m(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant.     

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.     

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.     

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.     

Combinatorial families enumerated by quasi-polynomials

We say that the sequence (an) is quasi-polynomial in n if there exist polynomials P₀,…,Ps−1 and an integer n₀ such that, for all n?n₀, an=Pi(n) where . We present several families of combinatorial objects with the following properties: Each family of objects depends on two or more parameters, and the number of isomorphism types of objects is quasi-polynomial in one of the parameters whenever the values of the remaining parameters are fixed to arbitrary constants. For each family we are able to translate the problem of counting isomorphism types of objects into the problem of counting integer points in a union of parametrized rational polytopes. The families of objects to which this approach is applicable include combinatorial designs, linear and unrestricted codes, and dissections of regular polygons.     

Fast enumeration of words generated by Dyck grammars

The problem of enumerating and denumerating words generated by Dyck grammars arises in the work of compilers for high-level programming languages and a number of other applications. The present paper proposes an algorithm for the fast enumeration and denumeration of words of Dyck languages; the complexity of this algorithm per one symbol of enumerated words is O(log³ n log log n) bit operations, provided that the Schönhage-Strassen multiplication and division algorithmis used. The well-knownmethods applied earlier possess complexityO(n) per one symbol of enumerated words. The construction of the proposed algorithm is based on the Ryabko method.     

Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite Graphs

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of ${n^{an^2}}$ nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph K _n,n,n and the complete graph K _n for linear classes of values of n and suitable constants a. Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of n were of the form ${2^{an^2}.}$ We remark that trivial upper bounds are ${n^{n^2/3}}$ in the case of complete graphs K _n and ${n^{2n^2}}$ in the case of complete tripartite graphs K _n,n,n .