A canonical decomposition of the probability measure of sets of isotropic random points in Rn

The probability measure of X = (x₀,…, x_r), where x₀,…, x_r are independent isotropic random points in $\text{R}$ⁿ (1 ≤ r ≤ n ? 1) with absolutely continuous distributions is, for a certain class of distributions of X, expressed as a product measure involving as factors the joint probability measure of (ω, ?), the probability measure of p, and the probability measure of $\text{Y}{}^1\text{= (y}{}_0{}^1\text{,…, y}{}_{\mathrm{r}}{}^1\text{)}$. Here ω is the r-subspace parallel to the r-flat η determined by X, ? is a unit vector in ω^⊥ with ‘initial’ point at the origin [ω^⊥ is the (n ? r)-subspace orthocomplementary to ω], p is the norm of the vector z from the origin to the orthogonal projection of the origin on η, and $\text{y}{}_{\mathrm{i}}{}^1\text{=}\text{(x}{}_{\mathrm{i}}\text{? z)}\text{α(p}{}^2\text{)}$, where α is a scale factor determined by p. The probability measure for ω is the unique probability measure on the Grassmann manifold of r-subspaces in $\text{R}$ⁿ invariant under the group of rotations in $\text{R}$ⁿ, while the conditional probability measure of ? given ω is uniform on the boundary of the unit (n ? r)-ball in ω^⊥ with centre at the origin. The decomposition allows the evaluation of the moments, for a suitable class of distributions of X, of the r-volume of the simplicial convex hull of {x₀,…, x_r} for 1 ≤ r ≤ n.     

Enumeration of pairs of permutations

Let π = (a₁, a₂, …, a_n), ? = (b₁, b₂, …, b_n) be two permutations of $\text{Z}{}_{\mathrm{n}}\text{= {1, 2, …, n}}$. A rise of π is pair a_i, a_i+1 with a_i < a_i+1; a fall is a pair a_i, a_i+1 with a_i > a_i+1. Thus, for i = 1, 2, …, n ? 1, the two pairs a_i, a_i+1; b_i, b_i+1 are either both rises, both falls, the first a rise and the second a fall or the first a fall and the second a rise. These possibilities are denoted by RR, FF, RF, FR. The paper is concerned with the enumeration of pairs π, p with a given number of RR, FF, RF, FR. In particular if ω_n denotes the number of pairs with RR forbidden, it is proved that $\text{∑}{}^{\mathrm{\infty }}{}_0\text{ω}{}_{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}\text{=}\text{1}\text{?(z)}$, $\text{?(z) = ∑}{}^{\mathrm{\infty }}{}_0\text{(-1)}{}^{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}$. More precisely if ω(n, k) denotes the number of pairs π, p with exactly k occurences of RR(or FF, RF, FR) then $\text{1 + ∑}{}^{\mathrm{\infty }}{}_{\mathrm{n=1}}\text{z}{}^{\mathrm{n}}\text{n!n!}$$\text{∑}{}^{\mathrm{n?1}}{}_{\mathrm{k=0}}\text{ω(n, k)x}{}^{\mathrm{k}}\text{=}\text{(1 ? x)}\text{(?(z(1 ? x)) ? x)}$.     

Three problems on the lengths of increasing runs

Let U₁, U₂,… be a sequence of independent, uniform (0, 1) r.v.'s and let R₁, R₂,… be the lengths of increasing runs of {U_i}, i.e., X₁=R₁=inf{i:U_i+1<U_i},…, X_n=R₁+R₂+?+R_n=inf{i:i>X_n?1,U_i+1<U_i}. The first theorem states that the sequence $\text{(}\text{3}\text{2}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(X}{}_{\mathrm{n}}\text{?2n)}$ can be approximated by a Wiener process in strong sense.Let τ(n) be the largest integer for which R₁+R₂+?+R_τ(n)?n, $\text{R}{}^1{}_{\mathrm{n}}\text{=n?(R}{}_1\text{+R}{}_2\text{+?+R}{}_{\mathrm{\tau (n)}}\text{)}$ and $\text{M}{}_{\mathrm{n}}\text{=}\text{max}\text{{R}{}_1\text{,R}{}_2\text{,…,R}{}_{\mathrm{\tau (n)}}\text{,R}{}^1{}_{\mathrm{n}}\text{}}$. Here M_n is the length of the longest increasing block. A strong theorem is given to characterize the limit behaviour of M_n.The limit distribution of the lengths of increasing runs is our third problem.     

