Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

Restricted Dumont permutations, Dyck paths, and noncrossing partitions

We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain patterns of length 3 and 4 and give a natural bijection between 3142-avoiding Dumont permutations of the second kind and noncrossing partitions that uses cycle decomposition, as well as bijections between 132-, 231- and 321-avoiding Dumont permutations and Dyck paths. Finally, we enumerate Dumont permutations of the first kind simultaneously avoiding certain pairs of 4-letter patterns and another pattern of arbitrary length.     

Counting strings in Dyck paths

This paper deals with the enumeration of Dyck paths according to the statistic “number of occurrences of τ”, for an arbitrary string τ. In this direction, the statistic “number of occurrences of τ at height j” is considered. It is shown that the corresponding generating function can be evaluated with the aid of Chebyshev polynomials of the second kind. This is applied to every string of length 4. Further results are obtained for the statistic “number of occurrences of τ at even (or odd) height”.     

Ordered OLPS and CF Nth numerators

Definitions, theorems and examples are established for a general model of Laurent polynomial spaces and ordered orthogonal Laurent polynomial sequences, ordered with respect to ordered bases and orthogonal with respect to inner products ·=L°⊙ decomposed into transition functional ⊙ and strong moment functional, or, more generally, sample functional L couplings. Under this formulation that is shown to subsume those in the existing literature, new fundamental results are produced, including necessary and sufficient conditions for ordered OLPS to be sequences of nth numerators of continued fractions, in contrast to the classical result concerning nth denominators which is shown to hold only in special cases.     

Orthogonality and recurrence for ordered Laurent polynomial sequences

We consider orderings of nested subspaces of the space of Laurent polynomials on the real line, more general than the balanced orderings associated with the ordered bases {1,z⁻¹,z,z⁻²,z²,…} and {1,z,z⁻¹,z²,z⁻²,…}. We show that with such orderings the sequence of orthonormal Laurent polynomials determined by a positive linear functional satisfies a three-term recurrence relation. Reciprocally, we show that with such orderings a sequence of Laurent polynomials which satisfies a recurrence relation of this form is orthonormal with respect to a certain positive functional.     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

Sur la suite de polynômes orthogonaux associée à la formeu=δ c +λ(x−c) −1 L

We show that, ifL is regular, semi-classical functional, thenu is also regular and semi-classical for every complex λ, except for a discrete set of numbers depending onL andc. We give the second order linear differential equation satisfied by each polynomial of the orthogonal sequence associated withu. The cases whereL is either a classical functional (Hermite, Laguerre, Bessel, Jacobi) or a functional associated with generalized Hermite polynomials are treated in detail.

     

More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection G of n spanning subgraphs of K_n, all isomorphic to G, such that any two members of G share exactly one edge and every edge of K_n is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of K_n by a Hamiltonian path implies the existence of ODCs of K_4n and of K_16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of K_n by a Hamiltonian path for some n?3 and a two-colorable ODC of K_q by a Hamiltonian path for some prime power q?5, then there is an ODC of K_qn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths for all n of the form n=4k²+1 or n=(k²+1)/2 for some integer k.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

On the translation invariance of wavelet subspaces

An examination of the translation invariance of V₀ under dyadic rationals is presented, generating a new equivalence relation on the collection of wavelets. The equivalence classes under this relation are completely characterized in terms of the support of the Fourier transform of the wavelet. Using operator interpolation, it is shown that several equivalence classes are non-empty.     

Optimization over analytic functions whose founrier coefficients are constrained

This article gives necessary and sufficient conditions for local solutions to several very general constrained optimization problems over spaces of analytic functions.The results presented here have many applications, a particular instance of which is the sup-norm approximation of functions continuous on the unit circle in the complex plane by functions continuous on the circle and analytic on the open disk and whose Fourier coefficients satisfy prescribed linear relations.Also, the results in this article generalize Nevanlinna-Pick and Caratheodory-Fejer Interpolation results to allow values of arbitrary derivatives of functions to be assigned or merely bounded. Classically, NP and CF solve only problems with consecutive derivatives specified.In engineering, constraints on the Fourier coefficients of a frequency response function correspond to constraints on its time domain behavior. Indeed the central problems of control theory involve both time and frequency domain constraints. That is precisely what the results in this paper handle.Supported in part by the AFOSR and the NSF     

Electrostatic models for zeros of polynomials: Old,new, and some open problems

We give a survey concerning both very classical and recent results on the electrostatic interpretation of the zeros of some well-known families of polynomials, and the interplay between these models and the asymptotic distribution of their zeros when the degree of the polynomials tends to infinity. The leading role is played by the differential equation satisfied by these polynomials. Some new developments, applications and open problems are presented.     

Partial vexillarity and bigrassmannian permutations

We define two closely related notions of degree for permutation patterns of type 2143. These give rise to classes of “m-vexillary elements” in the symmetric group. Using partitions, the Ehresmann–Bruhat partial order, and sets constructed from permutation inversions, we characterize the m-vexillary elements. We relate the maximal bigrassmannian permutations in the (Ehresmann–Bruhat) order ideal generated by any given m-vexillary element w to the maximal rectangles contained in the shape of w.     

The maximal (C, α, β) operator of two-parameter walsh-fourier series

The two-parameter dyadic martingale Hardy spacesH _p are introduced and it is proved that the maximal operator of the (C, α, β) means of a two-dimensional Walsh-Fourier series is bounded from H_p to L_p (1/(α+1), 1/(β+1)<p<∞) and is of weak type (H ₁ ^# , L₁), where the Hardy space H ₁ ^# is defined by the hybrid maximal function. As a consequence, we obtain that the (C, α, β) means of a function f∈H ₁ ^# converge a.e. to the function in question. Moreover, we prove that the (C, α, β) means are uniformly bounded on H_p whenever 1/(α+1), 1/(β+1)<p<∞. Thus in case f∈H_p, the (C, α, β) means converge to f in H_p norm. The same results are proved for the conjugate (C, α, β) means, too.     

On rational approximation of algebraic functions

We construct a new scheme of approximation of any multivalued algebraic function f(z) by a sequence {r_n(z)}_n∈N of rational functions. The latter sequence is generated by a recurrence relation which is completely determined by the algebraic equation satisfied by f(z). Compared to the usual Padé approximation our scheme has a number of advantages, such as simple computational procedures that allow us to prove natural analogs of the Padé Conjecture and Nuttall's Conjecture for the sequence {r_n(z)}_n∈N in the complement CP¹?D_f, where D_f is the union of a finite number of segments of real algebraic curves and finitely many isolated points. In particular, our construction makes it possible to control the behavior of spurious poles and to describe the asymptotic ratio distribution of the family {r_n(z)}_n∈N. As an application we settle the so-called 3-conjecture of Egecioglu et al. dealing with a 4-term recursion related to a polynomial Riemann Hypothesis.