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 1-3-2 Permutations and Generalized Patterns

Recently, Babson and Steingrimsson (see [2]) introduced generalized permutations patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We study generating functions for the number of permutations on n letters avoiding 1-3-2 (or containing 1-3-2 exactly once) and an arbitrary generalized pattern t \tau on k letters, or containing t \tau exactly once. In several cases, the generating function depends only on k and can be expressed via Chebyshev polynomials of the second kind, and the generating function of Motzkin numbers.     

Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.     

Forest-Like Permutations

Given a permutation , construct a graph G _π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G _π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G _π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.     

Quasi-symmetric functions and up–down compositions

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up–down permutations for compositions with parts in {1,…,n}. Cristea and Prodinger (2008/2009) [7] studied additional analogues for compositions with unbounded parts. We show that the results of Carlitz, Rawlings, and Cristea and Prodinger on up–down compositions are special cases of four different analogues of generalized Euler numbers for compositions. That is, for any s≥2, we consider classes of compositions that can be divided into an initial set of blocks of size s followed by a block of size j where 0≤j≤s−1. We then consider the classes of such compositions where all the blocks are strictly increasing (weakly increasing) and there are strict (weak) decreases between blocks. We show that the weight generating functions of such compositions w=w₁?w_m, where the weight of w is , are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.     

Enumeration of rises and falls by position

Let π=(π₁, π₂,…,π_n) denote a permutation of Z_n = {1, 2,…, n}. The pair (π_i, π_i+1) is a rise if π_i<π_i+1 or a fall if π_i>π_i+1. Also a conventional rise is counted at the beginning of π and a conventional fall at the end. Let k be a fixed integer ≥ 1. The rise π_i,π_i+1 is said to be in a in a j (mod k) position if i ≡ j (mod k); similarly for a fall. The conventional rise at the beginning is in a 0 (mod k) position, while the conventional fall at the end is in an n (mod k) position. Let $\text{P}{}_{\mathrm{n}}\text{≡P}{}_{\mathrm{n}}\text{(r}{}_0\text{,…,r}{}_{\mathrm{k}}\text{?1,?}{}_0\text{,…,?;}{}_{\mathrm{k}}\text{?1)}$ denote the number of permutations having r_i rises i (mod k) positions and ?;_i falls in i (mod k) positions. A generating function for P_n is obtained. In particular, for k = 2 the generating function is quite explicit and also, for certain special cases when k = 4.     

Enumeration of up-down sequences

Generalizing the notion of up-down permutations, the author considers sequences σ = (a₁, a₂, , α_N) of length N = s₂ + s₂ ++ s_n, where α_i ∈ {1, 2,n } and the element j occurs exactly s_j times. The repeated elements of a are labeled i, i′, i″, and it is assumed that they occur in a m natural order. Generating functions for the number of up-down sequences are constructed. Making use of the generating functions, explicit formulas for the number of up-down sequences are obtained.     

Restricted 132-Alternating Permutations and Chebyshev Polynomials

A permutation is said to be alternating if it starts with rise and then descents and rises come in turn. In this paper we study the generating function for the number of alternating permutations on n letters that avoid or contain exactly once 132 and also avoid or contain exactly once an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.AMS Subject Classification: 05A05, 05A15, 30B70, 42C05.     

Counting permutations by successions and other figures

Let π=(π(1), π(2),…, π(n)) be a permutation of the arbitrary n-set S of positive integers. A p-succession (alternately, p-rise) in π is any pair π(i), π(i+1) with π(i+1)=π(i)+1p, i=1,2,…, n-1 (alternately, π(i+1)?π(i)+p). A succession (alternately, rise) is just a p-succession (alternately, p-rise) with p=1. A p-run in π is a subsequence i, i+1,…,i+p-1 of the permutation π. We show that the number of permutations of S which have precisely α rises and β successions depends only on n=¦S¦, α, β, and l, where l is the number of maximal subsets {i,i+1,…,i+j)} of S, and determine an explicit recursion and generating function for these numbers. The same methodology is applied to count permutations of S by number of rises and figures of a more general type, where a specific criterion characterizes such figures. As a special case, we obtain the generating function when the figure is a p-run. Finally, we enumerate permutations of S by number of p-successions. Additional results are provided relating this particular enumeration problem to the special case of ordinary successions (p=1).     

Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation

A set of results concerning goodness of approximation and convergence in norm is given for L_∞ and L₁ approximation of multivariate functions on hypercubes. Firstly the trigonometric polynomial formed by taking a partial sum of a multivariate Fourier series and the algebraic polynomials formed either by taking a partial sum of a multivariate Chebyshev series of the first kind or by interpolating at a tensor product of Chebyshev polynomial zeros are all shown to be near-best L_∞ approximations. Secondly the trigonometric and algebraic polynomials formed by taking, respectively, a partial sum of a multivariate Fourier series and a partial sum of a multivariate Chebyshev series of the second kind are both shown to be hear-best L₁ approximations. In all the cases considered, the relative distance of a near-best approximation from a corresponding best approximation is shown to be at most of the order of Π log n_j, where n_j (j = 1, 2,…, N) are the respective degrees of approximation in the N individual variables. Moreover, convergence in the relevant norm is established for all the sequences of near-best approximations under consideration, subject to appropriate restrictions on the function space.     

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation π such that in any prefix of π the descent number is not more than the ascent number. By using a reversal-concatenation map, we (i) give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, (ii) connect this distribution and the joint distribution (pk, des) over ordinary permutations in terms of generating functions, and (iii) confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.     

