Search results for "permutation"
showing 10 items of 132 documents
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
Lehmer code transforms and Mahonian statistics on permutations
2012
Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections…
A Classification of all Symmetric Block Designs of Order Nine with an Automorphism of Order Six
2006
We complete the classification of all symmetric designs of order nine admitting an automorphism of order six. As a matter of fact, the classification for the parameters (35,17,8), (56,11,2), and (91,10,1) had already been done, and in this paper we present the results for the parameters (36,15,6), (40,13,4), and (45,12,3). We also provide information about the order and the structure of the full automorphism groups of the constructed designs. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 301–312, 2006
A matrix of combinatorial numbers related to the symmetric groups
1979
For permutation groups G of finite degree we define numbers t"B(G)=|G|^-^[email protected]?"R"@?"[email protected]?"1(1a"1(g))^b^"^i, where B=(b"1,...,b"1) is a tuple of non-negative integers and a"1(g) denotes the number of i cycles in the element g. We show that t"B(G) is the number of orbits of G, acting on a set @D"B(G) of tuples of matrices. In the case G=S"n we get a natural interpretation for combinatorial numbers connected with the Stiring numbers of the second kind.
Symmetric units and group identities
1998
In this paper we study rings R with an involution whose symmetric units satisfy a group identity. An important example is given by FG, the group algebra of a group G over a field F; in fact FG has a natural involution induced by setting g?g −1 for all group elements g∈G. In case of group algebras if F is infinite, charF≠ 2 and G is a torsion group we give a characterization by proving the following: the symmetric units satisfy a group identity if and only if either the group of units satisfies a group identity (and a characterization is known in this case) or char F=p >0 and 1) FG satisfies a polynomial identity, 2) the p-elements of G form a (normal) subgroup P of G and G/P is a Hamiltonia…
Sensitivity Versus Certificate Complexity of Boolean Functions
2016
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $…
Classical sequences revisited with permutations avoiding dotted pattern
2011
International audience; Inspired by the definition of the barred pattern-avoiding permutation, we introduce the new concept of dotted pattern for permutations. We investigate permutations classes avoiding dotted patterns of length at most 3, possibly along with other classical patterns. We deduce some enumerating results which allow us to exhibit new families of permutations counted by the classical sequences: 2^n, Catalan, Motzkin, Pell, Fibonacci, Fine, Riordan, Padovan, Eulerian.
McKay natural correspondences on characters
2014
Let [math] be a finite group, let [math] be an odd prime, and let [math] . If [math] , then there is a canonical correspondence between the irreducible complex characters of [math] of degree not divisible by [math] belonging to the principal block of [math] and the linear characters of [math] . As a consequence, we give a characterization of finite groups that possess a self-normalizing Sylow [math] -subgroup or a [math] -decomposable Sylow normalizer.
Generating restricted classes of involutions, Bell and Stirling permutations
2010
AbstractWe present a recursive generating algorithm for unrestricted permutations which is based on both the decomposition of a permutation as a product of transpositions and that as a union of disjoint cycles. It generates permutations at each recursive step and slight modifications of it produce generating algorithms for Bell permutations and involutions. Further refinements yield algorithms for these classes of permutations subject to additional restrictions: a given number of cycles or/and fixed points. We obtain, as particular cases, generating algorithms for permutations counted by the Stirling numbers of the first and second kind, even permutations, fixed-point-free involutions and d…
Equivalence classes of permutations modulo descents and left-to-right maxima
2014
Abstract In a recent paper [2], the authors provide enumerating results for equivalence classes of permutations modulo excedances. In this paper we investigate two other equivalence relations based on descents and left-to-right maxima. Enumerating results are presented for permutations, involutions, derangements, cycles and permutations avoiding one pattern of length three.