容斥原理在汉密尔顿问题中的应用

容斥原理是组合数学中的经典的计数方法,该原理的基本思想是:先不排除重叠的情况,把包含于某种性质的所有对象的数目先计算出来,然后再把重复计算的数目排斥出去.针对汉密尔顿问题,[15]利用邻接矩阵给出了判断一个图是否为汉密尔顿图的充要条件.本文将结合容斥原理给出汉密尔顿路径存在性的一个判别条件,并给出汉密尔顿路径的计算公式.     

广义容斥原理及其应用

容斥原理(包含和排斥原理的简称,又称取舍原理或出入原理)是组合计数中的一个非常基本而重要的工具。Schwenk和魏万迪推广了容斥原理。本文给出了容斥原理的一种新的拓广,得到了广义容斥原理。     

Signed words and permutations, IV: Fixed and pixed points

The flag-major index “fmaj” and the classical length function “ℓ” are used to construct two q-analogs of the generating polynomial for the hyperoctahedral group B _n by number of positive and negative fixed points (resp., pixed points). Specializations of those q-analogs are also derived dealing with signed derangements and desarrangements, as well as several classical results that were previously proved for the symmetric group. To Volker Strehl, a dedication à la Goethe, on the occasion of his sixtieth birthday.     

A p, q-Analogue of the Generalized Derangement Numbers

In this paper, we study the numbers D _n,k which are defined as the number of permutations σ of the symmetric group S _n such that σ has no cycles of length j for j ≤ k. In the case k = 1, D _n,1 is simply the number of derangements of an n-element set. As such, we shall call the numbers D _n,k generalized derangement numbers. Garsia and Remmel [4] defined some natural q-analogues of D _n,1, denoted by D _n,1(q), which give rise to natural q-analogues of the two classical recursions of the number of derangements. The method of Garsia and Remmel can be easily extended to give natural p, q-analogues D _n,1(p, q) which satisfy natural p, q-analogues of the two classical recursions for the number of derangements. In [4], Garsia and Remmel also suggested an approach to define q-analogues of the numbers D _n,k . In this paper, we show that their ideas can be extended to give a p, q-analogue of the generalized derangements numbers. Again there are two classical recursions for eneralized derangement numbers. However, the p, q-analogues of the two classical recursions are not as straightforward when k ≥ 2. Partially supported by NSF grant DMS 0400507.     

Dynamic programming meets the principle of inclusion and exclusion

We show that several combinatorial existence problems can be attacked by solving associated enumeration problems using a combination of dynamic programming and the principle of inclusion and exclusion. In comparison with the usual dynamic programming algorithms, the new methods have somewhat greater execution time but require far less storage.     

Exceedingly deranging!

This paper studies the excedance distribution on derangements and gives its generating function. It also studies the excedance distribution on the set of even derangements and the set of odd derangements and proves combinatorially an unexpected relation between the number of odd and the number of even derangements having a given number of excedances.     

Inclusion–exclusion principle for belief functions

The inclusion–exclusion principle is a well-known property in probability theory, and is instrumental in some computational problems such as the evaluation of system reliability or the calculation of the probability of a Boolean formula in diagnosis. However, in the setting of uncertainty theories more general than probability theory, this principle no longer holds in general. It is therefore useful to know for which families of events it continues to hold. This paper investigates this question in the setting of belief functions. After exhibiting original sufficient and necessary conditions for the principle to hold, we illustrate its use on the uncertainty analysis of Boolean and non-Boolean systems in reliability.     

Competitive exclusion and coexistence in a Leslie–Gower competition model with Allee effects

The classical competitive exclusion principle states that two populations competing for a limited resource cannot coexist, one of the populations will drive the other to extinction. We prove in this work that when one population is subject to Allee effects, then for certain parameter regimes both competing populations may either coexist or one population may drive the other to extinction depending on initial conditions.     

Viscous stress relaxation,characteristics, and numerical boundary conditions

The anomalous infinite propagation speeds in the classical parabolic flow equations are removed by the inclusion of a small amount of fluid elasticity or viscous stress relaxation. The inclusion of such effects results in a hyperbolic system of equations with a complete set of characteristic equations. The directional characteristic equations are used to give insights into the appropriate boundary molecules to be used in finite difference numerical schemes. © 1994 John Wiley & Sons, Inc.     

Stable iterative Lagrange principle in convex programming as a tool for solving unstable problems

A convex programming problem in a Hilbert space with an operator equality constraint and a finite number of functional inequality constraints is considered. All constraints involve parameters. The close relation of the instability of this problem and, hence, the instability of the classical Lagrange principle for it to its regularity properties and the subdifferentiability of the value function in the problem is discussed. An iterative nondifferential Lagrange principle with a stopping rule is proved for the indicated problem. The principle is stable with respect to errors in the initial data and covers the normal, regular, and abnormal cases of the problem and the case where the classical Lagrange principle does not hold. The possibility of using the stable sequential Lagrange principle for directly solving unstable optimization problems is discussed. The capabilities of this principle are illustrated by numerically solving the classical ill-posed problem of finding the normal solution of a Fredholm integral equation of the first kind.