Enumerating pairs of permutations with the same up-down form

For each sequence q = {q_i} = ± 1, i = 1, …, n−1 let N_q = the number of permutations σ of 1, 2, …, n with up-down sequence sgn(σ_i+1 − σ_i) = q_i, i = 1,…, n−1. Clearly Σ_q (N_q/n!) =1 but what is the probability p_n = Σ_q (N_q/n!)² that two random permutations have the same up-down sequence? We show that p_n = (Kⁿ⁻¹1,1) where 1 = 1(x, y) ≡ 1 and Kⁿ⁻¹ is the iterated integral operator with Kφ(x, y) = ∫₀¹∫₀¹ K(x, y; x′, y′)φ(x′, y′) dx′ dy′ on L²[0, 1] × [0, 1] where K(x, y; x′, y′) is 1 if (x− x′)(y − y′) > 0 otherwise, and (f, g) = ∫₀¹∫₀¹fg. The eigenexpression of K yeilds p_n ∼ cαⁿ as n → ∞, where c ≈ 1.6, α ≈ 0.55.We also give a recursion formula for a polynomial whose coefficients are the frequencies of all the possible forms.     

Generalized cartan type k lie algebras in characteristic 0

The Lie algebra of Cartan type K which occurs as a subalgebra of the Lie algebra of derivations of the polynomial algebra F[x₀, x₁,…, x_n,x_n?1,…,x_?n], where F is a field of characteristic 0, was generalized by the first author to a class which included a subalgebra of the derivations of the Laurent polynomials F[x₀,x₁,…, x_n,x_?1,…,x_?n,X₀ ^?1x₁ ^-1,…,x_n ^?1,…,x_?1 ^?1…,x_?n ^?1]A further generalization of these algebras is the main topic of this paper. We show when these algebras are simple, determine all possible     

Application of the Szili method of interpolation on the roots of the Legendre polynomials

Let $$P_n (x) = \frac{{( - 1)^n }}{{2^n n!}}\frac{{d^n }}{{dx^n }}\left[ {(1 - x^2 )^n } \right]$$ be thenth Legendre polynomial. Letx ₁,x ₂,…,x _n andx*₁,x*₂,…,x* _n?1 denote the roots ofP _n (x) andP′ _n (x), respectively. Putx ₀=x*₀=?1 andx* _n =1. In this paper we prove the following theorem: Ify ₀,y ₁,…,y _n andy′ ₀,y′ ₁, …,y′ _n are two systems of arbitrary real numbers, then there exists a unique polynomialQ _2n+1(x) of degree at most 2n+1 satisfying the conditions $$Q_{2n + 1} (x_k^* ) = y_k and Q_{2n + 1}^\prime (x_k ) = y_k^\prime (k = 0,...,n).$$ .     

Polynomials arising in factoring generalized Vandermonde determinants II: A condition for monicity