The probability that k positive integers are relatively r-prime

If r, k are positive integers, then $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ denotes the number of k-tuples of positive integers (x₁, x₂, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r = 1. An explicit formula for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ is derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}\text{n}{}^{\mathrm{k}}\text{=}\text{1}\text{ζ(rk)}$.If S = {p₁, p₂, …, p_a} is a finite set of primes, then 〈S〉 = {p₁^a₁p₂^a₂…p_s^a_s; p_i ∈ S and a_i ≥ 0 for all i} and $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ denotes the number of k-tuples (x₁, x₃, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r ∈ 〈S〉. Asymptotic formulas for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ are derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}\text{n}{}^{\mathrm{k}}\text{=}\text{(p}{}_1\text{… p}{}_{\mathrm{a}}\text{)}{}^{\mathrm{rk}}\text{ζ(rk)(p}{}_1{}^{\mathrm{rk}}\text{? 1) … (p}{}_{\mathrm{s}}{}^{\mathrm{rk}}\text{? 1)}$.     

Some divided difference inequalities for n-convex functions

Using results from the theory of B-splines, various inequalities involving the nth order divided differences of a function f with convex nth derivative are proved; notably, $\text{f}{}^{\mathrm{(n)}}\text{(z)}\text{n! ? [x}{}_0\text{,…, x}{}_{\mathrm{n}}\text{]f}\text{?}\text{∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{n}}\text{(f}{}^{\mathrm{(n)}}\text{(x}{}_{\mathrm{i}}\text{)}\text{(n + 1)!)}$, where z is the center of mass $\text{(}\text{1}\text{(n + 1))}\text{∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{n}}\text{x}{}_{\mathrm{i}}$.     

The KMS condition and spectral passivity in group duality

Let (A, G, α) be a C¹-dynamical system, where G is abelian, and let φ be an invariant state. Suppose that there is a neighbourhood Ω of the identity in $\text{G}\text{?}$ and a finite constant κ such that $\text{Π}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{φ(x}{}_{\mathrm{i}}{}^1\text{x}{}_{\mathrm{i}}\text{) ? κ}\text{Π}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{φ(x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}{}^1\text{)}$ whenever x_i lies in a spectral subspace $\text{R}{}^{\mathrm{\alpha }}\text{(Ω}{}_{\mathrm{i}}\text{)}$, where $\text{Ω}{}_1\text{+ … + Ω}{}_{\mathrm{n}}\text{? Ω}$. This condition of complete spectral passivity, together with self-adjointness of the left kernel of φ, ensures that φ satisfies the KMS condition for some one-parameter subgroup of G.     

Spectral theory of commuting self-adjoint partial differential operators

Let Ω denote a connected and open subset of $\text{R}$ⁿ. The existence of n commuting self-adjoint operators H₁,…, H_n on $\text{L}{}^2\text{(Ω)}$ such that each H_j is an extension of $\text{−}\text{i∂}\text{∂x}{}_{\mathrm{j}}$ (acting on $\text{C}{}_{\mathrm{c}}{}^{\mathrm{\infty }}\text{(Ω))}$ is shown to be equivalent to the existence of a measure μ on $\text{R}$ⁿ such that f → $\text{}\text{̂}$tf (the Fourier transform of f) is unitary from $\text{L}{}^2\text{(Ω)}$ onto Ω. It is shown that the support of μ can be chosen as a subgroup of $\text{R}$ⁿ iff H₁,…, H_n can be chosen such that the unitary groups generated by H₁,…, H_n act multiplicatively on $\text{L}{}^2\text{(Ω)}$. This happens iff Ω (after correction by a null set) forms a system of representatives for the quotient of $\text{R}$ⁿ by some subgroup, i.e., iff Ω is essentially a fundamental domain.     

