Search

The Z statistic of Zeilberger and Bressoud is computed by summing the major index of the 2-letter subwords. We generalize this idea to other splittable Mahonian statistics. We call splittable Mahonian statistics which produce other splittable Mahonian statistics in this fashion Z-Mahonian. We characterize Z-Mahonian statistics and include several examples.

A generalized inversion statistic is introduced on k-tuples of semistandard tableaux. It is shown that the cospin of a semistandard k-ribbon tableau is equal to the generalized inversion number of its k-quotient. This leads to a branching formula for the q-analogue of Littlewood–Richardson coefficients defined by Lascoux, Leclerc, and Thibon. This branching formula generalizes a recurrence of Garsia and Procesi involving Kostka–Foulkes polynomials.

A new Schensted bijection is given from colored permutations to pairs of standard k-ribbon tableaux, such that twice the total color of the colored permutation, is equal to the sum of the spins of the pair of tableaux. A highly nontrivial extension of this bijection is also given, from colored words to a pair of k-ribbon tableaux, one semistandard and the other standard.

We present basic results and open problems related to the study of sets L(P) of linear extensions of posets (P, ≼). In our study, these linear extensions are regarded as permutations σ with the alternating character (-1)inv(σ). On the combinatorial side (Section 2), we present a number of open problems related to the fundamental study of sign-balanced posets whose Hasse diagrams are specified by Ferrers diagrams of partitions. On the multilinear-algebraic side (Section 3), we propose the general study of operators associated with P L(P), and the alternating character. We derive an antisymmetric decomposition of such operators as shuffles of anti-symmetric operators associated with symmetric groups. In general, we show that the set L(P)=G is a group if and only if P is an ordinal sum of antichains and G is a direct product of symmetric groups. As a consequence, the antisymmetric decomposition becomes a tensor product if and only if L(P) is a group.

We prove that the probability p2(n) that a random permutation of length n has a square root is monotonically nonincreasing in n. More generally, we prove that the probability pr(n) that a random permutation of length n has an rth root, r prime, is monotonically nonincreasing in n. We also show for all r≥2 that pr(n)0 as n∞. While doing this, we combinatorially prove that pr(n)=pr(n+1) for r prime and for all n not congruent to −1 mod r, and we construct several bijections for sets of permutations defined by modular class restrictions on the cycle lengths. We also include a simple probabilistic proof that, for r≥2, pr(n)0 as n∞. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 157–167, 2000

We describe a general machine for constructing statistics on words with a certain recursive structure. The classical Mahonian statistics, major index and inversion number, are examples, as are more modern Mahonian statistics, including those of Zeilberger and Bressoud, Denert, Han, Rawlings and Kadell. We give simple recursive procedures for calculating these statistics, as well as statistic-preserving bijections among them. We also describe other non-Mahonian distributions with similar recursive structures.

Four statistics on set partitions were introduced by Wachs and White. These statistics had q -Stirling numbers as their distribution generating function. The distribution of these statistics on non-crossing statistics was investigated by Simion. We introduce classes of statistics which interpolate between pairs of these four statistics. We give sufficient conditions for these classes to be q -Stirling distributed. We describe the restriction of these classes to non-crossing statistics. We also describe an interpolating statistic between the set partition major index of Sagan and its “hard” analog.

We give bijections on restricted growth functions and rook placements on stairstep Ferrers boards to show that the q -Stirling numbers of the second kind, described by Gould, arise as generating functions for various statistics on set partitions. We also describe a two-variable, p, q -Stirling number which is the generating function for the joint distribution of pairs of statistics.

We give a combinatorial proof that the coefficient of zAB in a certain rational function is a sum of two binomial coefficients.

Let G n be the graph of permutations with edges drawn between permutations differing by an adjacent transposition. Using the Kazhdan-Lusztig representations of S n and combinatorial arguments, we show that integers frequently occur in the spectrum of G n . That 0 and −1 are among the integers which arise has application to finite Radon transforms and to existence of perfect 1-codes on G n

