Fix-Mahonian Calculus, II: Further statistics

Using classical transformations on the symmetric group and two transformations constructed in Fix-Mahonian Calculus I, we show that several multivariable statistics are equidistributed either with the triplet (fix, des, maj), or the pair (fix, maj), where “fix,” “des” and “maj” denote the number of fixed points, the number of descents and the major index, respectively.     

Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

Restricted 132-Alternating Permutations and Chebyshev Polynomials

A permutation is said to be alternating if it starts with rise and then descents and rises come in turn. In this paper we study the generating function for the number of alternating permutations on n letters that avoid or contain exactly once 132 and also avoid or contain exactly once an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.AMS Subject Classification: 05A05, 05A15, 30B70, 42C05.     

Coloured Permutations Containing and Avoiding Certain Patterns

Let be the set of all coloured permutations on the symbols 1, 2, . . . , n with colours 1, 2, . . . , r, which is the analogous of the symmetric group when r = 1, and the hyperoctahedral group when r = 2. Let be a subset of d colours; we define to be the set of all coloured permutations . We prove that the number of -avoiding coloured permutations in . We then prove that for any , the number of coloured permutations in which avoid all patterns in except for and contain exactly once equals . Finally, for any , this number equals . These results generalize recent results due to Mansour, Mansour and West, and Simion.AMS Subject Classification: 05A05, 05A15.     

Circle action with prescribed number of fixed points

Given any two positive integers k and n, this paper is concerned with the existence of a circle action on a closed, smooth orientable n-dimensional manifold with precisely k isolated fixed points. We first show that this existence problem can be reduced to that of an n-dimensional manifold with exactly three fixed points. Then by using a rigidity result, we determine possible weights on these three fixed points when n = 4.     

有关重复排列的一类计数问题

利用生成函数解决了从n个元素的集合中任意重复选取r个元素且这r个元素中含有不同元素的个数一定时，所构成的不同r-序列的方法数．     

A New Class of Wilf-Equivalent Permutations

For about 10 years, the classification up to Wilf equivalence of permutation patterns was thought completed up to length 6. In this paper, we establish a new class of Wilf-equivalent permutation patterns, namely, (n – 1, n – 2, n, ) (n – 2, n, n – 1, ) for any S _{n –3}. In particular, at level n = 6, this result includes the only missing equivalence (546213) (465213), and for n = 7 it completes the classification of permutation patterns by settling all remaining cases in S ₇.     

Permutations with Low Discrepancy Consecutive k-sums

Consider the permutation π=(π₁,…, π_n) of 1,2,…, n as being placed on a circle with indices taken modulo n. For given kn there are n sums of k consecutive entries. We say the maximum difference of any consecutive k-sum from the average k-sum is the discrepancy of the permutation. We seek a permutation of minimum discrepancy. We find that in general the discrepancy is small, never more than k+6, independent of n. For g= gcd(n,k)>1, we show that the discrepancy is . For g=1 it is more complicated. Our constructions show that the discrepancy never exceeds k/2 by more than 9 for large n, while it is at least k/2 for infinitely many n.We also give an analysis for the easier case of linear permutations, where we view the permutation as written on a line. The analogous discrepancy is at most 2 for all n,k.     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

Primitive symmetric designs with prime power number of points

In this paper we either prove the non‐existence or give explicit construction of primitive symmetric (v, k, λ) designs with v=p^m<2500, p prime and m>1. The method of design construction is based on an automorphism group action; non‐existence results additionally include the theory of difference sets, multiplier theorems in particular. The research involves programming and wide‐range computations. We make use of software package GAP and the library of primitive groups which it contains. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 141–154, 2010     

On Sums of Products of Bernoulli Variables and Random Permutations

Let {X _k } _k1 be independent Bernoulli random variables with parameters p _k . We study the distribution of the number or runs of length 2: that is . Let S=lim _n S _n . For the particular case p _k =1/(k+B), B being given, we show that the distribution of S is a Beta mixture of Poisson distributions. When B=0 this is a Poisson(1) distribution. For the particular case p _k =p for all k we obtain the generating function of S _n and the limiting distribution of S _n for .     

A four-group of automorphisms with a small number of fixed points

Translated from Algebra i Logika, Vol. 30, No. 6, pp. 735–746, November–December, 1991.     

有限域上低差分置换的计算与构造

低差分置换是对称密码算法的重要组件,最近屈等先后提出了优先函数、优先布尔函数的概念,并用之构造4-差分置换.构造了一些具有较少项数的优先布尔函数,将交换法中的布尔函数推广为F_(2~n)到F_4的映射,进一步研究了广义的交换构造,构造了三类新的4-差分置换,并计算了它们的非线性度.     

Tree maps having chain movable fixed points

In this paper we discuss some basic properties of chain reachable sets and chain equivalent sets of continuous maps. It is proved that if f:T→T is a tree map which has a chain movable fixed point v, and the chain equivalent set CE(v,f) is not contained in the set P(f) of periodic points of f, then there exists a positive integer p not greater than the number of points in the set End([CE(v,f)])−Pv(f) such that fp is turbulent, and the topological entropy . This result generalizes the corresponding results given in Block and Coven (1986) [2], Guo et al. (2003) [6], Sun and Liu (2003) [10], Ye (2000) [11], Zhang and Zeng (2004) [12]. In addition, in this paper we also consider metric spaces which may not be trees but have open subsets U such that the closures are trees. Maps of such metric spaces which have chain movable fixed points are discussed.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

The number of fixed points of the majority rule

Formulae are derived for the number of cyclic binary strings of length n in which no single 1 occurs between two zeros and no single 0 occurs between two ones, and for the number of cyclic binary strings without substrings of the form 000 and 111. This problem is motivated by a problem of genetic information processing.