首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f1,f2,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size fi. It is proved that there exist constants c=c(n) and k0=k0(n) such that fk+1=fk+fkc for all k>k0, and limn→∞ c(n)/(nlogn)=1.  相似文献   

2.
We consider embeddings of the complete t-ary trees of depth k (denotation Tk,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(Tk,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(Tk,3)2k+1 up to limk→∞dim(Tk,3)/k5/3 and show limt→∞dim(T3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(Tk,t) for arbitrary k and t.  相似文献   

3.
We obtain an approximation for the logarithmic averages of I{k1/2a(k) S(k) k1/2b(k)}, where a(k) → 0, b(k) → 0 (k → ∞) and S(k) is partial sum of independent, identically distributed random variables.  相似文献   

4.
We partially characterize the rational numbers x and integers n 0 for which the sum ∑k=0 knxk assumes integers. We prove that if ∑k=0 knxk is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where va(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑k=02nk! S(2n, k) , for all integers n 1.  相似文献   


5.
In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate
1 p < ∞, for every polynomial P of degree at most n + rn1/3, where W2 is a Freud weight such as exp(−¦x¦), > 1, λjn are the Christoffel numbers, xjn are the zeros of the orthonormal polynomials for the weight W2, and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξnn1/3, where ξn → ∞ as n → ∞. Previous estimates could sum only over those xjn with ¦xjn¦ σx1n, some fixed 0 < σ < 1.  相似文献   

6.
We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t*)r, where t*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τr,n lets approximately t*n arrivals go by and then stops ‘almost immediately’, in the sense that τr,n/nt* in probability as n→∞, r→∞  相似文献   

7.
Let πi :EiM, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections si :MEi. Suppose that U is an open neighborhood of s1(M) in E1 and F :UE2 a smooth embedding so that π2Fs1 :MM is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E1 and the induced bundle f*E2 are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E1 and E2 of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E1 and f*E2 are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.  相似文献   

8.
It is shown that if W is a linear subspace of real n × n matrices, such that rank (A) = k for all 0 ≠ AW, then dim Wn. If dim W = n.5≤ n is prime, and 2 is primitive modulo n then k =1.  相似文献   

9.
If 1≤kn, then Cor(n,k) denotes the set of all n×n real correlation matrices of rank not exceeding k. Grone and Pierce have shown that if A∈Cor (n, n-1), then per(A)≥n/(n-1). We show that if A∈Cor(n,2), then , and that this inequality is the best possible.  相似文献   

10.
《Discrete Mathematics》1999,200(1-3):61-77
We say (n, e) → (m, f), an (m, f) subgraph is forced, if every n-vertex graph of size e has an m-vertex spanned subgraph with f edges. For example, as Turán proved, (n,e)→(k,(k2)) for e> tk − 1(n) and (n,e) (k2)), otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.  相似文献   

11.
Ergodic Hamiltonian systems with an arbitrary number of degrees of freedom n are considered. A relation is derived connecting the distribution function of the system characteristics with the entropy. It is shown that as n → ∞ it reduces to Einstein's formula /1/. A variational principle for the distribution function, which reduces to the maximum-uncertainty principle as n → ∞ is derived. The principle of maximum entropy for Hamiltonian systems is formulated.  相似文献   

12.
We prove using a direct construction that one can choose n − 2 subsets of an n-element set with different cardinality such that none of them contains any other. As a generalization, we prove that if for any j we can have at most k subsets containing exactly j elements (k> 1), then for n 5 we can choose at most k(n − 3) subsets from an n-element set such that they form a Sperner system. Moreover, we prove that this can be achieved if n is large enough, and give a construction for n 8k − 4.  相似文献   

13.
A k-connected graph G is said to be critically k-connected if Gv is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(nk)+p2/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.  相似文献   

14.
Suppose {k, −∞ < k < ∞} is an independent, not necessarily identically distributed sequence of random variables, and {cj}j=0, {dj}j=0 are sequences of real numbers such that Σjc2j < ∞, Σjd2j < ∞. Then, under appropriate moment conditions on {k, −∞ < k < ∞}, yk Σj=0cjk-j, zk Σj=0djk-j exist almost surely and in 4 and the question of Gaussian approximation to S[t]Σ[t]k=1 (yk zkE{yk zk}) becomes of interest. Prior to this work several related central limit theorems and a weak invariance principle were proven under stationary assumptions. In this note, we demonstrate that an almost sure invariance principle for S[t], with error bound sharp enough to imply a weak invariance principle, a functional law of the iterated logarithm, and even upper and lower class results, also exists. Moreover, we remove virtually all constraints on k for “time” k ≤ 0, weaken the stationarity assumptions on {k, −∞ < k < ∞}, and improve the summability conditions on {cj}j=0, {dj}j=0 as compared to the existing weak invariance principle. Applications relevant to this work include normal approximation and almost sure fluctuation results in sample covariances (let dj = cj-m for jm and otherwise 0), quadratic forms, Whittle's and Hosoya's estimates, adaptive filtering and stochastic approximation.  相似文献   

15.
We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the nk − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering kn/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number kn/2 decide whether a query rectangle contains k points or less.  相似文献   

16.
We construct the polynomial pm,n* of degree m which interpolates a given real-valued function f L2[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L2-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L2-error pm,n*f → 0 as m → ∞ if f C[a, b].  相似文献   

17.
Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers   总被引:6,自引:0,他引:6  
The Ramsey number r(H,Kn) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K2,m,Kn)(m−1+o(1))(n/log n)2 and r(C2m,Kn)c(n/log n)m/(m−1) for m fixed and n→∞. Also r(K2,n,Kn)=Θ(n3/log2 n) and .  相似文献   

18.
It is shown that if all subpermaneats of order k of an n × n doubly stochastic matrix are equal for some kn - 2, then all the entries of the matrix must be equal to 1/n.  相似文献   

19.
《Discrete Mathematics》1999,200(1-3):137-147
We form squares from the product of integers in a short interval [n, n + tn], where we include n in the product. If p is prime, p|n, and (2p) > n, we prove that p is the minimum tn. If no such prime exists, we prove tn √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then tn = 3p> 3 √n/2. For n(n + u) a square > n2, we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g2(n) be minimal such that a square can be formed as the product of distinct integers from [n, g2(n)] so that no pair of consecutive integers is omitted. We prove that g2(n) 3n − 3, and list or conjecture the values of g2(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.  相似文献   

20.
The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σi = 1ni(xi + λgi(xi)), under simple constraints Σi = 1n xi = M, lixiui and xi: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and li and ui are given lower and upper bounds on xi. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(GMlog2 n + n log n + n log(M/n)), where G = Σi = 1n ui − Σi = 1n li and an evaluation of ƒi(·) or gi(·) is assumed to be done in constant time.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号