A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

The generating functions of the rank and crank modulo 8

Let N(i,m;n) be the number of partitions of n with rank (Dyson) congruent to i (mod m) and let M(j,m;n) be the number of partitions of n with crank (Andrews, Garvan) congruent to j (mod m). I give here the generating functions for the numbers N(i,8;n) and M(j,8;n). I suggest forms for the one hundred power series

Some formulae for the q-Bernoulli and Euler polynomials of higher order

The purpose of this paper is to give a proof of Kummer type congruence for the q-Bernoulli numbers of higher order, which is an answer to a part of the problem in a previous publication (see Indian J. Pure Appl. Math. 32 (2001) 1565-1570).     

Factorization of alternating sums of Virasoro characters

G. Andrews proved that if n is a prime number then the coefficients ak and ak+n of the product _∞(q,q)/_∞(qn,qn)=k_∑akqk have the same sign, see [G. Andrews, On a conjecture of Peter Borwein, J. Symbolic Comput. 20 (1995) 487-501]. We generalize this result in several directions. Our results are based on the observation that many products can be written as alternating sums of characters of Virasoro modules.     

Factors of the Gaussian coefficients

We present some simple observations on factors of the q-binomial coefficients, the q-Catalan numbers, and the q-multinomial coefficients. Writing the Gaussian coefficient with numerator n and denominator k in a form such that 2k?n by the symmetry in k, we show that this coefficient has at least k factors. Some divisibility results of Andrews, Brunetti and Del Lungo are also discussed.     

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy a_i,j=a_i−1,j−1+a_i−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K₂ is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (a_i,j)_1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (a_i,j)_2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.     

On discrete q-ultraspherical polynomials and their duals

A special case of the big q-Jacobi polynomials Pn(x;a,b,c;q), which corresponds to a=b=−c, is shown to satisfy a discrete orthogonality relation for imaginary values of the parameter a (outside of its commonly known domain 0<a<q⁻¹). Since Pn(x;qα,qα,−qα;q) tend to Gegenbauer (or ultraspherical) polynomials in the limit as q→1, this family represents another q-extension of these classical polynomials, different from the continuous q-ultraspherical polynomials of Rogers. For a dual family with respect to the polynomials Pn(x;a,a,−a;q) (i.e., for dual discrete q-ultraspherical polynomials) we also find new orthogonality relations with extremal measures.     

The Eulerian generating function of q-derangements

Let F_q denote the finite field with q elements. For nonnegative integers n,k, let d_q(n,k) denote the number of n×nF_q-matrices having k as the sum of the dimensions of the eigenspaces (of the eigenvalues lying in F_q). Let d_q(n)=d_q(n,0), i.e., d_q(n) denotes the number of n×nF_q-matrices having no eigenvalues in F_q. The Eulerian generating function of d_q(n) has been well studied in the last 20 years [Kung, The cycle structure of a linear transformation over a finite field, Linear Algebra Appl. 36 (1981) 141-155, Neumann and Praeger, Derangements and eigenvalue-free elements in finite classical groups, J. London Math. Soc. (2) 58 (1998) 564-586 and Stong, Some asymptotic results on finite vector spaces, Adv. Appl. Math. 9(2) (1988) 167-199]. The main tools have been the rational canonical form, nilpotent matrices, and a q-series identity of Euler. In this paper we take an elementary approach to this problem, based on Möbius inversion, and find the following bivariate generating function:

     

Exact solutions of multi-component nonlinear Schrödinger and Klein–Gordon equations

Applying the sec_q−tanh_q-method [Phys. Lett. A 298 (2002) 253], we find a class of exact solution of multi-component nonlinear Schrödinger and Klein–Gordon equations and generalize the correspond results in [Phys. Lett. A 298 (2002) 253] and [J. Phys. A: Math. Gen. 34 (2001) 4281].     

A q-summation formula,the continuous q-Hahn polynomials and the big q-Jacobi polynomials

Using a general q-summation formula, we derive a generating function for the q-Hahn polynomials, which is used to give a complete proof of the orthogonality relation for the continuous q-Hahn polynomials. A new proof of the orthogonality relation for the big q-Jacobi polynomials is also given. A simple evaluation of the Nassrallah–Rahman integral is derived by using this summation formula. A new q-beta integral formula is established, which includes the Nassrallah–Rahman integral as a special case. The q-summation formula also allows us to recover several strange q-series identities.     

A note on approximation properties of q-Durrmeyer operators

In this paper, the approximation properties of q-Durrmeyer operators D_n,q(f;x) for f∈C[0,1] are discussed. The exact class of continuous functions satisfying approximation process lim_n→∞D_n,q(f;x)=f(x) is determined. The results of the paper provide an elaboration of the previously-known ones on operators D_n,q.     

Stability of iterative procedures with errors for approximating common fixed points of a couple of q-contractive-like mappings in Banach spaces

