共查询到20条相似文献,搜索用时 31 毫秒
1.
Ervin Győri 《Combinatorica》1981,1(4):377-380
The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR
n
belongs to then-dimensional unit cubeQ
n, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log2
x−(x−1) log2 (x−1)=1. 相似文献
2.
Melvin Hausner 《Combinatorica》1985,5(3):215-225
Ifμ is a positive measure, andA
2, ...,A
n
are measurable sets, the sequencesS
0, ...,S
n
andP
[0], ...,P
[n] are related by the inclusion-exclusion equalities. Inequalities among theS
i
are based on the obviousP
[k]≧0. Letting
=the average average measure of the intersection ofk of the setsA
i
, it is shown that (−1)
k
Δ
k
M
i
≧0 fori+k≦n. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS
0=1,
whenS
1≧N−1, and
for 1≦k<N≦n andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN,
for all sequencesM
0, ...,M
n
of sufficiently large length if and only if
for 0<t<1. 相似文献
3.
For a subsetS, let the descent statistic (S) be the number of permutations that have descent setS. We study inequalities between the descent statistics of subsets. Each subset (and its complement) is encoded by a list containing the lengths of the runs. We define two preorders that compare different lists based on the descent statistic. Using these preorders, we obtain a complete order on lists of the form (k
i
,P,k
n–i
, whereP is a palindrome, whose first entry is larger thank. We prove a conjecture due to Gessel, which determines the list that maximizes the descent statistic, among lists of a given size and given length. We also have a generalization of the boustrophedon transform of Millar, Sloane and Young. 相似文献
4.
G. F. Clements 《Order》1995,12(3):233-237
IfA is a family ofk-element subsets of a finite setM having elements of several different types (i.e., amultiset) and A is the set of all (k–1)-element subsets ofM obtainable by removing a single element ofM from a single member ofA, then, according to the well known normalized matching condition, the density ofA among thek-element subsets ofM never exceeds the density of A among the (k–1)-element subsets ofM. We show that this useful fact can be regarded as yet another corollary of the generalized Macaulay theorem. 相似文献
5.
József Beck 《Combinatorica》1981,1(2):103-116
Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy.
By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK
N
k
, and the first player wins if he has selected allk-tuples of ann-set. LetR
k*(n) be the least integerN so that the first player has a winning strategy.
We prove (W* (n))1/n → 2,R
2*(n)<(2+ε)
n
andR
k
*
n<2
nk
/
k!
fork ≧3. 相似文献
6.
A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold. 相似文献
7.
Eric S. Egge 《Annals of Combinatorics》2007,11(3-4):405-434
Pattern-avoiding involutions, which have received much enumerative attention, are pattern-avoiding permutations which are
invariant under the natural action of a certain subgroup of D
8, the symmetry group of a square. Three other nontrivial subgroups of D
8 also have invariant permutations under this action. For each of these subgroups, we enumerate the set of permutations which
are invariant under the action of the subgroup and which also avoid a given set of forbidden patterns. The sets of forbidden
patterns we consider include all subsets of S
3. For each subgroup we also give a bijection between the invariant permutations and certain symmetric signed permutations.
Received September 14, 2006 相似文献
8.
Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n}
n
; interchange cards 1 andt
1, then interchange cards 2 andt
2, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS
n
, is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539. 相似文献
9.
The q-Catalan numbers studied by Carlitz and Riordan are polynomials in q with nonnegative coefficients. They evaluate, at q = 1, to the Catalan numbers: 1, 1, 2, 5, 14,…, a log-convex sequence. We use a combinatorial interpretation of these polynomials
to prove a q-log-convexity result. The sequence of q-Catalan numbers is not q-log-convex in the narrow sense used by other authors, so our work suggests a more flexible definition of q-log convex be adopted.
Received January 2, 2007 相似文献
10.
The symmetric chain decomposition of the lattice of divisors,D
N, is applied to prove results about the strict unimodality of the Whitney numbers ofD
N, about minimum interval covers for the union of consecutive rank-sets ofD
N, and about the distribution of sums of vectors in which each vector can be included several times (an extension of the famous Littlewood-Offord problem)Research supported in part by NSA/MSP GrantMDA904-92H3053. 相似文献
11.
It is shown that the maximum number of patterns that can occur in a permutation of length n is asymptotically 2
n
. This significantly improves a previous result of Coleman.
Received September 28, 2006 相似文献
12.
An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B
n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B
n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076. 相似文献
13.
G. F. Clements 《Periodica Mathematica Hungarica》1992,25(2):119-126
IfX is a family ofl-subsets of a multiset, then there is a set of distinct representatives of the members ofX among the (l-k)-subsets of the members ofX provided the cardinality ofX does not exceed a certain bound. An algorithm for calculating this bound is given. 相似文献
14.
The old workhorse called linearity of expectation, by which it is often very easy to compute the expectation (alias first moment) of interesting combinatorial quantities, can also be used to compute higher moments, as well as correlations, but then things get very soon too complicated for mere humans. The computer, used as a symbol-cruncher, can go much further (alas, only by a few orders of magnitude). In this article, a methodology for using Computer Algebra Systems to automatically derive higher moments of interesting combinatorial random variables is described, and applied to Pattern Statistics of permutations. This would be hopefully followed by sequels applied to other combinatorial objects like graph-colorings, Boolean functions, and Random Walks. In addition to the intrinsic interest that the actual results might have, it is also hoped that this work will serve as as an illustrative example for conducting reliable mathematical experiments that lead to completely rigorous results, by an Overlapping Stages approach. 相似文献
15.
For a fixed setI of positive integers we consider the set of paths (p
o,...,p
k
) of arbitrary length satisfyingp
l
–p
l–1I forl=2,...,k andp
0=1,p
k
=n. Equipping it with the uniform distribution, the random path lengthT
n
is studied. Asymptotic expansions of the moments ofT
n
are derived and its asymptotic normality is proved. The step lengthsp
l
–p
l–1 are seen to follow asymptotically a restricted geometrical distribution. Analogous results are given for the free boundary case in which the values ofp
0 andp
k
are not specified. In the special caseI={m+1,m+2,...} (for some fixed m) we derive the exact distribution of a random m-gap subset of {1,...,n} and exhibit some connections to the theory of representations of natural numbers. A simple mechanism for generating a randomm-gap subset is also presented. 相似文献
16.
Jerrold R. Griggs 《Order》1984,1(1):21-28
Let P be the poset k
1 × ... × k
n
, which is a product of chains, where n1 and k
1 ... k
n
2. Let
. P is known to have the Sperner property, which means that its maximum ranks are maximum antichains. Here we prove that its maximum ranks are its only maximum antichains if and only if either n=1 or M1. This is a generalization of a classical result, Sperner's Theorem, which is the case k
1= ... =k
n
=2. We also determine the number and location of the maximum ranks of P.Research supported in part by the National Science Foundation 10/25/83. 相似文献
17.
Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z
k
-coloring f: P Z
k
there exists either a chain or an antichain A, |A|=n and
aA
f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)2–c(k) p(n, k) (n+k–2)2+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing). 相似文献
18.
Henrik Eriksson Kimmo Eriksson Svante Linusson Johan Wästlund 《Annals of Combinatorics》2007,11(3-4):459-470
We study the length L
k
of the shortest permutation containing all patterns of length k. We establish the bounds e
−2
k
2 < L
k
≤ (2/3 + o(1))k
2. We also prove that as k → ∞, there are permutations of length (1/4 + o(1))k
2 containing almost all patterns of length k.
Received January 2, 2007 相似文献
19.
《Quaestiones Mathematicae》2013,36(6):733-748
AbstractLet a word be a sequence of n i.i.d. integer random variables. The perimeter P of the word is the number of edges of the word, seen as a polyomino. In this paper, we present a probabilistic approach to the computation of the moments of P. This is applied to uniform and geometric random variables. We also show that, asymptotically, the distribution of P is Gaussian and, seen as a stochastic process, the perimeter converges in distribution to a Brownian motion. 相似文献
20.
Amy N. Myers 《Annals of Combinatorics》2007,11(3-4):507-517
It is well-known that the number of permutations of n letters that avoid a pattern τ of 3 letters is independent of τ. In this note we provide bijective proof that the same result
holds for permutations of a multiset.
Received August 16, 2006 相似文献