Permutations and successions

Let π = (π(1), π(2),…, π(n)) be a permutation on {1, 2, …, n}. A succession (respectively, ¹-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, $\text{R}{}^1\text{(n, k)}$) be the number of permutations with k successions (respectively, ¹-successions). In this note we determine R(n, k) and $\text{R}{}^1\text{(n, k)}$. In addition, these notions are generalized to the case of circular permutations, where analogous results are developed.     

Periodic-type functionals and their extensions

Let Ω denote a simply connected domain in the complex plane and let $\text{K[Ω]}$ be the collection of all entire functions of exponential type whose Laplace transforms are analytic on Ω′, the complement of Ω with respect to the sphere. Define a sequence of functionals $\text{{L}{}_{\mathrm{n}}\text{}}\text{on}\text{K[Ω]}$ by $\text{L}{}_{\mathrm{n}}\text{(f) =}\text{1}\text{2πi}\text{∝}{}_{\mathrm{\Gamma }}\text{g}{}_{\mathrm{n}}\text{(ζ) F(ζ) dζ}$, where F denotes the Laplace transform of f, Γ ? Ω is a simple closed contour chosen so that F is analytic outside and on Ω, and g_n is analytic on Ω. The specific functionals considered by this paper are patterned after the Lidstone functions, L_2n(f) = f⁽²ⁿ⁾(0) and L_{2n + 1}(f) = f⁽²ⁿ⁾(1), in that their sequence of generating functions {g_n} are “periodic.” Set g_{pn + k}(ζ) = h_k(ζ) ζ^pn, where p is a positive integer and each h_k (k = 0, 1,…, p ? 1) is analytic on Ω. We find necessary and sufficient conditions for $\text{f ∈ k[Ω]}\text{with}\text{L}{}_{\mathrm{n}}\text{(f) = 0 (n = 0, 1,…)}$. DeMar previously was able to find necessary conditions [7]. Next, we generalize {L_n} in several ways and find corresponding necessary and sufficient conditions.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

On solutions of “equations in symmetric groups”

Let x?S_n, the symmetric group on n symbols. Let θ? Aut(S_n) and let the automorphim order of x with respect to θ be defined by

$\text{γθ(x)=}\text{min}\text{{k:x xθ xθ}{}^2\text{? xθ}{}^{\mathrm{k?1}}\text{=1}}$