Recently, Agarwal, Cho, Li and Huang [R.P. Agarwal, Y.J. Cho, J. Li, N.J. Huang, Stability of iterative procedures with errors approximating common fixed points for a couple of quasi-contractive mappings in q-uniformly smooth Banach spaces, J. Math. Anal. Appl. 272 (2002) 435-447] introduced the new iterative procedures with errors for approximating the common fixed point of a couple of quasi-contractive mappings and showed the stability of these iterative procedures with errors in Banach spaces. In this paper, we introduce a new concept of a couple of q-contractive-like mappings (q>1) in a Banach space and apply these iterative procedures with errors for approximating the common fixed point of the couple of q-contractive-like mappings. The results established in this paper improve, extend and unify the corresponding ones of Agarwal, Cho, Li and Huang [R.P. Agarwal, Y.J. Cho, J. Li, N.J. Huang, Stability of iterative procedures with errors approximating common fixed points for a couple of quasi-contractive mappings in q-uniformly smooth Banach spaces, J. Math. Anal. Appl. 272 (2002) 435-447], Chidume [C.E. Chidume, Approximation of fixed points of quasi-contractive mappings in Lp spaces, Indian J. Pure Appl. Math. 22 (1991) 273-386], Chidume and Osilike [C.E. Chidume, M.O. Osilike, Fixed points iterations for quasi-contractive maps in uniformly smooth Banach spaces, Bull. Korean Math. Soc. 30 (1993) 201-212], Liu [Q.H. Liu, On Naimpally and Singh's open questions, J. Math. Anal. Appl. 124 (1987) 157-164; Q.H. Liu, A convergence theorem of the sequence of Ishikawa iterates for quasi-contractive mappings, J. Math. Anal. Appl. 146 (1990) 301-305], Osilike [M.O. Osilike, A stable iteration procedure for quasi-contractive maps, Indian J. Pure Appl. Math. 27 (1996) 25-34; M.O. Osilike, Stability of the Ishikawa iteration method for quasi-contractive maps, Indian J. Pure Appl. Math. 28 (1997) 1251-1265] and many others in the literature.     

q-Bernstein polynomials and their iterates

Let B_n( f,q;x), n=1,2,… be q-Bernstein polynomials of a function f : [0,1]→C. The polynomials B_n( f,1;x) are classical Bernstein polynomials. For q≠1 the properties of q-Bernstein polynomials differ essentially from those in the classical case. This paper deals with approximating properties of q-Bernstein polynomials in the case q>1 with respect to both n and q. Some estimates on the rate of convergence are given. In particular, it is proved that for a function f analytic in {z: |z|<q+} the rate of convergence of {B_n( f,q;x)} to f(x) in the norm of C[0,1] has the order q⁻ⁿ (versus 1/n for the classical Bernstein polynomials). Also iterates of q-Bernstein polynomials {B_n^j_n( f,q;x)}, where both n→∞ and j_n→∞, are studied. It is shown that for q(0,1) the asymptotic behavior of such iterates is quite different from the classical case. In particular, the limit does not depend on the rate of j_n→∞.     

Symposium on combinatorial mathematics and optimal design

Let A₁,A₂,…,A_n be finite sets such that A_i?A_j for all i≠j. Let F be an intersecting family consisting of sets contained in some A_i, i=1,2,…,n. Chvátal conjectured that among the largest intersecting families, there is always a star. In this paper, we obtain another proof of a result of Schönheim: If A₁∩A₂∩?∩A_n≠?, then the conjecture is true. We also prove that if A_i∩A_jA_k = ? for all i≠j≠k≠i or if the independent system satisfies a hereditary tree structure, then the conjecture is also true.     

On the q-Bernstein polynomials of rational functions with real poles

The paper aims to investigate the convergence of the q  -Bernstein polynomials _Bn,q(f;x)$B_{n,q}(f;x)$ attached to rational functions in the case q>1$q>1$. The problem reduces to that for the partial fractions (x−α)^−j${(x-\alpha )}^{-j}$, j∈N$j\in \mathbb{N}$. The already available results deal with cases, where either the pole α   is simple or α≠q^−m$\alpha \ne q^{-m}$, m∈_N0$m\in {\mathbb{N}}_0$. Consequently, the present work is focused on the polynomials _Bn,q(f;x)$B_{n,q}(f;x)$ for the functions of the form f(x)=(x−q^−m)^−j$f(x)={(x-q^{-m})}^{-j}$ with j?2$j?2$. For such functions, it is proved that the interval of convergence of {_Bn,q(f;x)}$\{B_{n,q}(f;x)\}$ depends not only on the location, but also on the multiplicity of the pole – a phenomenon which has not been considered previously.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Log-concavity and LC-positivity

A triangle {a(n,k)}_0?k?n of nonnegative numbers is LC-positive if for each r, the sequence of polynomials is q-log-concave. It is double LC-positive if both triangles {a(n,k)} and {a(n,n−k)} are LC-positive. We show that if {a(n,k)} is LC-positive then the log-concavity of the sequence {xk} implies that of the sequence {zn} defined by , and if {a(n,k)} is double LC-positive then the log-concavity of sequences {xk} and {yk} implies that of the sequence {zn} defined by . Examples of double LC-positive triangles include the constant triangle and the Pascal triangle. We also give a generalization of a result of Liggett that is used to prove a conjecture of Pemantle on characteristics of negative dependence.     

New orthogonality relations for the continuous and the discrete q-ultraspherical polynomials

In a recent contribution [N.M. Atakishiyev, A.U. Klimyk, On discrete q-ultraspherical polynomials and their duals, J. Math. Anal. Appl. 306 (2005) 637-645], the so-named discrete q-ultraspherical polynomials were introduced as a specialization of the big q-Jacobi polynomials, and their orthogonality established for values of the parameter outside its commonly known domain but inside the range of validity of the conditions of Favard's theorem. In this paper we consider both the continuous and the discrete q-ultraspherical polynomials and we prove that their orthogonality is guaranteed for the whole range of the allowed parameters, even in those intriguing cases in which the three term recurrence relation breaks down. The presence of either the Askey-Wilson divided difference operator (in the continuous case), or the q-derivative operator (in the discrete one), provides the q-Sobolev character of the non-standard inner products introduced in our approach.     

Coloring some classes of mixed graphs

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i,x_j], c(x_i)≠c(x_j) and for every arc (x_p,x_q), c(x_p)<c(x_q). We will analyse the complexity status of this problem for some special classes of graphs.