The Littlewood-Richardson rule is a combinatorial procedure for computing the multiplicities of irreducible characters of the symmetric group in the decomposition of certain reducible characters. Proofs of this rule usually rely on an algebraically equivalent formulation in terms of Schur functions. This paper presents a proof of the rule based totally on the characters. It uses the Murnaghan-Nakayama formula as the combinatorial description of the relevant characters of the symmetric group. The proof introduces a new kind of tableau, called a hybrid tableau, which displays both column-strict and rim-hook behavior. The proof makes extensive use, including recursive use, of the involution principle of Garsia and Milne.

We describe the domino Schensted algorithm of Barbasch, Vogan, Garfinkle and van Leeuwen. We place this algorithm in the context of Haiman's mixed and left-right insertion algorithms and extend it to colored words. It follows easily from this description that total color of a colored word maps to the sum of the spins of a pair of $2$-ribbon tableaux. Various other properties of this algorithm are described, including an alternative version of the Littlewood-Richardson bijection which yields the $q$-Littlewood-Richardson coefficients of Carré and Leclerc. The case where the ribbon tableau decomposes into a pair of rectangles is worked out in detail. This case is central in recent work by D. White on the number of even and odd linear extensions of a product of two chains.

In the SW part of the Southern Uplands of Scotland the relatively thin Moffat Shale Group (late Ordovician–early Silurian) is succeeded by a thick development of Silurian greywackes, of variable turbiditic facies. This includes late Llandovery (Telychian) quartzose greywackes with interbedded thin graptolitic shales of the turriculatus and crispus biozones, in the upper part of the Gala Group, a sequencewhich is laterally equivalent to the basal part of the Hawick Group. The age of the finer-grained calcareous Hawick Group, which here includes 1. the Ross Formation, ranges from late Llandovery (turriculatus Biozone) to early Wenlock (riccartonensis Biozone). The Riccarton Group, which contains thick units of thinly-bedded siltstones and mudstones, is of Wenlock age (riccartonensis to lundgreni biozones). Within this sequence, all the biozones of the standard graptolite zonal scheme have been recognised in the area, with the exception of the crenulata Biozone of the late Llandovery (Telychian Stage) and the murchisoni and ellesae biozones of the Wenlock (Sheinwoodian Stage). Details of the graptolite biostratigraphy areclosely comparable with those of the markedly thinner sequences of northern England. Acritarchs occur throughout the sequence but are most numerous and best preserved in the Gala Group. Poorly preserved chitinozoa and spores are also present, the former occurring sporadically throughout the succession but the latter become common only in the Riccarton Group.

A review of lithofacies and fossil distributions in the Downton strata of the Welsh Borderland and Wales indicates that these beds form a suitable basis for definition of a chronostratigraphical division of Series rank within the Silurian System. The basal boundary stratotype for the Downton Series is defined at the base of the Ludlow Bone Bed Member of the Downton Castle Sandstone Formation in a section at Whitcliffe Road, Ludlow. Shallow water marine sediments span the boundary, with no evidence of a measurable time break. Correlation of the base of the Downton Series from eastern North America through Baltoscandia and Poland suggests that it lies at or very close to the base of the Monograptus ultimus Biozone and thus approximates to the base of the Přiacute;doli beds of Bohemia. This paper formed a submission to the Subcommission on Silurian Stratigraphy in May. 1981. □Silurian, Downtown Series, standard subdivision, lithostratigraphy, biostratigraphy, chronostratigraphy, correlation.

If the irreducible characters of the symmetric group are interpreted combinatorially using the Murnaghan-Nakayama formula, a sign reversing involution is given which proves the orthogonality formula of the first kind for these characters.

Probabilistic analogs of combinatorial problems from the general class of problems associated with Po1ya's Theorem and its numerous extensions are described. Several basic models for the random generation of functions in a finite function space are considered. Measures of the symmetry of a function with respect to certain classes of group actions on the space of functions are considered as random variables and methods for computing their moments and distributions are discussed. Other random variables associated with local restrictions on the functions are also considered. Some asymptotic results are given