where xθ is the image of x under θ. Let α_g? Aut(S_n) denote conjugation by the element g?S_n. Let where s and k are positive integers and $\text{a}\text{b}$ denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?S_n let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let g_s denote the product of all cycles in g whose lengths do not divide s. Then g_s moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then $\text{b(g; s, 1:n)=∑}{}_{\mathrm{<mtext>i</mtext><mtext>s</mtext>}}\text{b(g; s, 1:n?1)(}{}^{\mathrm{t}}{}_{\mathrm{i?1}}\text{(i?1)!}$ (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z⁺ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in g_s^s of any given length is smaller than the smallest prime dividing s iff b(g_s; s, 1 : c) = 1. If g = (12 … p^m)^t and $\text{sk}\text{p}{}^{\mathrm{m}}$ then $\text{b(g;s,k:p}{}^{\mathrm{m}}\text{) {}{}^0{}_{\mathrm{\pm 1}}\text{(}\text{mod}\text{p)}$.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

On the g-circulant solutions to the matrix equation Am = λJ, II

Let g and n be positive integers and let $\text{k =}\text{n(g, n)}\text{(g}{}^{\mathrm{m}}\text{, n)}$. If θ(x) is a multiple of Σ_{i = 0}^{k ? 1}xⁱ, then the g-circulant whose Hall polynomial is equal to θ(x) satisfies the matrix equation in the title. If the g-circulant whose Hall polynomial is equal to Σ_{i = 0}^{h ? 1}xⁱ satisfies the matrix equation in the title, then h is a multiple of k.     

On the separation power and the completion of partial latin squares

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 P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. 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 $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, 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.     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) 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 = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

A combinatorial interpretation for two transformations of series that commute with compositional inversion

For a formal power series $\text{g(t) =}\text{1}\text{[1 + ∑}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{h}{}_{\mathrm{n}}\text{t}{}^{\mathrm{n}}\text{]}$ with nonnegative integer coefficients, the compositional inverse $\text{f}\text{(t) = t · f(t)}$ of $\text{g}\text{(t) = t · g(t)}$ is shown to be the generating function for the colored planted plane trees in which each vertex of degree i + 1 is colored one of h_i colors. Since the compositional inverse of the Euler transformation of f(t) is the star transformation [[g(t)]^?1 ? 1]^?1 of g(t), [2], it follows that the Euler transformation of f(t) is the generating function for the colored planted plane trees in which each internal vertex of degree i + 1 is colored one of h_i colors for i > 1, and h₁ ? 1 colors for i = 1.     

A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (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.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

Packing a convex domain with similar convex domains

Given a convex domain C and a positive integer k, inscribe k nonoverlapping convex domains into C, all of them similar to C. Denote by f(k) the maximal sum of their circumferences. In this paper it is shown, that for C square, parallelogram or triangle (1) the first increase of f(k) after k = l² occurs not later than at k = l² + 2, (2) constructions can be given, where the following lower bounds are attained for f(k) = f(l² + j):

$\text{(}\text{1}\text{c}\text{) ? l +}\text{(j ? 1)}\text{2l}\text{j}\text{odd}\text{, l? 2}$

$\text{? l +}\text{j}\text{2}\text{(l + 1) j}\text{even}\text{, l?2}$

where c denotes the circumference of C.     

On the parity of the frequency of cycle lengths of shift register sequences

Let A(n, k) be the number of k-long cycles generated by binary shift registers of span n ? 2. It is shown that A(n, k) is odd if and only if $\text{k =}\text{1}\text{3}\text{[2}{}^{\mathrm{n+1}}\text{± 3 + (?1)}{}^{\mathrm{n}}\text{]}$. A recursive construction of complete self-dual, self-reversing cycles of these lengths is presented.     

An asymptotic evaluation of the cycle index of a symmetric group

Let $\text{Z(S}{}_{\mathrm{n}}\text{;?(x))}$ denote the polynomial obtained from the cycle index of the symmetric group Z(S_n) by replacing each variable s_i by f(x¹). Let f(x) have a Taylor series with radius of convergence ? of the form f(x)=x^k + a_k+1x^k+1 + a_k+2x^k+2+? with every a₁?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 $\text{1}\text{n!e}$.In order to prove the main theorem, an appealing generalization of the principle of inclusion and exclusion is presented.     

On the number of line separations of a finite set in the plane

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S?S′. We let f_k(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of f_k(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on f_k(n) is established. Both are nontrivial and improve bounds known before. In particular, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = Ω(n}\text{log}\text{k)}$ is shown by exhibiting special point-sets which realize that many k-sets. In addition, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = O(nk}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is proved by the study of a combinatorial problem which is of interest in its own right.     

Construction of a recurrence relation for modified moments

In this paper we are constructing a recurrence relation of the form

$\text{∑}\text{i=0}\text{r}\text{ω}{}_{\mathrm{i}}\text{(k)m}{}_{\mathrm{k+i}}{}^{\mathrm{\{\lambda \}}}\text{[f] = ω(k)}$

for integrals (called modified moments)

$\text{m}{}_{\mathrm{k}}{}^{\mathrm{\{\lambda \}}}\text{[f]df=}\text{∫}\text{?1}\text{1}\text{f(x)C}{}_{\mathrm{k}}{}^{\mathrm{(\lambda )}}\text{(x)dx (k = 0,1,…)}$

in which C_k^(λ) is the k-th Gegenbauer polynomial of order $\text{λ(λ > ?}\text{1}\text{2}\text{)}$, and f is a function satisfying the differential equation

$\text{∑}\text{i=0}\text{n}\text{P}{}_{\mathrm{i}}\text{(x)f}{}^{\mathrm{(i)}}\text{(x) = p(x) (?1?x?1)}$

of order n, where p₀, p₁, …, p_n ? 0 are polynomials, and m_k^〈λ〉[p] is known for every k. We give three methods of construction of such a recurrence relation. The first of them (called Method I) is optimum in a certain sense.     

Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.