The cycle structure of two rows in a random Latin square

Let L be chosen uniformly at random from among the latin squares of order n ≥ 4 and let r,s be arbitrary distinct rows of L. We study the distribution of σ_r,s, the permutation of the symbols of L which maps r to s. We show that for any constant c > 0, the following events hold with probability 1 ‐ o(1) as n → ∞: (i) σ_r,s has more than (log n)^1?c cycles, (ii) σ_r,s has fewer than 9 cycles, (iii) L has fewer than n^5/2 intercalates (latin subsquares of order 2). We also show that the probability that σ_r,s is an even permutation lies in an interval and the probability that it has a single cycle lies in [2n^‐2,2n^‐2/3]. Indeed, we show that almost all derangements have similar probability (within a factor of n^3/2) of occurring as σ_r,s as they do if chosen uniformly at random from among all derangements of {1,2,…,n}. We conjecture that σ_r,s shares the asymptotic distribution of a random derangement. Finally, we give computational data on the cycle structure of latin squares of orders n ≤ 11. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

组合学中一类排列问题的历史研究--从错位排列到限位排列

阐述了历史上错位排问题最早出现的两种不同形式及其发展历程．论述了由解决此问题而引出的数学中的重要方法与原理——递推方法和容斥原理．介绍了数学家们研究由错位排问题延伸出的经典数学名题“夫妻入座问题”的成果．     

应用Mathematica计算组合数学问题

讨论组合数学中的带有条件限制的排列和组合问题的计算机算法,特别对典型的错排问题、有禁位排列问题和重集的组合问题进行了研究.在对照传统的理论解法的基础上,再运用数学软件Mathematica4.0在计算机上进行编程计算.     

Semigroups, Rings, and Markov Chains

We analyze random walks on a class of semigroups called left-regular bands. These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are generalized derangement numbers, which may be of independent interest.     

错排指数族的一些性质

针对错排设计了一个新的指数族,结合已有的结论得到有关错排指数族的性质,同时用错排指数族讨论了有关Stirling数与错排数的某些组合恒等式.最后通过限制牌的花色得出有关错排数的一些新的恒等式.     

Riordan paths and derangements

Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and -avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schröder numbers.     

关于数“e”的一个注记

从概率的观点对于数e的意义给出了一个新的解释,证明了当n→∞时,n元集合的一个变换是重排变换的概率的极限是-e 1,n元集合的一个变换恰有m个不动点的概率的极限是1也有完全相同的结论.     

循环均匀拉丁方

给出了循环均匀拉丁方的新定义，简记为ＵＣＬ（ｎ），并给出了ｎ≤１０的循环均匀拉丁方。     

二重错排与拉丁矩的计数

错排问题是组合数学中禁位排列的重要内容.基于3行拉丁矩计数问题的考虑,提出了条件更强的错排问题,即所谓的二重错排问题,并给出二重错排的相关计数公式及其在3行拉丁矩计数问题中的应用.同时给出ménage问题的2种推广形式.