Existence of stable equilibrium point for dynamical systems of Volterra type

This paper presents sufficient conditions for the existence of a nonnegative and stable equilibrium point of a dynamical system of Volterra type, (1) $\text{(}\text{d}\text{dt}\text{) x}{}_{\mathrm{i}}\text{(t) = ?x}{}_{\mathrm{i}}\text{(t)[f}{}_{\mathrm{i}}\text{(x}{}_1\text{(t),…, x}{}_{\mathrm{n}}\text{(t)) ? q}{}_{\mathrm{i}}\text{], i = 1,…, n}$, for every q = (q₁,…, q_n)^T?Rⁿ. Results of a nonlinear complementarity problem are applied to obtain the conditions. System (1) has a nonnegative and stable equilibrium point if (i) f(x) = (f₁(x),…,f_n(x))^T is a continuous and differentiable M-function and it satisfies a certain surjectivity property, or (ii), f(x) is continuous and strongly monotone on R₊₀ⁿ.     

“Integer-making” theorems

Let X = {x₁, x₂,…} be a finite set and associate to every x_i a real number α_i. Let f(n) [g (n)] be the least value such that given any family $\text{F}$ of subsets of X having maximum degree n [cardinality n], one can find integers α_i, i=1,2,… so that α_i ? α_i|<1 and

$\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{a}{}_{\mathrm{i}}\text{?}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{α}{}_{\mathrm{i}}\text{≤?(n)}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{a}{}_{\mathrm{i}}\text{?}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{α}{}_{\mathrm{i}}\text{≤}\text{g(n)}$

for all $\text{E ?}\text{F}$. We prove

$\text{f(n)≤n ? 1 and g(n)≤c(n}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$

.     

A method of feasible directions using function approximations,with applications to min max problems

This paper presents a demonstrably convergent method of feasible directions for solving the problem min{φ(ξ)| gⁱ(ξ)?0i=1,2,…,m}, which approximates, adaptively, both φ(x) and ▽φ(x). These approximations are necessitated by the fact that in certain problems, such as when $\text{φ(x) =}\text{max}\text{{f(x, y) ¦ y ? Ω}{}_{\mathrm{y}}\text{}}$, a precise evaluation of φ(x) and ▽φ(x) is extremely costly. The adaptive procedure progressively refines the precision of the approximations as an optimum is approached and as a result should be much more efficient than fixed precision algorithms.It is outlined how this new algorithm can be used for solving problems of the form $\text{min}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{x}}\text{max}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{y}}\text{f(x, y)}$ under the assumption that Ωm_ξ={x|gⁱ(x)?0, j=1,…,s} ∩$\text{R}$ⁿ, Ω_y={y|ζ_i(y)?0, i-1,…,t} ∩ $\text{R}$^m, with f, g^j, ζⁱ continuously differentiable, f(x, ·) concave, ζⁱ convex for $\text{i = 1,…, t,}\text{and}\text{Ω}{}_{\mathrm{x}}\text{, Ω}{}_{\mathrm{y}}$ compact.     

Inverse Hölder inequalities in one and several dimensions

We study certain functionals and obtain an inverse Hölder inequality for n functions f₁^a1,…,f_n^an (f_k concave, 1 dimension).We also prove a multidimensional inverse Hölder inequality for n functions f₁,…,f_n, where $\text{?}{}^2\text{f}{}_{\mathrm{k}}\text{?x}{}_{\mathrm{i}}{}^2\text{? 0, i = 1,…, d, k = 1,…, n}$.Finally we give an inverse Minkowski inequality for concave functions.     

Factorization of fredholm operators on analytic functions