This paper considers the problem of enumerating the elements of a set under a group action with a given automorphism group. The problem is approached from a linear algebraic point of view, with a class of identities obtained by applications of appropriate linear operators and functionals. A variety of new counting and enumerating results are obtained in this manner, and the connections to the recent work of de Bruijn, Foulkes, Sheehan, Stockmeyer and White are defined. Included among the new results are general formulas for enumerating patterns with a given automorphism group when a group acts on the range and domain of a finite function space. In this case, the multilinear computing techniques developed by Williamson are exploited.

Recursive matching algorithms based on two standard recursions in the subset lattice are analyzed and shown to produce the same explicit matching function ϕ. It is shown that for a large class of linear orders on the subset lattice the mapping defined recursively by matching in order subsets of size l to first available subsets of size l + 1 is a matching in the lattice and equals ϕ.

A generalization of the binomial theorem is proved for sequences of polynomials of binomial type. The equivalence of two formulas which count group-invariant partitions is shown to be a consequence of this theorem. The theorem is also used to demonstrate the equivalence of two formulas for rook polynomials.

It is observed that if @D is a system of orbit representatives for the action of a finite group G on a G-stable subset L of a finite set S and if F is a field of characteristic zero, then F^S is an algebra of dimension |S|. Furthermore, if S = R^D, the set of functions from a finite set D to a finite set R, then F^S has a multilinear structure. A general problem is stated: Given linear operators T"1 and T"2, construct vectors v"1, ... v"[email protected]^S such that T"2I"@D = T"1(v"1 + ... + v"t) where l"@D is the indicator or characteristic function of @D. (Note that this construction gives, in some sense, a solution to the problem of isomorph rejection.) For appropriate choices of T"1 and T"2, two approaches to this construction problem are considered. These are the principle of inclusion-exclusion and backtrack computer programming. In particular, these approaches are discussed when S = R^D and the vectors to be constructed are pure or homogeneous tensors.

A combinatorial and algebraic approach has been applied to the problem of determining the number of distinct configurations of univariant reaction lines about an invariant point, NC, in nondegenerate n-component systems. The resulting expression is $$NC = [1/(4n + 8)]\left( {\sum {[2^{d/2} (\phi (2n + 4)/d]) + (n + 2) 2^{\{ (n + 2)/2\} } } } \right) - 1$$ where the summation is taken over all values of d which divide (2n + 4)evenly but which do not divide (n + 2)evenly, [(n + 2)/2]is the smallest integer greater than or equal to (n + 2)/2,and o[(2n + 4)/d]is the number of integers less than (2n + 4)/d whose only factor is common with (2n + 4)/d is 1.This concise expression is derived through the application of Burnside's lemma, which relates the number of equivalence classes into which a set S is divided by an equivalence relation induced by a permutation group of S to the number of elements of S left invariant by the members of the permutation group. In the derivation of the above expression, the set S is taken to be the set of all possible configurations and orientations of univariant lines about an invariant point, the permutation group is taken to be the set of rigid-body symmetries of S, and the equivalence classes are composed of the different orientations of each configuration. Although the methods used to obtain the above expression are probably unfamiliar to most geologists, they are standard mathematical techniques and represent just one application of these tools to problems of geologic interest.

When S is a finite set and G a finite group acting on S, we consider the problem of rejecting isomorphs in a G-stable subset of S. In previous work we developed a linear algebraic context for this problem by constructing the finite dimensional vector spaceF s whereF is a field of characteristic zero. When S is a finite function space, or a finite direct product of finite function spacesF s acquires a multilinear structure By various specializations ofG and S and by applications of results which have appeared elsewhere, identities of Sheehan, deBruijn and P61ya are obtained. Furthermore, these same techniques are applied to examples which do not have a clear resolution using the more common formulas

