共查询到20条相似文献,搜索用时 453 毫秒
1.
Joseph G. Deken 《Discrete Mathematics》1979,26(1):17-31
The length ln of a longest common subsequence before time n sequences (B11, B12, …) (B21, B22, …) is the cardinality of the largest increasing set of pairs of integers {(j1α, j2α)} such that ?1?α?ln, (B1j1α=B2j2α). If B1 and B2 are independent random sequences with co-ordinates i.i.d. uniform on {1, 2, …, k}, it follows from Kingman's subadditive ergodic theorem that the ratio ln/n converges to a constant ck a.s. A method of deriving lower bounds for the constants ck is given, the bounds obtained improving known lower bounds, for k>2. The rate of decrease of ck with k is shown to be no faster than 1/√k, contrasting with P{B1i?B2i}=1/k. Finally, an alternative method of deriving lower bounds is given and used to improve the lower bound for c2. 相似文献
2.
Noga Alon 《Journal of Combinatorial Theory, Series A》1985,40(1):82-89
Let X1, …, Xn be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let Aij and Bij be subsets of Xi that satisfy |Aij| ? ri and |Bij| ? si for 1 ? i ? n, 1 ? j ? h, for 1 ? j ? h, for 1 ? j < l ? h. We prove that . This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra). 相似文献
3.
Moshe Roitman 《Advances in Mathematics》1981,41(3):301-311
For a finite group G and a set I ? {1, 2,…, n} let ,where We prove, among other results, that the positive integers for 1 ? j ? r, Ij1 ∩ Ij2 ∩ Ij3 ∩ Ij4 = Ø for any 1 ? j1 <j2 <j3 <j4 ? r, determine G up to isomorphism. We also show that under certain assumptions finite groups are determined up to isomorphism by the number of their subgroups. 相似文献
4.
The existence, uniqueness, and construction of unitary n × n matrix valued functions in Wiener-like algebras on the circle with prescribed matrix Fourier coefficients for j ? 0 are studied. In particular, if , then such an ? exists with if and only if ∥Γ0∥ ? 1, where Γv, denotes the infinite block Hankel matrix (γj + k + v), j, k = 0, 1,…, acting in the sequence space ln2. One of the main results is that the nonnegative factorization indices of every such ? are uniquely determined by the given data in terms of the dimensions of the kernels of , whereas the negative factorization indices are arbitrary. It is also shown that there is a unique such ? if and only if the data forces all the factorization indices to be nonnegative and simple conditions for that and a formula for ? in terms of certain Schmidt pairs of Γ0 are given. The results depend upon a fine analysis of the structure of the kernels of and of the one step extension problem of Adamjan, Arov, and Krein (Funct. Anal. Appl.2 (1968), 1–18). Isometric interpolants for the nonsquare case are also considered. 相似文献
5.
Allen J. Schwenk 《Discrete Mathematics》1977,18(1):71-78
Let denote the polynomial obtained from the cycle index of the symmetric group Z(Sn) by replacing each variable si by f(x1). Let f(x) have a Taylor series with radius of convergence ? of the form f(x)=xk + ak+1xk+1 + ak+2xk+2+? with every a1?0. Finally, let 0<x<1 and let x??. We prove that This limit is used to estimate the probability (for n and p both large) that a point chosen at random from a random p-point tree has degree n + 1. These limiting probabilities are independent of p and decrease geometrically in n, contrasting with the labeled limiting probabilities of .In order to prove the main theorem, an appealing generalization of the principle of inclusion and exclusion is presented. 相似文献
6.
It is shown that if satisfies , where σk(A) denotes the sum of all kth order subpermanent of A, then Per[λJn+(1?λ)A] is strictly decreasing in the interval 0<λ<1. 相似文献
7.
David S Jerison 《Journal of Functional Analysis》1981,43(1):97-142
For (x,y,t)∈n × n × , denote and . When α = n ? 2q, a represents the action of the Kohn Laplacian □b on q-forms on the Heisenberg group. For ?n < α < n, we construct a parametrix for the Dirichlet problem in smooth domains D near non-characteristic points of ?D. A point w of ?D is non-characteristic if one of X1,…, Xn, Y1,…, Yn is transverse to ?D at w. This yields sharp local estimates in the Dirichlet problem in the appropriate non-isotropic Lipschitz classes. The main new tool is a “convolution calculus” of pseudo-differential operators that can be applied to the relevant layer potentials, for which the usual asymptotic composition formula is false. Characteristic points are treated in Part II. 相似文献
8.
S.K. Bajpai Joseph Tanne Donald Whittier 《Journal of Mathematical Analysis and Applications》1974,48(3):736-742
Let f(z), an analytic function with radius of convergence R (0 < R < ∞) be represented by the gap series ∑k = 0∞ckzλk. Set and define the growth constants ?, λ, T, t by , and if 0 < ? < ∞, . Then, assuming 0 < t < T < ∞, we obtain a decomposition theorem for f(z). 相似文献
9.
Let n1+n2+?+nm=n where the ni's are integers (possibly negative or greater than n). Let p=(k1,…,km), where k1+k2+?+km=k, be a partition of the nonnegative integer k into m nonnegative integers and let P denote the set of all such partitions. For m?2, we prove the combinatorial identity which implies the surprising result that the left side of the above equation depends on n but not on the ni's. 相似文献
10.
11.
Results on partition of energy and on energy decay are derived for solutions of the Cauchy problem . Here the Aj's are constant, k × k Hermitian matrices, x = (x1,…, xn), t represents time, and u = u(t, x) is a k-vector. It is shown that the energy of Mu approaches a limit , where M is an arbitrary matrix; that there exists a sufficiently large subspace of data ?, which is invariant under the solution group U0(t) and such that depending on ? and that the local energy of nonstatic solutions decays as . More refined results on energy decay are also given and the existence of wave operators is established, considering a perturbed equation at infinity. 相似文献
12.
The non-linear autonomous of differential equations which plays an important role in chemical kinetics and other fields of physics (turbulence and plasma physics) is investigated using the Carleman linearization procedure. 相似文献
13.
R.J Cook 《Journal of Number Theory》1983,17(1):80-92
Let k be an odd positive integer. Davenport and Lewis have shown that the equations with integer coefficients, have a nontrivial solution in integers x1,…, xN provided that Here it is shown that for any ? > 0 and k > k0(?) the equations have a nontrivial solution provided that 相似文献
14.
A p-vertex graph is called pancyclic if it contains cycles of every length l, 3 ≤ l ≤ p. In this paper we prove the following conjecture of Bondy and Chvátal: If a graph G has vertex degree sequence d1 ≤ d2 ≤ … ≤ dν, and if implies dν?k ≥ p ? k, then G is pancyclic or bipartite. 相似文献
15.
Let k and r be fixed integers such that 1 < r < k. Any positive integer n of the form n = akb, where b is r-free, is called a (k, r)-integer. In this paper we prove that if Qk,r(x) denotes the number of (k, r)-integers ≤ x, then , where , B being a positive constant depending on r and the O-estimate is uniform in k. On the assumption of the Riemann hypothesis, we improve the above order estimate of Δk,r(x) and prove that , according as or , where ω(x) = exp [B log x(log log x)?1]. 相似文献
16.
we prove that if R is a nonscalar Toeplitz matrix Ri, j=r?i?j? which commutes with a tridiagonal matrix with simple spectrum, then , k=4, 5,…, with Uk the Chebychev polynomial of the second kind, where p is determined from . 相似文献
17.
In two party elections with popular vote ratio , a theoretical model suggests replacing the so-called MacMahon cube law approximation , for the ratio of candidates elected, by the ratio of the two half sums in the binomial expansion of (p+q)2k+1 for some k. This ratio is nearly when k = 6. The success probability for the power law is shown to so closely approximate , if we choose , that for . Computationally, we avoid large binomial coefficients in computing for k>22 by expressing as the sum , whose terms decrease by the factors . Setting K = 4k+3, we compute ak for the large k using a continued fraction derived from the ratio of π to the finite Wallis product approximation. 相似文献
18.
Let be a Dirichlet form in , where Ω is an open subset of n, n ? 2, and m a Radon measure on Ω; for each integer k with 1 ? k < n, let k be a Dirichlet form on some k-dimensional submanifold of Ω. The paper is devoted to the study of the closability of the forms E with domain and defined by: ki where 1 ? kp < ? < n, and where , gki denote restrictions of ?, g in to . Conditions are given for E to be closable if, for each i = 1,…, p, one has ki = n ? i. Other conditions are given for E to be nonclosable if, for some i, ki < n ? i. 相似文献
19.
Let Ω be a finite set with k elements and for each integer let (n-tuple) and and aj ≠ aj+1 for some 1 ≦ j ≦ n ? 1}. Let {Ym} be a sequence of independent and identically distributed random variables such that P(Y1 = a) = k?1 for all a in Ω. In this paper, we obtain some very surprising and interesting results about the first occurrence of elements in and in Ω?n with respect to the stochastic process {Ym}. The results here provide us with a better and deeper understanding of the fair coin-tossing (k-sided) process. 相似文献
20.
B.G. Pittel 《Stochastic Processes and their Applications》1980,10(1):33-48
Let X1,X2,… be i.i.d. random variables with a continuous distribution function. Let R0=0, Rk=min{j>Rk?1, such that Xj>Xj+1}, k?1. We prove that all finite-dimensional distributions of a process , converge to those of the standard Brownian motion. 相似文献