Über Folgen,die BezÜglich Eines Mittels Rekurrent Sind

Let X be a convex subset of a finite-dimensional real vector space. A function M: X ^k → X is called a strict mean value, if M(x₁,…, x_k) lies in the convex hull of x₁,…, x_k), but does not coincide with one of its vertices. A sequence (x_n)_{n∈ ?} in X is called M-recursive if x_n+k = M(x_n, x_n+1,…, x_n+k?1) for all n. We prove that for a continuous strict mean value M every M-recursive sequence is convergent. We give a necessary and sufficient condition for a convergent sequence in X to be M-recursive for some continuous strict mean value M, and we characterize its limit by a functional equation. 39 B 72, 39 B 52, 40 A 05.     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

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.     

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.     

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).$$ .     

Convergence in distribution of quotients of order statistics

Let X₁, X₂,… be i.i.d. random variables with continuous distribution function F < 1. It is known that if 1 - F(x) varies regularly of order - p, the successive quotients of the order statistics in decreasing order of X₁,…,X_n are asymptotically independent, as n→∞, with distribution functions x^kp, k = 1, 2, …. A strong converse is proved, viz. convergence in distribution of this type of one of the quotients implies regular varation of 1 - F(x).     

More on the Erdös-Ko-Rado theorem for integer sequences

For positive integers n, k₁, k₂,…, k_n, t the probem: how many integer sequences (x₁, x₂,…, x_n) does it take such that 0 ? x_i ? k_i for 1 ? i ? n and any two sequences agree in at least t positions is investigated. Moreover all maximal systems of sequences are described. Results of Livingston and Frankl and Füredi are generalized also.     

Asymptotical Formulas For Solutions Of Linear Differential Systems Of The First Order

In this paper a system of differential equations y′ ? A(·,λ)y = 0 is considered on the finite interval [a,b] where λ ∈ C, A(·, λ):= λ A₁+ A ₀ +λ _?1A_?1(·,λ) and A ₁,A ₀, A _{? 1} are n × n matrix-functions. The main assumptions: A ₁ is absolutely continuous on the interval [a, b], A ₀ and A _{- 1}(·,λ) are summable on the same interval when ¦λ¦ is sufficiently large; the roots φ₁(x),…,φ_n (x) of the characteristic equation det (φ E — A ₁) = 0 are different for all x ∈ [a,b] and do not vanish; there exists some unlimited set Ω ? C on which the inequalities Re(λφ₁(x)) ≤ … ≤ Re (λφ_n(x)) are fulfilled for all x ∈ [a,b] and for some numeration of the functions φ_j(x). The asymptotic formula of the exponential type for a fundamental matrix of solutions of the system is obtained for sufficiently large ¦λ¦. The remainder term of this formula has a new type dependence on properties of the coefficients A ₁ (x), A _o (x) and A _{- 1} (x).     

A balancing strategy

Suppose x₁, x₂,…, is a sequence of vectors in R^k, 6X_n6⩽1, where 6(x₁,…,x_k)6 = max_j|x_j|. An algorithm is given for choosing a corresponding sequence ε₁, ε₂,…, of numbers, ε_n = ±1, so that 6ε₁x₁+ … +ε_nx_n6 remains small.     

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 α,β,γ.     

Permanence and Positive Periodic Solutions for Kolmogorov Competing Species Systems

We prove the existence of periodic solutions in a compact attractor of (R⁺)ⁿ for the Kolmogorov system x′_i = x_if_i(t, x₁, …, x_n), i = l, …, n in the competitive case. Extension to differential delay equations are con- sidered too. Applications are given to Lotka-Volterra systems with periodic coefficients.     

Monotonicity of permanents of certain doubly stochastic circulant matrices

Let p_k(A), k=2,…,n, denote the sum of the permanents of all k×k submatrices of the n×n matrix A. A conjecture of Ðokovi?, which is stronger than the famed van der Waerden permanent conjecture, asserts that the functions p_k((1?θ)J_n+;θA), k=2,…, n, are strictly increasing in the interval 0?θ?1 for every doubly stochastic matrix A. Here J_n is the n×n matrix all whose entries are equal $\text{1}\text{n}$. In the present paper it is proved that the conjecture holds true for the circulant matrices A=αI_n+ βP_n, α, β?0, α+;β=1, and $\text{A=}\text{(nJ}{}_{\mathrm{n}}\text{?I}{}_{\mathrm{n}}\text{?P}{}_{\mathrm{n}}\text{)}\text{(n?2)}$, where I_n and P_n are respectively the n×n identify matrix and the n×n permutation matrix with 1's in positions (1,2), (2,3),…, (n?1, n), (n, 1).     

Next-fit packs a list and its reverse into the same number of bins

Suppose the next-fit algorithm packs {x₁, x₂, …, x_n} into k identical bins. Under modest assumptions about what fits into a bin, we prove that next-fit also packs {x_n, …, x₂, x₁} into k bins. Thus, the next-fit decreasing algorithm uses the same number of bins as a next-fit increasing algorithm.     

The general divisor problem

Let Δ_k(x) = Δ(a₁, …, a_k; x) be the error term in the asymptotic formula for the summatory function of the general divisor function d(a₁, …, a_k; n), which is generated by ζ(a₁s) … ζ(a_ks) (1 ≤ a₁ ≤ … ≤ a_k are fixed integers). Precise omega results for the mean square integral ∫₁^x Δ_k²(x) dx are given, with applications to some specific divisor problems.     

Phase reconstruction from magnitude of band-limited multidimensional signals

In this paper, the problem of phase reconstruction from magnitude of multidimensional band-limited functions is considered. It is shown that any irreducible band-limited function f(z₁…,z_n), z_i ? $\text{C}$, i=1, …, n, is uniquely determined from the magnitude of f(x₁…,x_n): | f(x₁…,x_n)|, x_i ? $\text{R}$, i=1,…, n, except for (1) linear shifts: ^{i(α1z1+…+α_n2n+β}), β, α_i?$\text{R}$, i=1,…, n; and (2) conjugation: $\text{f}{}^1\text{(z}{}_1{}^1\text{,…,z}{}_{\mathrm{n}}{}^1\text{)}$.     

Infinite families of infinite families of congruences for k-regular partitions

Let k∈{10,15,20}, and let b _k (n) denote the number k-regular partitions of n. We prove for half of all primes p and any t≥1 that there exist p?1 arithmetic progressions modulo p ^2t such that b _k (n) is a multiple of 5 for each n in one of these progressions.     

Large minimal sets which force long arithmetic progressions

A classic theorem of van der Waerden asserts that for any positive integer k, there is an integer W(k) with the property that if W⩾W(k) and the set {1, 2,…, W} is partitioned into r classes C₁, C₂,…, C_r, then some C_i will always contain a k-term arithmetic progression. Let us abbreviate this assertion by saying that {1, 2,…, W}arrows AP(k) (written {1, 2,…, W} → AP(k)). Further, we say that a set Xcritically arrows AP(k) if:(i) X arrows AP(k); (ii) for any proper subset X′ ⊂ X, X′ does not arrow AP(k). The main result of this note shows that for any given k there exist arbitrarily large sets X which critically arrow AP(k).     

Symmetric words in metabelian groups

An n-ary word w(x₁,…,x_n) is called n-symmetric for a group G if w(g₁,…,g_n) = w(g_{σ 1},…,g_{σ n}) for all g₁,…,g_n in G and all permu¬tations a in the symmetric group S_n. In this note we describe 2 and 3-symmetric words in free metabelian groups and metabelian groups of nilpotency class c, for arbitrary c.     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.