In our previous paper [1], we observed that generalized Vandermonde determinants of the form V_n;ν(x₁,…,x_s) = |x_i^μk|, 1 ≤ i, k ≤ n, where the x_i are distinct points belonging to an interval [a, b] of the real line, the index n stands for the order, the sequence μ consists of ordered integers 0 ≤ μ₁ < μ₂ < … < μ_n, can be factored as a product of the classical Vandermonde determinant and a Schur function. On the other hand, we showed that when x = x_n, the resulting polynomial in x is a Schur function which can be factored as a two-factors polynomial: the first is the constant ∏_i=1ⁿ⁻¹ x_i^μ₁ times the monic polynomial ∏_i=1ⁿ⁻¹ (x − x_i, while the second is a polynomial P_M(x) of degree M = m_n−1 − n + 1. In this paper, we first present a typical application in which these factorizations arise and then we discuss a condition under which the polynomial P_M (x) is monic.     

A note on the average-case behavior of a simple differencing method for partitioning

Given n positive values x₁, x₂,…, x_n, we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. Karp and Karmarkar have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributions, a difference of O(n^−alogn), for some α > 0, with probability approaching 1 as n → ∞. Their work left open the question of how two simple and more natural implementations of the algorithm behaved. In this paper, under the assumption that the input values are uniformly distributed, we show that one of these algorithms is not nearly so effective, confirming empirical observations of Karp.     

Positive powers of certain conditionally negative definite matrices

We investigate the spectrum of matrices (∣x_i,−x_j∣^a)ⁿ_i,j=1 with α>0 and distinct x₁,…,x_n whichare relevant to the theory of scattered data interpolation and spline functions. The main result is the non-singularity of these matrices, which is based on the property that the number of negativeand positive eigenvalues of these matrices is independent of x₁,…,x_n. Oscillation properties of asubset of eigenvectors of these matrices are also obtained. For 2<α<4 and points x¹,…,xⁿ∈R²,a sufficient condition for the non-singularity of (∥xⁱ−x^j∥^α₂)ⁿ_i,j=1 is derived.     

Supplement to the Pál type (0; 0, 1) lacunary interpolation

Letx ₁, …,x _n be givenn distinct positive nodal points which generate the polynomial $$\omega _n (x) = \prod\limits_{i = 1}^n {(x - x_i )} .$$ Letx*₁, …,x* _n?1 be the roots of the derivativeω′ _n (x) and putx ₀=0. In this paper, the following theorem is proved: Ify ₀, …,y _n andy′₁, …,y′ _n?1 are arbitrary real numbers, then there exists a unique polynomialP _2n?1(x) of degree 2n?1 having the following interpolation properties: $$P_{2n - 1} (x_j ) = y_j (j = 0,...,n),$$ , $$P_{2n - 1}^\prime (x_j^* ) = y_j^\prime (j = 1,...,n - 1).$$ . This result gives the theoretical completion of the original Pál type interpolation process, since it ensures uniqueness without assuming any additional condition.     

Solution of the Szili type conjugate problem on the roots of the laguerre polynomials

Let ?1<α≤0 and let $$L_n^{(\alpha )} (x) = \frac{1}{{n!}}x^{ - \alpha } e^x \frac{{d^n }}{{dx^n }}(x^{\alpha + n} e^{ - x} )$$ be the generalizednth Laguerre polynomial,n=1,2,… Letx ₁,x ₂,…,x _n andx*₁,x*₂,…,x* _n?1 denote the roots ofL _n ^(α) (x) andL _n ^(α)′ (x) respectively and putx*₀=0. In this paper we prove the following theorem: Ify ₀,y ₁,…,y _n ?1 andy ₁ ^′ ,…,y _n ^′ are two systems of arbitrary real numbers, then there exists a unique polynomialP(x) of degree 2n?1 satisfying the conditions $$\begin{gathered} P\left( {x_k^* } \right) = y_k (k = 0,...,n - 1) \hfill \\ P'\left( {x_k } \right) = y_k^\prime (k = 1,...,n). \hfill \\ \end{gathered} $$ .     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

THE EXTREME POINTS OF SEVERAL CLASSES OF ANALYTIC FUNCTIONS

1Intr0ducti0nLetAden0tethesetofallfunctionsanalyticinA={z:Izl<1}.LetB={W:WEAandIW(z)l51}.Aisalocallyconvexlineaztop0l0gicalspacewithrespecttothetopologyofuniformconvergenceon`c0mpact8ubsetsofA-LetTh(c1,'tc.-1)={p(z):p(z)EA,Rop(z)>0,p(z)=1 clz czzz ' c.-lz"-l 4z" ',wherecl,',cn-1areforedcomplexconstants}.LetTh,.(b,,-..,b,-,)={p(z):P(z)'EAwithReP(z)>Oandp(z)=1 blz ' b.-lz"-l 4z" '-,wherebl,-'-jbu-1areffeedrealconstantsanddkarerealnumbersf0rk=n,n 1,'--}-LetTu(l1,'i'tI.-1)={…     

Computing Lyapunov constants for random recurrences with smooth coefficients

In recent years, there has been much interest in the growth and decay rates (Lyapunov constants) of solutions to random recurrences such as the random Fibonacci sequence x_n+1=±x_n±x_n−1. Many of these problems involve nonsmooth dynamics (nondifferentiable invariant measures), making computations hard. Here, however, we consider recurrences with smooth random coefficients and smooth invariant measures. By computing discretised invariant measures and applying Richardson extrapolation, we can compute Lyapunov constants to 10 digits of accuracy. In particular, solutions to the recurrence x_n+1=x_n+c_n+1x_n−1, where the {c_n} are independent standard normal variables, increase exponentially (almost surely) at the asymptotic rate (1.0574735537…)ⁿ. Solutions to the related recurrences x_n+1=c_n+1x_n+x_n−1 and x_n+1=c_n+1x_n+d_n+1x_n−1 (where the {d_n} are also independent standard normal variables) increase (decrease) at the rates (1.1149200917…)ⁿ and (0.9949018837…)ⁿ, respectively.     

On the rational recursive sequence x_{n+1}=\frac{\alpha+\beta x_{n-k}}{\gamma-x_{n}}

In this paper, we investigate the global asymptotic stability, the periodicity nature and the boundedness character of the positive solutions of the difference equation x _n+1=(α+β x _n?k )/(γ?x _n ) where n=0,1,2,… and k∈{1,2,…}. The parameters α≥0, γ,β>0 and the initial conditions x _?k , x _?k+1,…,x _?1,x ₀ are real positive numbers. We show that the positive equilibrium point of this equation is a global attractor with a basin that depends on certain conditions posed on the coefficients α,β,γ.     

Analyzing Ek|Er|c queues

In this paper we study a system consisting of c parallel identical servers and a common queue. The service times are Erlang-r distributed and the interarrival times are Erlang-k distributed. The service discipline is first-come first-served. The waiting process may be characterized by (n₋₁, n₀, n₁,…, n_c) where n₋₁ represents the number of remaining arrival stages, n₀ the number of waiting jobs and n_i, i = 1,…, c, the number of remaining service stages for server i. Bertsimas has proved that the equilibrium probability for saturated states (i.e. states with all servers busy) can be written as a linear combination of geometric terms with n₀ as exponent. In the present paper it is shown that the coefficients also have a geometric form with respect to n₋₁, n₁, …, n_c. It is also shown how the factors may be found efficiently. The present paper uses a direct approach for solving the equilibrium equations rather than a generating function approach as Bertsimas does. The direct approach is based on separation of variables and has been inspired by previous work of two of the authors on the shortest queue problem in particular and the two-dimensional random walk more generally. The characterization of the equilibrium probabilities leads to exact expressions for performance measures such as the moments of the queue length and the waiting time, which are useful for numerical computations. Numerical results are presented.     

Lyapunov equations and Gram matrices

If p is a polynomial with all roots inside the unit disc and C its companion matrix, then the Lyapunov equation

$\text{X ? C}{}^1\text{XC = P}$

has a unique solution for every positive semidefinite matrix P. We characterize sets of vectors x₀,…,x_n?1 and y₀,…,y_n?1 such that X = G(x₀,…,x_n?1)= G(y₀,…, y_n?1)^-1. Geometrical connections between such bases and contractions with one- dimensional defect spaces are established.     

On the polynomial mixed 0–1 fractional programming problems

This paper proposes a new method of solving polynomial mixed 0–1 fractional programming (P01FP) problems to obtain a global optimum. Given a polynomial 0–1 term x₁x₂,…,x_ny, where x_i is a 0–1 variable and y is a continuous variable; we develop a linearization technique to transfer the x₁x₂,…,x_ny term into a set of mixed 0–1 linear inequalities. Based on this technique, the P01FP can then be solved by a branch-and-bound method to obtain the global solution.     

On maximal antichains consisting of sets and their complements

Let 1 ? k₁ ? k₂ ? … ? k_n be integers and let S denote the set of all vectors x = (x₁, x₂, …, x_n) with integral coordinates satisfying 0 ? x_i ? k_i, i = 1, 2, …, n. The complement of x is (k₁ ? x₁, k₂ ? x₂, …, k_n ? x_n) and a subset X of S is an antichain provided that for any two distinct elements x, y of X, the inequalities x_i ? y_i, i = 1, 2, …, n, do not all hold. We determine an LYM inequality and the maximal cardinality of an antichain consisting of vectors and its complements. Also a generalization of the Erdös-Ko-Rado theorem is given.     

A product quadrature algorithm by Hermite interpolation

This paper is concerned with numerical integration of ∫¹₋₁f(x)k(x)dx by product integration rules based on Hermite interpolation. Special attention is given to the kernel k(x) = e^iτx, with a view to providing high precision rules for oscillatory integrals. Convergence results and error estimates are obtained in the case where the points of integration are zeros of p_n(W; x) or of (1 − x²)p_n−2(W; x), where p_n(W; x), n = 0, 1, 2…, are the orthonormal polynomials associated with a generalized Jacobi weight W. Further, examples are given that test the performance of the algorithm for oscillatory weight functions.     

Linear combinations of Hermitian and real symmetric matrices

This paper, by purely algebraic and elementary methods, studies useful criteria under which the quadratic forms x′Ax and x′Bx, where A,B are n × n symmetric real matrices and x′=(x₁,x₂, …,x_n)≠(0,0,0,0, …,0), can vanish simultaneously and some real linear combination of A,B can be positive definite. Analogous results for hermitian matrices have also been discussed. We have given sufficient conditions on m real symmetric matrices so that some real linear combination of them can be positive definite.     

Centralizers of generalized derivations on multilinear polynomials in prime rings

Let R be a prime ring of characteristic different from 2, with Utumi quotient ring U and extended centroid C, δ a nonzero derivation of R, G a nonzero generalized derivation of R, and f(x ₁, …, x _n ) a noncentral multilinear polynomial over C. If δ(G(f(r ₁, …, r _n ))f(r ₁, …, r _n )) = 0 for all r ₁, …, r _n ∈ R, then f(x ₁, …, x _n )² is central-valued on R. Moreover there exists a ∈ U such that G(x) = ax for all x ∈ R and δ is an inner derivation of R such that δ(a) = 0.