On the combinatorics of the Pfaff identity

Recently, there has been a revival of interest in the Pfaff identity on hypergeometric series because of the specialization of Simons and a generalization of Munarini. We present combinatorial settings and interpretations of the specialization and the generalization; one is based on free Dyck paths and free Schröder paths, and the other relies on a correspondence of Foata and Labelle between the Meixner endofunctions and bicolored permutations, and an extension of the technique developed by Labelle and Yeh for the Pfaff identity. Applying the involution on weighted Schröder paths, we derive a formula for the Narayana numbers as an alternating sum of the Catalan numbers.     

Combinatorial data analysis: Confirmatory comparisons between sets of matrices

The task of assessing the similarity of pattern between the entries of two square matrices has been discussed extensively over the last decade, as a unifying strategy for approaching a variety of seemingly disparate statistical problems. As typically defined, the comparison depends on a measure of matrix correspondence, usually a normalized cross-product measure of some form, that is evaluated for relative size by the use of a reference distribution constructed through an equally likely permutation hypothesis defined at the level of the objects corresponding to the rows and columns of the two matrices. The extreme generality provided by this very simple framework subsumes a variety of different statistical problems, ranging from the study of spatial autocorrelation for variables observed over a set of geographic locations, to the topics of analysis of variance, the measurement of rank correlation, and confirmation techniques concerned with various conjectures of combinatorial structure that might be posited for an empirically determined measure of relationship between pairs of a given set of objects. The comparison strategies extant always assume that both matrices are fixed, and in those cases where one of the matrices codifies a given theoretical structure to be evaluated according to a second, this assumption can lead to substantial arbitrariness in how matrix similarity might be indexed, and thus, in how the comparison is implemented. As developed in this paper, exactly the same principles appropriate for use in the fixed comparison context can be extended to include matrices constructed through optimally weighted linear combinations of other sets of matrices. This generalization provides one mechanism for developing comparison strategies that allow assessment against very broad classes of matrices, which in turn serve to represent very general conjectures of possible combinatorial structure. This paper reviews some of these extensions in detail, with a particular emphasis on categorical and ordered categorical variables and whether they may reflect an empirically generated measure of object relationship.     

Normal subgroups of nonstandard symmetric and alternating groups

Let be a nonstandard model of Peano Arithmetic with domain M and let be nonstandard. We study the symmetric and alternating groups S _n and A _n of permutations of the set internal to , and classify all their normal subgroups, identifying many externally defined such normal subgroups in the process. We provide evidence that A _n and S _n are not split extensions by these normal subgroups, by showing that any such complement if it exists, cannot be a limit of definable sets. We conclude by identifying an -valued metric on and (where B _S , B _A are the maximal normal subgroups of S _n and A _n identified earlier) making these groups into topological groups, and by showing that if is -saturated then and are complete with respect to this metric.      

Permutations via linear translators

We show that many infinite classes of permutations over finite fields can be constructed via translators with a large choice of parameters. We first characterize some functions having linear translators, based on which several families of permutations are then derived. Extending the results of [9], we give in several cases the compositional inverse of these permutations. The connection with complete permutations is also utilized to provide further infinite classes of permutations. Moreover, we propose new tools to study permutations of the form $x\mapsto x+{(x^{p^m}-x+\delta )}^s$ and a few infinite classes of permutations of this form are proposed.     

Odd length for even hyperoctahedral groups and signed generating functions

We define a new statistic on the even hyperoctahedral groups which is a natural analogue of the odd length statistic recently defined and studied on Coxeter groups of types $A$ and $B$. We compute the signed (by length) generating function of this statistic over the whole group and over its maximal and some other quotients and show that it always factors nicely. We also present some conjectures.     

The structure of alternative tableaux

In this paper we study alternative tableaux introduced by Viennot [X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk in Cambridge, 2008]. These tableaux are in simple bijection with permutation tableaux, defined previously by Postnikov [A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764v1 [math.CO], 2006].We exhibit a simple recursive structure for alternative tableaux, from which we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labeled trees. Finally, we exhibit a bijection with permutations, and relate it to some other bijections that already appeared in the literature.     

q-Analog of tableau containment

We prove a q-analog of the following result due to McKay, Morse and Wilf: the probability that a random standard Young tableau of size n contains a fixed standard Young tableau of shape λ?k tends to fλ/k! in the large n limit, where fλ is the number of standard Young tableaux of shape λ. We also consider the probability that a random pair (P,Q) of standard Young tableaux of the same shape contains a fixed pair (A,B) of standard Young tableaux.