Product integration of logarithmic singular integrands based on cubic splines

This paper is concerned with the practical evaluation of the product integral ∫¹_{? 1}f(x)k(x)dx for the case when k(x) = In|x - λ|, λ? (?1, +1) and f is bounded in [?1, +1]. The approximation is a quadrature rule

where the weights {w_n,n,i} are chosen to be exact when f is given by a linear combination of a chosen set of functions {φ_n,j}. In this paper the functions {φ_n,j} are chosen to be cubic B-splines. An error bound for product quadrature rules based on cubic splines is provided. Examples that test the performance of the product quadrature rules for different choices of the function are given. A comparison is made with product quadrature rules based on first kind Chebyshev polynomials.     

Partial γ-positivity for quasi-Stirling permutations of multisets

We prove that the enumerative polynomials of quasi-Stirling permutations of multisets with respect to the statistics of plateaux, descents and ascents are partial γ-positive, thereby confirming a recent conjecture posed by Lin, Ma and Zhang. This is accomplished by proving the partial γ-positivity of the enumerative polynomials of certain ordered labeled trees, which are in bijection with quasi-Stirling permutations of multisets. As an application, we provide an alternative proof of the partial γ-positivity of the enumerative polynomials on Stirling permutations of multisets.     

Polynomials orthogonal on the semicircle,II

Generalizing previous work [2], we study complex polynomials {π _k },π _k (z)=z ^k +?, orthogonal with respect to a complex-valued inner product (f,g)=∫ ₀ ^π f(e ^iθ)g(e ^iθ)w(e ^iθ)dθ. Under suitable assumptions on the “weight function”w, we show that these polynomials exist whenever Re ∫ ₀ ^π w(e ^iθ)dθ≠0, and we express them in terms of the real polynomials orthogonal with respect to the weight functionw(x). We also obtain the basic three-term recurrence relation. A detailed study is made of the polynomials {π _k } in the case of the Jacobi weight functionw(z)=(1?z)^α(1+z)^β, α>?1, and its special case \(\alpha = \beta = \lambda - \tfrac{1}{2}\) (Gegenbauer weight). We show, in particular, that for Gegenbauer weights the zeros ofπ _n are all simple and, ifn≥2, contained in the interior of the upper unit half disc. We strongly suspect that the same holds true for arbitrary Jacobi weights. Finally, for the Gegenbauer weight, we obtain a linear second-order differential equation forπ _n (z). It has regular singular points atz=1, ?1, ∞ (like Gegenbauer's equation) and an additional regular singular point on the negative imaginary axis, which depends onn.     

Moments of square-integrable functions

This paper is motivated by [2], where we have given necessary and sufficient conditions for a given basis P in the space of polynomials to be orthogonal with respect to the measure ϱdφ for a certain function ϱ ϵ L₂(dφ). Let P = {p_i: i = 0, 1, …}, p₀ = 1. Then the conditions are (1) a multivariate analog of the three-term recurrence relation holds, see Section 4 for details; and (2) {q_i = ∑_{j = 0}^∞ c_ij P_j, i = 0, 1, …} is a φ-orthonormal basis in the space of polynomials for some coefficients c_ij such that ∑_{i = 0}^∞ c_i0² <-∞. This paper provides an algebraic condition (a condition on the coefficients c_i0) such that ϱ satisfies ∥p∥ <B, Bϵ (0, ∞], and has a cone-positivity property. In particular, our results imply that ϱ is nonnegative a.e. if ∑_{i = 0}^∞ c_i0² < ∞ and ∑_{jϵ Sk} c_j0 q_j defines nonnegative polynomials for certain finite sets S₁, S₂, … of integers.     

Monotonicity of quotients of theta functions related to an extremal problem on harmonic measure

We prove that for fixed u and v such that u,v∈[0,1/2), the quotients θj(u|iπt)/θj(v|iπt), j=1,2,3,4, of the theta functions are monotone on 0<t<∞. The case v=0 has been used by the second author to study a generalization of Gonchar's problem on harmonic measure of radial slits.     

Padé-type approximants with orthogonal generating polynomials

The interpolation of the function x → 1/(1 ? xt) generating the series f(t) = ∑^∞_{i = 0}c_itⁱ at the zeros of an orthogonal polynomial with respect to a distribution d α satisfying some conditions will give us a process for accelerating the convergence of f_n(t) = ∑ⁿ_{i = 0}c_itⁱ. Then, we shall see that the polynomial of best approximation of x → 1/(1 ? xt) over some interval or its development in Chebyshev polynomials T_n or U_n are only particular cases of the main theorem.At last, we shall show that all these processes accelerate linear combinations with positive coefficients of totally monotonic and oscillating sequences.     

Representations for partially exchangeable arrays of random variables

Consider an array of random variables (X_i,j), 1 ≤ i,j < ∞, such that permutations of rows or of columns do not alter the distribution of the array. We show that such an array may be represented as functions f(α, ξ_i, η_j, λ_i,j) of underlying i.i.d, random variables. This result may be useful in characterizing arrays with additional structure. For example, we characterize random matrices whose distribution is invariant under orthogonal rotation, confirming a conjecture of Dawid.