共查询到20条相似文献,搜索用时 15 毫秒
1.
G.F Clements 《Journal of Combinatorial Theory, Series A》1984,37(1):91-97
Let kn ? kn?1 ? … ? k1 be positive integers and let () denote the coefficient of xi in . For given integers l, m, where 1 ? l ? kn + kn?1 + … + k1 and , it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which . Moreover, any m l-subsets of a multiset with ki elements of type i, i = 1, 2,…, n, will contain at least different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k1 = 1, the numbers () are binomial coefficients and the result is the Kruskal-Katona theorem. 相似文献
2.
Let 1?k1?k2?…?kn be integers and let S denote the set of all vectors x = (x1, …, xn with integral coordinates satisfying 0?xi?ki, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of ki elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities xi?yi, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k1 + k2 + …kn. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k1-x1, k2-x2, …, kn -xn). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and does not exceed the number of vectors in with first coordinate different from k1, then . 相似文献
3.
4.
R.-D Reiss 《Journal of multivariate analysis》1981,11(3):386-399
Let n denote the sample size, and let ri ∈ {1,…,n} fulfill the conditions ri ? ri?1 ≥ 5 for i = 1,…,k. It is proved that the joint normalized distribution of the order statistics Zri:n, i = 1,…,k, is independent of the underlying probability measure up to a remainder term of order . A counterexample shows that, as far as central order statistics are concerned, this remainder term is not of the order if ri ? ri?1 = 1 for i = 2,…,k. 相似文献
5.
Recently (see De Vylder & Goovaerts (1984), this issue) so called credibility matrices have been introduced and studied in the framework of general properties of matrices, such as non-negativity, total positivity etc. In the present note we characterize a class of credibility matrices generated by the normed sequence of functions (pl, pl,…, pn) on K = [0, b] where , i=0, …, n, θ ? K, and where ?, g, h are nonnegative (eventually depending on n, n may be finite or infinite). For simplicity we suppose h to be monotonic and continuous. 相似文献
6.
John R Bloom 《Journal of Number Theory》1979,11(2):239-256
Let k ? k1 ? … ? K be a Zi-extension. The relations of and is studied, where is a cyclic l-extension. If is another Zi-extension of k, it is shown that for i ? 0, under minimal additional hypotheses. Finally if has a unique totally ramified prime, and XK is cyclic, it is shown that MK can contain at most one Zi-extension with non-zero μ invariant. 相似文献
7.
The following results are proved: Let A = (aij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f1,…,fn) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f1,…,fn) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1. 相似文献
8.
Let Ω be a simply connected domain in the complex plane, and , the space of functions which are defined and analytic on , if K is the operator on elements defined in terms of the kernels ki(t, s, a1, …, an) in by is the identity operator on , then the operator I ? K may be factored in the form (I ? K)(M ? W) = (I ? ΠK)(M ? ΠW). Here, W is an operator on defined in terms of a kernel w(t, s, a1, …, an) in by Wu = ∝antw(t, s, a1, …, an) u(s, a1, …, an) ds. ΠW is the operator; ΠWu = ∝an ? 1w(t, s, a1, …, an) u(s, a1, …, an) ds. ΠK is the operator; ΠKu = ∑i = 1n ? 1 ∝aitki(t, s, a1, …, an) ds + ∝an ? 1tkn(t, s, a1, …, an) u(s, a1, …, an) ds. The operator M is of the form m(t, a1, …, an)I, where and maps elements of into itself by multiplication. The function m is uniquely derived from K in the following manner. The operator K defines an operator on functions u in , by . A determinant of the operator is defined as an element of . This is mapped into by setting an + 1 = t to give m(t, a1, …, an). The operator I ? ΠK may be factored in similar fashion, giving rise to a chain factorization of I ? K. In some cases all the matrix kernels ki defining K are separable in the sense that ki(t, s, a1, …, an) = Pi(t, a1, …, an) Qi(s, a1, …, an), where Pi is a 1 × pi matrix and Qi is a pi × 1 matrix, each with elements in , explicit formulas are given for the kernels of the factors W. The various results are stated in a form allowing immediate extension to the vector-matrix case. 相似文献
9.
Albert L Wells 《Journal of Combinatorial Theory, Series A》1979,27(3):342-355
Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P1,…, Pm such that A = P1 + … + Pm and each of the k 1's lies in a different Pi. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if . We obtain the bound , so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11. 相似文献
10.
Béla Bollobás 《Journal of Combinatorial Theory, Series A》1973,15(3):363-366
It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if = {;A1,…, Al}; consists of k-subsets of a set with n > 2k elements such that Ai ∩ Aj ≠ ? for all i, j then l ? (k?1n?1). Schönheim proved that if A1, …, Al are subsets of a set S with n elements such that Ai ? Aj, Ai ∩ Aj ≠ ø and Ai ∪ Aj ≠ S for all i ≠ j then . In this note we prove a common strengthening of these results. 相似文献
11.
John Konvalina 《Journal of Combinatorial Theory, Series A》1981,31(2):101-107
Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if (where ). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then . 相似文献
12.
Daniel J. Madden 《Journal of Number Theory》1978,10(3):303-323
If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions Kn over k(x) such that [K : k(x)] = pn using the concept of Witt vectors. This is accomplished in the following way; if [β1, β2,…, βn] is a Witt vector over k(x) = K0, then the Witt equation generates a tower of extensions through where . In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in Kn. This alternate generation has the form Ki = Ki?1(yi); yip ? yi = Bi, where, as a divisor in Ki?1, Bi has the form . In this form q is prime to Πpjλj and each λj is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field Kn over an algebraically closed field of constants. 相似文献
13.
Jorge L.C Sanz Thomas S Huang 《Journal of Mathematical Analysis and Applications》1984,104(1):302-308
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(z1…,zn), zi ? , i=1, …, n, is uniquely determined from the magnitude of f(x1…,xn): | f(x1…,xn)|, xi ? , i=1,…, n, except for (1) linear shifts: i(α1z1+…+αn2n+β), β, αi?, i=1,…, n; and (2) conjugation: . 相似文献
14.
L.E. Trotter 《Discrete Mathematics》1975,12(4):373-388
We examine a family of graphs called webs. For integers n ? 2 and , the web W(n, k) has vertices Vn = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?Vn (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement. 相似文献
15.
For a sequence A = {Ak} of finite subsets of N we introduce: , , where A(m) is the number of subsets Ak ? {1, 2, …, m}.The collection of all subsets of {1, …, n} together with the operation constitutes a finite semi-group N∪ (semi-group N∩) (group ). For N∪, N∩ we prove analogues of the Erdös-Landau theorem: δ(A+B) ? δ(A)(1+(2λ)?1(1?δ(A>))), where B is a base of N of the average order λ. We prove for analogues of Schnirelmann's theorem (that δ(A) + δ(B) > 1 implies δ(A + B) = 1) and the inequalities λ ? 2h, where h is the order of the base.We introduce the concept of divisibility of subsets: a|b if b is a continuation of a. We prove an analog of the Davenport-Erdös theorem: if d(A) > 0, then there exists an infinite sequence {Akr}, where Akr | Akr+1 for r = 1, 2, …. In Section 6 we consider for analogues of Rohrbach inequality: , where g(n) = min k over the subsets {a1 < … < ak} ? {0, 1, 2, …, n}, such that every m? {0, 1, 2, …, n} can be expressed as m = ai + aj.Pour une série A = {Ak} de sous-ensembles finis de N on introduit les densités: , où A(m) est le nombre d'ensembles Ak ? {1, 2, …, m}. L'ensemble de toutes les parties de {1, 2, …, n} devient, pour les opérations , un semi-groupe fini N∪, N∩ ou un groupe N1 respectivement. Pour N∪, N∩ on démontre l'analogue du théorème de Erdös-Landau: δ(A + B) ? δ(A)(1 + (2λ)?1(1?δ(A))), où B est une base de N d'ordre moyen λ. On démontre pour l'analogue du théorème de Schnirelmann (si δ(A) + δ(B) > 1, alors δ(A + B) = 1) et les inégalités λ ? 2h, où h est l'ordre de base. On introduit le rapport de divisibilité des enembles: a|b, si b est une continuation de a. On démontre l'analogue du théorème de Davenport-Erdös: si d(A) > 0, alors il existe une sous-série infinie {Akr}, où Akr|Akr+1, pour r = 1, 2, … . Dans le Paragraphe 6 on envisage pour N∪, les analogues de l'inégalité de Rohrbach: , où g(n) = min k pour les ensembles {a1 < … < ak} ? {0, 1, 2, …, n} tels que pour tout m? {0, 1, 2, …, n} on a m = ai + aj. 相似文献
16.
Laurie B. Hopkins William T. Trotter Douglas B. West 《Discrete Applied Mathematics》1984,8(2):163-187
The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line . Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is . Matthews showed that the interval number of the complete multipartite graph K(n1,n2,…,np) was the same as the interval number of K(n1,n2) when n1 = n2 = ? = np. Trotter and Hopkins showed that i(K(n1,n2,…,np)) ≤ 1 + i(K(n1,n2)) whenever p ≥ 2 and n1≥n2≥ ? ≥np. West showed that for each n ≥ 3, there exists a constant cn so that if p ≥ cn,n1 = n2?n ?1, and n2 = n3 = ? np = n, then i(K(n1,n2,…,np) = 1 + i(K(n1, n2)). In view of these results, it is natural to consider the problem of determining those pairs (n1,n2) with n1 ≥ n2 so that i(K(n2,…,np)) = i(K(n1,n2)) whenever p ≥ 2 and n2 ≥ n3 ≥ ? ≥ np. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n2 ? n ? 1, n) for n ≥ 3 and (7,5). 相似文献
17.
Stephen M Tanny 《Journal of Combinatorial Theory, Series A》1976,21(2):196-202
Let π = (π(1), π(2),…, π(n)) be a permutation on {1, 2, …, n}. A succession (respectively, 1-succession) in π is any pair π(i), π(i + 1), where π(i + 1) = π(i) + 1 (respectively, π(i + 1) ≡ π(i) + 1 (mod n)), i = 1, 2, …, n ? 1. Let R(n, k) (respectively, ) be the number of permutations with k successions (respectively, 1-successions). In this note we determine R(n, k) and . In addition, these notions are generalized to the case of circular permutations, where analogous results are developed. 相似文献
18.
Michio Ozeki 《Journal of Number Theory》1977,9(1):112-120
Let F1(x, y),…, F2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of Fi(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field ((?q)1/2). 相似文献
19.
The following estimate of the pth derivative of a probability density function is examined: , where hk is the kth Hermite function and Σi = 1nhk(p)(Xi) is calculated from a sequence X1,…, Xn of independent random variables having the common unknown density. If the density has r derivatives the integrated square error converges to zero in the mean and almost completely as rapidly as O(n?α) and O(n?α log n), respectively, where . Rates for the uniform convergence both in the mean square and almost complete are also given. For any finite interval they are O(n?β) and , respectively, where . 相似文献
20.