共查询到20条相似文献,搜索用时 15 毫秒
1.
We prove an asymptotic formula for the number of permutations for which the associated permutation polynomial has degree smaller than q−2. 相似文献
2.
Eric S. Egge 《Annals of Combinatorics》2010,14(1):85-101
We use the Robinson-Schensted-Knuth correspondence and Schützenberger’s evacuation of standard tableaux to enumerate permutations
and involutions which are invariant under the reverse-complement map and which have no decreasing subsequences of length k. These enumerations are in terms of numbers of permutations with no decreasing subsequences of length approximately
\frack2;{{\frac{k}{2}};} we use known results concerning these quantities to give explicit formulas when k ≤ 6. 相似文献
3.
Denote by f(n) the number of subgroups of the symmetric groupSym(n) of degree n, and by ftrans(n) the number of its transitivesubgroups. It was conjectured by Pyber [9] that almost all subgroupsof Sym(n) are not transitive, that is, ftrans(n)/f(n) tendsto 0 when n tends to infinity. It is still an open questionwhether or not this conjecture is true. The difficulty comesfrom the fact that, from many points of view, transitivity isnot a really strong restriction on permutation groups, and thereare too many transitive groups [9, Sections 3 and 4]. In thispaper we solve the problem in the particular case of permutationgroups of prime power degree, proving the following result.1991 Mathematics Subject Classification 20B05, 20D60. 相似文献
4.
5.
We settle some conjectures formulated by A. Claesson and T. Mansour concerning generalized pattern avoidance of permutations. In particular, we solve the problem of the enumeration of permutations avoiding three generalized patterns of type (1, 2) or (2, 1) by using ECO method and a graphical representation of permutations.Received July 15, 2004 相似文献
6.
Fishburn 排列与许多重要组合结构包括区间序存在双射. 在这篇论文中, 我们利用生成树的方法, 得到两类模式避免Fishburn排列的关于7元经典统计量的生成函数.我们考虑的类别是避免 (321,312) 和 (321,4123) 模式的 Fishburn 排列.我们关注的统计量包括升序数、降序数、逆序数、从右到左的极大值、从右到左的极小值、从左到右的极大值和从左到右的极小值。我们的结果推广了 Egge 的一个结论. 相似文献
7.
Pinaki Das 《Finite Fields and Their Applications》2002,8(4):478
We relate the number of permutation polynomials in Fq[x] of degree d≤q−2 to the solutions (x1,x2,…,xq) of a system of linear equations over Fq, with the added restriction that xi≠0 and xi≠xj whenever i≠j. Using this we find an expression for the number of permutation polynomials of degree p−2 in Fp[x] in terms of the permanent of a Vandermonde matrix whose entries are the primitive pth roots of unity. This leads to nontrivial bounds for the number of such permutation polynomials. We provide numerical examples to illustrate our method and indicate how our results can be generalised to polynomials of other degrees. 相似文献
8.
In (Deodhar, Geom. Dedicata, 36(1) (1990), 95–119), Deodhar proposes a combinatorial framework for determining the Kazhdan-Lusztig polynomials P
x
,
w
in the case where W is any Coxeter group. We explicitly describe the combinatorics in the case where
(the symmetric group on n letters) and the permutation w is 321-hexagon-avoiding. Our formula can be expressed in terms of a simple statistic on all subexpressions of any fixed reduced expression for w. As a consequence of our results on Kazhdan-Lusztig polynomials, we show that the Poincaré polynomial of the intersection cohomology of the Schubert variety corresponding to w is (1+q)
l(w)
if and only if w is 321-hexagon-avoiding. We also give a sufficient condition for the Schubert variety X
w
to have a small resolution. We conclude with a simple method for completely determining the singular locus of X
w
when w is 321-hexagon-avoiding. The results extend easily to those Weyl groups whose Coxeter graphs have no branch points (B
C
n
, F
4, G
2). 相似文献
9.
《Finite Fields and Their Applications》2001,7(2):287-292
We give an exact characterization of permutation polynomials modulo n=2w, w≥2: a polynomial P(x)=a0+a1x +···+adxd with integral coefficients is a permutation polynomial modulo n if and only if a1 is odd, (a2+a4+a6+···) is even, and (a3+a5+a7+···) is even. We also characterize polynomials defining latin squares modulo n=2w, but prove that polynomial multipermutations (that is, a pair of polynomials defining a pair of orthogonal latin squares) modulo n=2wdo not exist. 相似文献
10.
11.
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. 相似文献
12.
分组峦码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位.199j年,美国Tcledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换.止形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质(良好的扩散性和完令平衡性),因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常订必要.本文根据文章[1]的方法讨论了F2^n(n=4,5)上的4次正形置换多项式的形式与计数,至于n〉5的情形我们将在以后的篇章中继续讨论. 相似文献
13.
分组密码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位.1995年,美国Teledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换.正形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质(良好的扩散性和完全平衡性),因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常有必要.本文根据文章[1]的方法讨论了F2n(n=4,5)上的4次正形置换多项式的形式与计数,至于n5的情形我们将在以后的篇章中继续讨论. 相似文献
14.
Richard M. Stafford 《Finite Fields and Their Applications》1998,4(4):450-452
LetFbe a finite field. We apply a result of Thierry Berger (1996,Designs Codes Cryptography,7, 215–221) to determine the structure of all groups of permutations onFgenerated by the permutations induced by the linear polynomials and any power map which induces a permutation onF. This generalizes a result of Leonard Carlitz (1953,Proc. Amer. Math. Soc.,4, 538). 相似文献
15.
For a commutative finite ring with identity R, the two definitions of "permutaIion polynomial in several indeterminates over R" coincide if and only if R is a direct sum of finite fields. 相似文献
16.
Masato Kobayashi 《Order》2011,28(1):131-137
In theory of Coxeter groups, bigrassmannian elements are well known as elements which have precisely one left descent and
precisely one right descent. In this article, we prove formulas on enumeration of bigrassmannian permutations weakly below
a permutation in Bruhat order in the symmetric groups. For the proof, we use equivalent characterizations of bigrassmannian
permutations by Lascoux-Schützenberger and Reading. 相似文献
17.
由于有限域上的置换多项式在密码、编码和组合设计有着重要的应用,置换多项式是人们比较感兴趣的一个研究课题.利用线性化多项式,得到了一类新的形如(x~(p~k)-x+δ)~s+L(x)的置换多项式. 相似文献
18.
《Finite Fields and Their Applications》2002,8(2):233-255
The linear group trinomial provides a mnemonic device for the recently discovered permutation polynomials of Müller, Cohen, and Matthews, whereas the symplectic group equation generalizes them, thereby giving rise to strong genus zero coverings for characteristic two. 相似文献
19.
Transitive Permutation Groups of Prime-Squared Degree 总被引:2,自引:0,他引:2
20.
《数学的实践与认识》2015,(23)
有限域F_(2~n)上,g(x)=b_2~dx~2~d+b_2~(d-1)x~2~(d-1)+…+b_2x~2+b_1x+b_0是2~d次仿射多项式,利用同余类知识和有限域上乘积多项式的次数分布规律,研究了F_(2~n)上形如xg(x)的2~d+1次正形置换多项式的存在性. 相似文献