A method for proving polynomial enumeration formulas

We present an elementary method for proving enumeration formulas which are polynomials in certain parameters if others are fixed and factorize into distinct linear factors over Z. Roughly speaking the idea is to prove such formulas by “explaining” their zeros using an appropriate combinatorial extension of the objects under consideration to negative integer parameters. We apply this method to prove a new refinement of the Bender-Knuth (ex-)Conjecture, which easily implies the Bender-Knuth (ex-)Conjecture itself. This is probably the most elementary way to prove this result currently known. Furthermore we adapt our method to q-polynomials, which allows us to derive generating function results as well. Finally we use this method to give another proof for the enumeration of semistandard tableaux of a fixed shape which differs from our proof of the Bender-Knuth (ex-)Conjecture in that it is a multivariate application of our method.     

Enumeration formulas for standard Young tableaux of nearly hollow rectangular shapes

This paper considers the enumeration problem of a generalization of standard Young tableau (SYT) of truncated shape. Let $\lambda ?\mu |\left\{(i_0,j_0)\right\}$ be the SYT of shape $\lambda$ truncated by $\mu$ whose upper left cell is $(i_0,j_0)$, where $\lambda$ and $\mu$ are partitions of integers. The summation representation of the number of SYT of the truncated shape $(n+k+2,{(n+2)}^{m+1})?\left(n^m\right)|\left\{(2,2)\right\}$ is derived. Consequently, three closed formulas for SYT of hollow shapes are obtained, including the cases of (i). $m=n=1$, (ii). $k=0$, and (iii). $k=1,m=n$. Finally, an open problem is posed.     

Adjacency of Young tableaux and the Springer fibers

We connect different results about irreducible components of the Springer fibers of type A. Firstly, we show a relation between the Spaltenstein partition of the fibers and a total order on the set of standard Young tableaux. Next, using a result of Steinberg, we connect a work of the first author to the Robinson–Schensted map. We also perform the Spaltenstein study of the relative position of the Springer fibers and -fibrations of the flag manifold. This leads us to consider the adjacency relation on the set of standard Young tableaux and to define oriented and labeled graphs with the standard Young tableaux as vertices. Using this adjacency relation, we describe some smooth irreducible components of the Springer fibers. Finally, we show that these graphs can be identified with some full subgraphs of the Bruhat graph.     

Oscillating rim hook tableaux and colored matchings

We find a correspondence between oscillating m-rim hook tableaux and m-colored matchings, where m is a positive integer. An oscillating m  -rim hook tableau is defined as a sequence (λ⁰,λ¹,…,λ2n)$({\lambda }^0,{\lambda }^1,\dots ,{\lambda }^{2n})$ of Young diagrams starting with the empty shape and ending with the empty shape such that λi${\lambda }^i$ is obtained from λi−1${\lambda }^{i-1}$ by adding an m-rim hook or by deleting an m-rim hook. Our bijection relies on the generalized Schensted algorithm due to White. An oscillating 2-rim hook tableau is also called an oscillating domino tableau. When we restrict our attention to two column oscillating domino tableaux of length 2n  , we are led to a bijection between such tableaux and noncrossing 2-colored matchings on {1,2,…,2n}$\{1,2,\dots ,2n\}$, which are counted by the product CnC_n+1$C_n{C}_{n+1}$ of two consecutive Catalan numbers. A 2-colored matching is noncrossing if there are no two arcs of the same color that are intersecting. We show that oscillating domino tableaux with at most two columns are in one-to-one correspondence with Dyck path packings. A Dyck path packing of length 2n   is a pair (D,E)$(D,E)$, where D is a Dyck path of length 2n, and E is a dispersed Dyck path of length 2n that is weakly covered by D. So we deduce that Dyck path packings of length 2n   are counted by CnC_n+1$C_n{C}_{n+1}$.     

The Robinson-Schensted correspondence for skew oscillating semi-standard tableaux

We introduce an analogue of the Robinson-Schensted correspondence for skew oscillating semi-standard tableaux that generalizes the correspondence for skew oscillating standard tableaux. We give a geometric construction for skew oscillating semi-standard tableaux and examine its combinatorial properties.     

On summation formulas due to Plana, Lindelöf and Abel, and related Gauss-christoffel rules, I

Three methods, old but not so well known, transform an infinite series into a complex integral over an infinite interval. Gauss quadrature rules are designed for each of them. Various questions concerning their construction and application are studied, theoretically or experimentally. They are so efficient that they should be considered for the development of software for special functions. Applications are made to slowly convergent alternating and positive series, to Fourier series, to the numerical analytic continuation of power series outside the circle of convergence, and to ill-conditioned power series.     

On the permanent of random Bernoulli matrices