Suppose ϱ and β are partitions of n. If ϱ ⋍ β, a bijection is given between positive pairs of rim hook tableaux of the same shape λ and content β and ϱ, respectively, and negative pairs of rim hook tableaux of some other shape μ and content β and ϱ, respectively. If ϱ = β, the bijection is between positive pairs and either negative pairs or permutations of hooks. The bijection, in the latter case, is a generalization of the Schensted correspondence between pairs of standard tableaux and permutations. If the irreducible characters of Sn are interpreted combinatorially using the Murnaghan-Nakayama formula, these bijections prove ∑ λ X λ ρ X λ β =δ ρβ 1 j1 J1!2 j2 J2!… where ϱ = 1j12j2….

A finite dimensional multilinear algebraic point of view is adopted to study the theory of enumeration under a group action. The classical results of Polya, deBruijn, and others are presented. These results are extended in various ways. These extensions include the study of patterns with prescribed symmetry or with prescribed boundary conditions. The non-discrete nature of the underlying multilinear structure is utilized to present several models for the random generation of patterns.

We consider families $\{ {\bf C}(n,k):O \leqq k \leqq n\} $ where each ${\bf C}(n,k)$ is a set of combinatorial objects, $C(n,k) = |{\bf C}(n,k)|$ satisfies a recursion $C(n,k)= a_{n,k}C(n - 1,k - 1) + b_{n,k} C(n - 1,k)$, and each object in ${\bf C}(n,k)$ is represented by an n-vector. We study “loop-free” or “uniformly bounded transition” algorithms, i.e., algorithms which yield linear orders on the sets ${\bf C}(n,k)$ so that the vectors representing consecutive objects are “close to each other” (combinatorial Gray codes).Key words. listing algorithms, uniformly bounded operations, uniformly bounded transition algorithms, loop-free algorithms, binary reflected Gray codes, combinatorial Gray codes, binomial grids

This paper considers certain linear and multilinear aspects of the classical isomorph rejection problem. Specifically, elements of a finite set S are considered as elements of a finite dimensional vector space. Some classical and more recent formulations of Bumside's Lemma are stated and proved in this linear algebraic setting. It is observed that the specialization of S as a finite function space yields a multilinear structure on the underlying vector space. It is remarked that the multilinear structure may be exploited to achieve Po1ya-like counting theorems

If a group acts on a set, an action of the group is induced on the partitions of the set. A formula is developed for the number of partitions invariant under this action. The formula is extended to count combinatorial objects such as labeled rooted trees or permutations defined on the invariant partitions.

A computer-operated millimeter-wave measurement system is described. The set performs automated insertion-loss and return-loss measurements on a stepped, discrete frequency basis, and covers the frequency range 40 to 110 GHz. Some notable features of the system are: a computer-controlled signal source of a BWO, extensive error reduction through real-time computer processing, and use of a harmonic comb mixer as a source of precisely known millimeter-wave reference frequencies. Measurement principles and performance features of the system are presented.

It is shown that the Kostka numbers respect a natural partial order (reverse domination) on the integer partitions. It is then proved that the number of Polya patterns with a given weight also respects this order. Immediate consequences include the unimodality of the number of graphs with n vertices and k edges and the unimodality of the coefficients of the expansion of the Gaussian coefficient m+n n .

Let G be a finite group acting on a finite set S and hence on $\Pi (S)$, the lattice of partitions of S. Computational methods are developed for enumerating the invariants of this action.

1. Introduction. The remarkable 1927 paper by J. H. Redfield [13] which anticipated many recent combinatorial results in Polya counting theory and, in fact, predated Polya's theorem by ten years has been discussed at length by Harary and Palmer [8], Foulkes [5; 6], Sheehan [15; 16] and Read [12], not to mention de Bruijn [3] and others. We shall, in this paper, demonstrate how multilinear techniques may be used in this context. The Redfield superposition theorem and decomposition theorem turn out to be statements about a group acting on finite function spaces, and may thus be dealt with in multilinear terms. We shall prove Redfield's results and an extension due to Foulkes [5].