Let Ω be a simply connected domain in the complex plane, and $\text{A(Ω}{}^{\mathrm{n}}\text{)}$, the space of functions which are defined and analytic on $\text{Ω}{}^{\mathrm{n}}$, if K is the operator on elements $\text{u(t, a}{}_1\text{, …, a}{}_{\mathrm{n}}\text{)}\text{of}\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of the kernels k_i(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by is the identity operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$, 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 $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of a kernel w(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by Wu = ∝_an^tw(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠW is the operator; ΠWu = ∝_{an ? 1}w(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠK is the operator; ΠKu = ∑_{i = 1}^{n ? 1} ∝_ai^tk_i(t, s, a₁, …, a_n) ds + ∝_{an ? 1}^tk_n(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. The operator M is of the form m(t, a₁, …, a_n)I, where $\text{m ? A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ and maps elements of $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ into itself by multiplication. The function m is uniquely derived from K in the following manner. The operator K defines an operator $\text{K}{}^1$ on functions u in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$, by . A determinant $\text{δ(I ? K}{}^1\text{)}$ of the operator $\text{I ? K}{}^1$ is defined as an element $\text{m}{}^1\text{(t, a}{}_1\text{, …, a}{}_{\mathrm{n\; +\; 1}}\text{)}$ of $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$. This is mapped into $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ by setting a_{n + 1} = t to give m(t, a₁, …, a_n). 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 k_i defining K are separable in the sense that k_i(t, s, a₁, …, a_n) = P_i(t, a₁, …, a_n) Q_i(s, a₁, …, a_n), where P_i is a 1 × p_i matrix and Q_i is a p_i × 1 matrix, each with elements in $\text{A(Ω}{}_{\mathrm{n\; +\; 1}}\text{)}$, 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.     

Strong law for the bootstrap

Let X₁, X₂, X₃, … be i.i.d. r.v. with E|X₁| < ∞, E X₁ = μ. Given a realization X = (X₁,X₂,…) and integers n and m, construct Y_n,i, i = 1, 2, …, m as i.i.d. r.v. with conditional distribution $\text{P}{}^1\text{(Y}{}_{\mathrm{n,i}}\text{= X}{}_{\mathrm{j}}\text{) =}\text{1}\text{n}$ for 1 ? j ? n. ($\text{P}{}^1$ denotes conditional distribution given X). Conditions relating the growth rate of m with n and the moments of X₁ are given to ensure the almost sure convergence of $\text{(}\text{1}\text{m}\text{)Σ}{}^{\mathrm{m}}{}_{\mathrm{i=1}}\text{Y}{}_{\mathrm{n,i}}$ toμ. This equation is of some relevance in the theory of Bootstrap as developed by Efron (1979) and Bickel and Freedman (1981).     

Commuting self-adjoint partial differential operators and a group theoretic problem

In Rⁿ let Ω denote a Nikodym region (= a connected open set on which every distribution of finite Dirichlet integral is itself in $\text{L}{}^2\text{(Ω))}$. The existence of n commuting self-adjoint operators $\text{H}{}_1\text{,…, H}{}_{\mathrm{n}}\text{in}\text{L}{}^2\text{(Ω)}$ such that each H_j is a restriction of $\text{?i β}\text{βx}{}_{\mathrm{j}}$ (acting in the distribution sense) is shown to be equivalent to the existence of a set Λ ?Rⁿ such that the restrictions to Ω of the functions exp i ∑ λ_jx_j form a total orthogonal family in $\text{L}{}^2\text{(Ω)}$. If it is required, in addition, that the unitary groups generated by H₁,…, H_n act multiplicatively on $\text{L}{}^2\text{(Ω)}$, then this is shown to correspond to the requirement that Λ can be chosen as a subgroup of the additive group Rⁿ. The measurable sets Ω ?Rⁿ (of finite Lebesgue measure) for which there exists a subgroup Λ ?Rⁿ as stated are precisely those measurable sets which (after a correction by a null set) form a system of representatives for the quotient of Rⁿ by some subgroup Γ (essentially the dual of Λ).     

Decomposability of symmetric multilinear functions

Let V denote a finite dimensional vector space over a field K of characteristic 0, let T_n(V) denote the vector space whose elements are the K-valued n-linear functions on V, and let S_n(V) denote the subspace of T_n(V) whose members are the fully symmetric members of T_n(V). If $\text{L}$_n denotes the symmetric group on {1,2,…,n} then we define the projection $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{: T}{}_{\mathrm{n}}\text{(V) → S}{}_{\mathrm{n}}\text{(V)}$ by the formula , where P_σ : T_n(V) → T_n(V) is defined so that P_σ(A)(y₁,y₂,…,y_n = A(y_σ(1),y_σ(2),…,y_σ(n)) for each A?T_n(V) and y_i?V, 1 ? i ? n. If $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, then x₁?x₂? … ?x_n denotes the member of T_n(V) such that $\text{(x}{}_1\text{?x}{}_2\text{· ? ? ?x}{}_{\mathrm{n}}\text{)(y}{}_1\text{,y}{}_2\text{,…,y}{}_{\mathrm{n}}\text{) = П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{x}{}_{\mathrm{i}}\text{(y}{}_{\mathrm{i}}\text{)}$ for each y₁ ,₂,…,y_n in V, and x₁·x₂… x_n denotes $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{(x}{}_1\text{?x}{}_2\text{? … ?x}{}_{\mathrm{n}}\text{)}$. If B? S_n(V) and there exists $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, such that B = x₁·x₂…x_n, then B is said to be decomposable. We present two sets of necessary and sufficient conditions for a member B of S_n(V) to be decomposable. One of these sets is valid for an arbitrary field of characteristic zero, while the other requires that K = R or C.     

The asymptotic eigenvalue-distribution for a certain class of random matrices

For an n × n Hermitean matrix A with eigenvalues λ₁, …, λ_n the eigenvalue-distribution is defined by $\text{G(x, A) :=}\text{1}\text{n}$ · number {λ_i: λ_i ? x} for all real x. Let A_n for n = 1, 2, … be an n × n matrix, whose entries a_ik are for i, k = 1, …, n independent complex random variables on a probability space (Ω, $\text{R}$, p) with the same distribution F_a. Suppose that all moments $\text{E}$ | a | ^k, k = 1, 2, … are finite, $\text{E}$a=0 and $\text{E}$ | a | ². Let

$\text{M(A)=}\text{∑}\text{σ=1}\text{s}\text{θ}{}_{\mathrm{\sigma }}\text{P}{}_{\mathrm{\sigma }}\text{(A,A}{}^1\text{)}$

with complex numbers θ_σ and finite products P_σ of factors A and $\text{A}{}^1$ (= Hermitean conjugate) be a function which assigns to each matrix A an Hermitean matrix M(A). The following limit theorem is proved: There exists a distribution function G₀(x) = G₁x) + G₂(x), where G₁ is a step function and G₂ is absolutely continuous, such that with probability $\text{1 G(x, M(}\text{A}{}_{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{))}$ converges to G₀(x) as n → ∞ for all continuity points x of G₀. The density g of G₂ vanishes outside a finite interval. There are only finitely many jumps of G₁. Both, G₁ and G₂, can explicitly be expressed by means of a certain algebraic function f, which is determined by equations, which can easily be derived from the special form of M(A). This result is analogous to Wigner's semicircle theorem for symmetric random matrices (E. P. Wigner, Random matrices in physics, SIAM Review9 (1967), 1–23). The examples $\text{A}{}_{\mathrm{r}}\text{A}{}^{\mathrm{1r}}$, $\text{A}{}^{\mathrm{r}}\text{+ A}{}^{\mathrm{1r}}$, $\text{A}{}^{\mathrm{r}}\text{A}{}^{\mathrm{1r}}\text{± A}{}^{\mathrm{1r}}\text{A}{}^{\mathrm{r}}$, r = 1, 2, …, are discussed in more detail. Some inequalities for random matrices are derived. It turns out that with probability 1 the sharpened form

$\text{lim sup}\text{n→∞}\text{∑}\text{i=1}{}^{\mathrm{n}}\text{|γ}{}_{\mathrm{i}}{}^{\mathrm{(n)}}\text{|}{}^2\text{?6A}{}_{\mathrm{n}}\text{6}{}^2\text{? 0.8228…}$

of Schur's inequality for the eigenvalues λ_i⁽ⁿ⁾ of A_n holds. Consequently random matrices do not tend to be normal matrices for large n.     

Hilbert space representations of general discrete time stochastic processes

We show that under mild conditions the joint densities Px₁,…,x_n) of the general discrete time stochastic process X_n on $\text{pH}$ can be computed via

$\text{Px}{}_1\text{,…,x}{}_{\mathrm{n}}\text{(x}{}_1\text{,…,x}{}_{\mathrm{n}}\text{) = 6?T(x}{}_1\text{)…T(x}{}_{\mathrm{n}}\text{)6}{}^2$

where ? is in a Hilbert space $\text{pH}$, and T (x), x ? $\text{pH}$ are linear operators on $\text{pH}$. We then show how the Central Limit Theorem can easily be derived from such representations.     

Ballots and rooks

The level code representation of the simplest ballot problem (weak lead lattice paths from (0, 0) to (n, n) is the set of sequences (b₁,…, b_n) defined by b₁ = 1, b_{i ?1} ≤ b_i ≤ i, 2 ≤ i ≤n. Each sequence is monotone non-decreasing, has a specification (c₁, c₂,…, c_n) with c_i the number of sequence elements equal to i (hence c₁ + c₂…+ c_n = n), and may be permuted in $\text{n!}\text{c}{}_1\text{!…c}{}_{\mathrm{n}}\text{!}$ ways. The set of permuted sequences, as noted in [4], is the set of parking functions, introduced by Konheim and Weiss in [1]. To count parking functions by number of fixed points, associate the rook polynomial for matching a deck of cards of specification (c₁,…,c_n), c_i cards marked i, with a deck of n distinct cards. The hit polynomial H_n(x) corresponding to the sum of such rook polynomials over all sequences (I am using the terminology of [2]) is the required enumerator and turns out to be simply

$\text{(n+1)}{}^2\text{H}{}_{\mathrm{n}}\text{(x)=(x+n)}{}^{\mathrm{n+1}}\text{?(x?1)}{}^{\mathrm{n+1}}$

.     

Segmental solutions of Boolean equations

Davio and Deschamps have shown that the solution set, K, of a consistent Boolean equation $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{)=0}$ over a finite Boolean algebra B may be expressed as the union of a collection of subsets of Bⁿ, each of the form {(x₁, …, x_n) | a_i≤x_i≤b_i, a_i?B, b_i?B, i = 1, …, n}. We refer to such subsets of Bⁿ as segments and to the collection as a segmental cover of K. We show that $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{) = 1}$ is consistent if and only if ? can be expressed by one of a class of sum-of-products expressions which we call segmental formulas. The object of this paper is to relate segmental covers of K to segmental formulas for ?.     

Explicit expressions for Bezoutians

The following commutator identity is proved:

$\text{[u(S}{}^1\text{), v(S)] = [v}{}_1\text{(S}{}^1\text{), u}{}_1\text{(S)]}$

. Here S is the n by n matrix of the truncated shift operator S = (Γ_i,i+1), i = 0, 1,…, n ? 1, and u, v are two polynomials of degree not exceeding n. The reciprocal polynomial f;₁ of a polynomial f; of degree ?n is defined by $\text{f}{}_1\text{(z) = z}{}^{\mathrm{n}}\text{f(}\text{1}\text{z}\text{)}$. The commutator identity is closely related to some properties of the Bezoutian matrix of a pair of polynomials; it is used to obtain the Bezoutian matrix in the form of a simple expression in terms of S and S¹. To demonstrate the advantage of this expression, we show how it can be used to obtain simple proofs of some interesting corollaries.