We show that the permanent of an n×n matrix with iid Bernoulli entries ±1 is of magnitude with probability 1−o(1). In particular, it is almost surely non-zero.     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

Counting formulas for glued lattices

A tolerance relation of a lattice L, i.e., a reflexive and symmetric relation of L which is compatible with join and meet, is called glued if covering blocks of have nonempty intersection. For a lattice L with a glued tolerance relation we prove a formula counting the number of elements of L with exactly k lower (upper) covers. Moreover, we prove similar formulas for incidence structures and graphs and we give a new proof of Dilworth's covering theorem.     

Slowing down and reflection of waves in truncated periodic media

We consider wave propagation and scattering governed by 1-D Schrödinger operators with truncated periodic potentials. The propagation of wave packets with narrow frequency supports is studied. The goal is to describe potentials for which the group velocity (for a periodic problem) is small and the transmission coefficient for the truncated potential is not too small, i.e. to find media where a slowing down of the wave packets coexists with a transparency.     

On the enumeration of skew Young tableaux

For fixed n and a fixed partition α of k<n we give an explicit formula for the number N(n;α) of standard skew Young tableaux with n squares and shape λ/α for some λ. From this formula the entire asymptotic expansion of N(n;α) as n→∞ can in principle be computed, generalizing recent work of McKay, Morse, and Wilf. We also give asymptotic formulas for the number f^λ/α of standard skew Young tableaux of shape λ/α for α fixed and λ “large.”     

Some asymptotic results useful in enumeration problems

Suppose one is given two related generating functionsa(x) = a _n x ⁿ andb(x) = b _n x ⁿ , often it is of interest to determine the limiting behaviour of the quantitiesa _n /b _n We survey some earlier results of this nature and give some new ones     

Prefilter spaces and a precompletion of preuniform convergence spaces related to some well-known completions

In non-symmetric Convenient Topology the notion of pre-Cauchy filter is introduced and the construction of a precompletion of a preuniform convergence space is given from which Wyler's completion of a separated uniform limit space [O. Wyler, Ein Komplettierungsfunktor für uniforme Limesräume, Math. Nachr. 46 (1970) 1-12] as well as Weil's Hausdorff completion of a separated uniform space [A. Weil, Sur les Espaces à Structures Uniformes et sur la Topologie Générale, Hermann, Paris, 1937] can be derived (up to isomorphism). By the way, the construct PFil of prefilter spaces, i.e. of those preuniform convergence space which are ‘generated’ by their pre-Cauchy filters, is a strong topological universe filling in a gap in the theory of preuniform convergence spaces.     

Some asymptotic results useful in enumeration problems

Suppose one is given two related generating functionsa(x) = a _n x ⁿ andb(x) = b _n x ⁿ , often it is of interest to determine the limiting behaviour of the quantitiesa _n /b _n We survey some earlier results of this nature and give some new ones     

On the enumeration of a class of plane multigraphs

A class of plane multigraphs having a series-parallel structure is defined and enumerated. The enumeration is carried out both for the rooted graphs as originally defined, and also for those where no distinctions are made between the vertices. Some other related problems are also discussed.     

Enumerating Permutations Avoiding Three Babson-Steingrímsson Patterns

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     

An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem

Text

We analyze an enumeration associated with the Josephus problem by applying a Fourier transform to a multivariate generating function. This yields a formula for the enumeration that reduces to a simple expression under a condition we call local prime abundance. Under this widely held condition, we prove (Corollary 3.4) that the proportion of Josephus permutations in the symmetric group Sn that map t to k (independent of the choice of t and k) is 1/n. Local prime abundance is intimately connected with a well-known result of S.S. Pillai, which we exploit for the purpose of determining when it holds and when it fails to hold. We pursue the first case where it fails, reducing an intractable DFT computation of the enumeration to a tractable one. A resulting computation shows that the enumeration is nontrivial for this case.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=DnZi-Znuk-A.     

On a problem of Erdős and Lovász: Random lines in a projective plane

Letn(k) be the least size of an intersecting family ofk-sets with cover numberk, and let _k denote any projective plane of orderk–1.Theorem There is a constant A such that ifH is a random set ofm Aklogk lines from _k then P_r(H<)0(k).Corollary If there exists a _k thenn(k)=O(klogk). These statements were conjectured by P. Erds and L. Lovász in 1973.Supported in part by NSF-DMS87-83558 and AFOSR grants 89-0066, 89-0512 and 90-0008     

Rota’s umbral calculus and recursions

Umbral Calculus can provide exact solutions to a wide range of linear recursions. We summarize the relevant theory and give a variety of examples from combinatorics in one, two and three variables.Dedicated to the Memory of Gian-Carlo Rota