A formula, analogous to the classical Burnside lemma, is developed which counts orbit representatives from a set under a group action with a given stabilizer subgroup conjugate class. This formula is applied in a manner analogous to a proof of Podlya's theorem to obtain an enumeration of patterns with a given automorphism group. 1. Let S be a finite set and G a finite group acting on S. Let A be a system of orbit representatives for G acting on S. The following theorem is well known: Theorem 1 (Burnside [1]). For any function co defined on S satisfying o(os) = o(s) for all a E G, for all s E 5, we have E a)(S) = 1 Ei: E (s)x(us = S) SEsA IGI JEG sES where X1 if statement is true, y(staztem en t)= ot O otherwise. For s E S let Gs = la E G: ars = s} be the stabilizer subgroup of G at T~~~~~~ S. I et G1, G2, .. . GN be a complete set of nonconjugate subgroups of G, ordered such that IG1 > ...> GN. For any two subgroups H, K C G we define M (H)= ? X(uHac-1 C K). K 7K I o-EG Received by the editors July 1, 1973. AMS(MOS) subject classifications (1970). Primary 05A15, 20B25; Secondary 05C25.

We develop a formula for enumerating the partitions of a set up to the action of a group. We give some special cases of this formula and illustrate its use with an example. Some comments are made relating the formula to an earlier formula.

We consider hooks, hook tableaux, rim hooks, and rim hook tableaux where all hooks and rim hooks have length k . Using a rim hook version of the “jeu d'taquin” of Schutzenberger and the orientation of a rim hook (its mod k distance from the main diagonal), we give a simple alternative description of the ∗-diagrams of Robinson. The rim hook Schensted correspondence given by one of us in a previous paper then decomposes into a k -tuple of ordinary Schensted correspondences. This decomposition is used to “lift” the important applications of the ordinary Schensted correspondence to the rim hook Schensted correspondence. These include applications to inverses, increasing and decreasing subsequences, and the Schutzenberger evacuation procedure.

When the Schur function is written as a linear combination of products of symmetric power sums, it takes the form of a character-weighted cycle index polynomial. A Polya-like interpretation is given to this formula and a purely combinatorial proof is given. Some observations concerning general group actions are made.

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of ''O's'' and ''1's'' with k ''1's''. Two such subsets are adjacent if one can be obtained from the other by switching a ''O'' and a ''1'' which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding ''Gray codes'' of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n>=7 and that such a cycle does exist in all other cases where k=

Let P be a finite partially ordered set with a fixed labeling. The sign of a linear extension of P is its sign when viewed as a permutation of the labels of the elements of P. Call P sign-balanced if the number of linear extensions of P of positive sign is the same as the number of linear extensions of P of negative sign. In this paper we determine when the posets in a particular class are sign-balanced. When posets in this class are not sign-balanced, we determine the difference between the number of positive linear extensions and the number of negative linear extensions. One special case of this class is the product of an m-chain with an n-chain, m and n both >1. In this case, we show P is sign-balanced if and only if m≡n mod2.

We describe various aspects of the Al Salam-Carlitz q -Charlier polynomials. These include combinatorial descriptions of the moments, the orthogonality relation, and the linearization coefficients.

This paper studies the relationship between the rook vector of a general board and the chromatic structure of an associated set of graphs. We prove that every rook vector is a chromatic vector. We give algebraic relations between the factorial polynomials of two boards and their union and sum, and the chromatic polynomials of two graphs and their union and sum.

At a basic level, one would expect that constructive combinatorics would address the question of how one constructs the fundamental objects in combinatorics. In fact, “constructing” these objects could mean providing an algorithm for listing all of them, or it could mean generating one of them at random. While both questions are of interest, we shall concentrate on the first.

Partially ordered sets, or posets, appear in many branches of mathematics, but they are fundamental in combinatorics. For example, many of the important enumeration techniques (generating functions, inclusion-exclusion) have their theoretical foundation in some underlying poset.

We introduce a new tool, the factorial polynomials, to study rook equivalence of Ferrers boards. We provide a set of invariants for rook equivalence as well as a very simple algorithm for deciding rook equivalence of Ferrers boards. We then count the number of Ferrers boards rook equivalent to a given Ferrers board.