Symmetrically Constrained Compositions (2009)
Beck, Matthias, Gessel, Ira M., Lee, Sunyoung, Savage, Carla D.
Given integers $a_1, a_2, ..., a_n$, with $a_1 + a_2 + ... + a_n \geq 1$, a symmetrically constrained composition $\lambda_1 + lambda_2 + ... + lambda_n = M$ of $M$ into $n$ nonnegative parts is one...
Multilinear generating functions for Charlier polynomials (2009)
Gessel, Ira M., Jayawant, Pallavi
Charlier configurations provide a combinatorial model for Charlier polynomials. We use this model to give a combinatorial proof of a multilinear generating function for Charlier polynomials. As...
Even and Odd Pairs of Lattice Paths With Multiple Intersections (2008)
Abstract. Let be the number of ordered pairs of paths in the plane, with unit steps E or N, that intersect k times in which the first path ends at the point (r,n-r) and the second path ends at the...
HYPERGRAPHS AND A FUNCTIONAL EQUATION OF BOUWKAMP AND DE BRUIJN (2008)
n=0 cmnu m v n. Bouwkamp and de Bruijn Abstract. Let Φ(u, v) = � ∞ m=0 found � that there exists a power � series Ψ(u, v) satisfying the equation tΨ(tz, z) = log. We show that this result...
Carla D. Savage, Ira M. Gessel, Herbert S. Wilf
joint distribution of descent and major index over
AN INTRODUCTION TO LATTICE PATH ENUMERATION (2008)
Abstract. This tutorial talk will describe some of the basic problems and methods of lattice path enumeration, including the reflection principle, the method of images, the
A recently Monthly article [1, Theorem 4] gave an incorrect proof of the following result (which was also stated incorrectly): Let p beaprime and let k beanonnegative integer such that k<p − 2....
search, and simplicial complex partitions (2008)
The Tutte polynomial of a graph, depth-first
RANDOM WALK IN A WEYL CHAMBER 1 (2008)
Ira M. Gessel, Doron Zeilberger
Abstract: The classical Ballot problem that counts the number of ways of walking from the origin and staying within the wedge x1 ≥ x2 ≥... ≥ xn (which is a Weyl chamber for the symmetric...
A refinement of Cayley’s formula for trees (2008)
A proper vertex of a rooted tree with totally ordered vertices is a vertex that is the smallest of all its descendants. We count several kinds of labeled rooted trees and forests by the number of...
Acyclic orientations and chromatic generating functions (2008)
www.cs.brandeis.edu / ~ ira
A Combinatorial Interpretation of the Numbers 6 (2n)! /n! (n + 2)! (2008)
It is well known that the numbers (2m)! (2n)!/m! n! (m + n)! are integers, but in general there is no known combinatorial interpretation for them. When m = 0 these numbers are the middle binomial...
Brian Drake, Ira M. Gessel, Guoce Xin
We prove and generalize a conjecture of Goulden, Litsyn, and Shevelev that certain Laurent polynomials related to the solution of a functional equation have only odd negative powers. 1
conjectured a relation between Hankel determinants whose en-
Abstract. One form of the inclusion-exclusion principle asserts that if A and B are functions of finite sets then the formulas A(S) = � B(T) and B(S) = T ⊆S � T ⊆S (−1)|S|−|T | A(T) are...
A triple lacunary generating function for Hermite (2008)
Ira M. Gessel, Pallavi Jayawant
polynomials
On the Order of Stirling Numbers and Alternating Binomial Cofficient Sums (2007)
Ira M. Gessel, Tamás Lengyel, Tam As Lengyel
this paper is to analyze # p (k! S(n, k)) for an arbitrary prime p. It turns out that identity (1) can be generalized to calculate the exact value of # p (k! S(n, k)) if n =
Abstract. We count labeled acyclic digraphs according to the number sources, sinks, and edges.
Abstract. We count labeled acyclic digraphs according to the number sources, sinks, and edges. 1. Counting acyclic digraphs by sources. Let An(t; α) = � D α s(D) t e(D), where the sum is over all...
A Bijective Approach to the Permutational Power of a Priority Queue (2007)
A priority queue transforms an input permutation p 1 of a totally ordered set of size n into an output permutation p 2. Atkinson and Thiyagarajah showed that the number of such pairs (p 1; p 2) is...
Applications of the classical umbral calculus (2007)
Dedicated to the memory of Gian-Carlo Rota Abstract. We describe applications of the classical umbral calculus to bilinear generating functions for polynomial sequences, identities for Bernoulli and...
A major index for matchings and set partitions (2007)
Chen, William Y. C, Gessel, Ira M., Yan, Catherine H., Yang, Arthur L. B.
We introduce a statistic $\pmaj$ on partitions of $[n]=\{1,2,..., n\}$, and show that it is equidistributed with the number of 2-crossings over partitions of $[n]$ with given sets of minimal block...
Gessel, Ira M., Lv, Lun, Xin, Guoce, Zhou, Yue
We introduce an elementary method to give unified proofs of the Dyson, Morris, and Aomoto identities for constant terms of Laurent polynomials. These identities can be expressed as equalities of...
Drake, Brian, Gessel, Ira M., Xin, Guoce
I. P. Goulden, S. Litsyn, and V. Shevelev [On a sequence arising in algebraic geometry, J. Integer Sequences 8 (2005), 05.4.7] conjectured that certain Laurent polynomials associated with the...
A short proof of the Zeilberger-Bressoud q-Dyson theorem (2006)
Abstract. We give a formal Laurent series proof of Andrews’s q-Dyson Conjecture, first proved by Zeilberger and Bressoud. 1.
A refinement of Cayley's formula for trees (2005)
Gessel, Ira M., Seo, Seunghyun
A proper vertex of a rooted tree with totally ordered vertices is a vertex that is less than all its proper descendants. We count several kinds of labeled rooted trees and forests by the number of...
Symmetric inclusion-exclusion (2005)
One form of the inclusion-exclusion principle asserts that if A and B are functions of finite sets then A(S) is the sum of B(T) over all subsets T of S if and only if B(S) is the sum of (-1)^|S-T|...
A Short Proof of the Zeilberger-Bressoud $q$-Dyson Theorem (2004)
We give a formal Laurent series proof of Andrews's $q$-Dyson Conjecture, first proved by Zeilberger and Bressoud.
Hypergraphs and a functional equation of Bouwkamp and de Bruijn (2004)
Gessel, Ira M., Kalikow, Louis H.
We show that a 1969 result of Bouwkamp and de Bruijn on a formal power series expansion can be interpreted as the hypergraph analogue of the fact that every connected graph with n vertices has at...
A triple lacunary generating function for Hermite polynomials (2004)
Gessel, Ira M., Jayawant, Pallavi
Some of the classical orthogonal polynomials such as Hermite, Laguerre, Charlier, etc. have been shown to be the generating polynomials for certain combinatorial objects. These combinatorial...
Adin, Ron M., Gessel, Ira M., Roichman, Yuval
A classical result of MacMahon gives a simple product formula for the generating function of major index over the symmetric group. A similar factorial-type product formula for the generating function...
A Combinatorial Interpretation of The Numbers $6(2n)! /n! (n+2)!$ (2004)
It is well known that the numbers $(2m)! (2n)!/m! n! (m+n)!$ are integers, but in general there is no known combinatorial interpretation for them. When $m=0$ these numbers are the middle binomial...
Abstract. E. Catalan stated in 1874 that the numbers (2m)! (2n)!/m! n!(m+n)! are integers. When m = 0 these numbers are the middle binomial coefficients �2n �. When m = 1 they are n twice the...
The polynomial part of a restricted partition function related to the Frobenius problem (2003)
Beck, Matthias, Gessel, Ira M., Komatsu, Takao
Given a set of positive integers A = {a_1,...,a_n}, we study the number p_A (t) of nonnegative integer solutions (m_1,...,m_n) to m_1 a_1 + ... m_n a_n = t. We derive an explicit formula for the...
Applications of the classical umbral calculus (2001)
We describe applications of the classical umbral calculus to bilinear generating functions for polynomial sequences, identities for Bernoulli and related numbers, and Kummer congruences.
We prove that the order of divisibility by prime p of k! S(a(p − 1) pq,k)doesnot depend on a and q if q is sufficiently large and k/p is not an odd integer. Here S(n, k) denotes the Stirling number...
The polynomial part of a restricted partition function related to the Frobenius problem (2001)
Matthias Beck, Takao Komatsu, Ira M. Gessel
Given a set of positive integers A = {a1,...,an}, we study the number pA(t) of nonnegative integer solutions (m1,...,mn)to �n j=1 mjaj = t. We derive an explicit formula for the polynomial part of...
The polynomial part of a restricted partition function related to the Frobenius problem (2001)
Matthias Beck, Takao Komatsu, Ira M. Gessel
Given a set of positive integers A = {a1,...,an}, we study the number pA(t) of nonnegative integer solutions (m1,...,mn) to �n j=1 mjaj = t. We derive an explicit formula for the polynomial part of...
The polynomial part of a restricted partition function related to the Frobenius problem (2001)
Matthias Beck, Ira M. Gessel, Takao Komatsu
Frobenius problem
Mathematical Monthly in 1974 [2]: (1999)
The following problem, proposed by Russell Maurer, appeared in the American
On Miki's Identity For Bernoulli Numbers (1999)
. We give a short proof of Miki's identity for Bernoulli numbers, n-2 # i=2 # i #n-i - n-2 # i=2 # n i # # i #n-i =2Hn#n , for n # 4 where, # i = B i /i, B i is the ith Bernoulli number, and Hn...
The Smith College Diploma Problem (1999)
rticular we shall relate the number of passes directly to one of these: A n,k is the number of permutations # of {1,...,n} with k strong excedances, which are values of i for which i<#(i). Before...
Acyclic Orientations And Chromatic Generating Functions (1999)
. Let P (k) be the chromatic polynomial of a graph with n # 2 vertices and no isolated vertices, and let R(k)=P (k +1)/k(k + 1). We show that the coe#cients of the polynomial (1 - t) n-1 # # k=1...
Enumeration of Trees By Inversions (1999)
Ira M. Gessel, Yeong-nan Yeh, Kungl Tekniska Hogskolan, Bruce E. Sagan, Bruce E. Sagan, Bruce E. Sagan
Mallows and Riordan [21] first defined the inversion polynomial, J n (q), for trees with n vertices and found its generating function. In the present work, we define inversion polynomials for...
Enumeration of Tilings of Diamonds and Hexagons with Defects (1999)
Harald A. Helfgott, Ira M. Gessel
We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions to...
Enumeration of Tilings of Diamonds and Hexagons with Defects (1999)
Harald A. Helfgott, Ira M. Gessel
We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions to...
On The Number Of Convex Polyominoes (1999)
. Lin and Chang gave a generating function for the number of convex polyominoes with an m+1byn+ 1 minimal bounding rectangle. We show that their result implies that the number of such polyominoes is...
Abstract. Lin and Chang gave a generating function for the number of convex polyominoes with an m +1by n + 1 minimal bounding rectangle. We show that their result implies that the number of such...
Enumeration of tilings of diamonds and hexagons with defects (1998)
Helfgott, Harald, Gessel, Ira M.
We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions to...
Enumeration of Tilings of Diamonds and Hexagons with Defects (1998)
Harald A. Helfgott, Ira M. Gessel
. We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions...
Ira M. Gessel, C. Krattenthaler
Abstract. A new object is introduced into the theory of partitions that generalizes plane partitions: cylindric partitions. We obtain the generating function for cylindric partitions of a given shape...
Generating functions and generalized Dedekind sums (1997)
Dedicated to Herb Wilf, in honor of his 65th birthday Abstract. We study sums of the form � ζ R(ζ), where R is a rational function and the sum is over all nth roots of unity ζ (often with ζ = 1...
The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions (1996)
depth-first search, spanning tree, acyclic orientation, inversion,
The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions (1996)
One of the most important numerical quantities that can be computed from a graph G is the two-variable Tutte polynomial. Specializations of the Tutte polynomial count various objects associated with...
Generating Functions and Generalized Dedekind Sums (1996)
. We study sums of the form P i R(i), where R is a rational function and the sum is over all nth roots of unity i (often with i = 1 excluded). We call these generalized Dedekind sums, since the most...
Lattice Paths And Faber Polynomials (1996)
. The rth Faber polynomial of the Laurent series f(t)=t + f 0 + f 1 /t + f 2 /t 2 + is the unique polynomial Fr (u) of degree r in u such that Fr (f)= t r + negative powers of t. We apply Faber...
Ira M. Gessel, C. Krattenthaler
. A new object is introduced into the theory of partitions that generalizes plane partitions: cylindric partitions. We obtain the generating function for cylindric partitions of a given shape that...
The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions (1995)
One of the most important numerical quantities that can be computed from a graph G is the two-variable Tutte polynomial. Specializations of the Tutte polynomial count various objects associated with...
Finding identities with the WZ method (1995)
Abstract. Extending the work of Wilf and Zeilberger on WZ-pairs, we describe how new terminating hypergeometric series identities can be derived by duality from known identities. A large number of...
Counting paths in Young's lattice (1993)
Abstract. Young’s lattice is the lattice of partitions of integers, ordered by inclusion of diagrams. Standard Young tableaux can be represented as paths in Young’s lattice that go up by one...
Enumerative Applications of a Decomposition for Graphs and Digraphs (1993)
A simple decomposition for graphs yields generating functions for counting graphs by edges and connected components. A change of variables gives a new interpretation to the Tutte polynomial of the...
this paper were found with the help of the Maple symbolic algebra programming language.
The Catalan numbers Cn =(2n)!/n!(n + 1)! are are well-known integers that arise in many combinatorial problems. The numbers 6(2n)!/n!(n + 2)!, 60(2n)!/n!(n + 3)!, and more generally (2r + 1)!/r! ·...
Introduction. Awell-known algorithm for coloring the vertices of a graph is the “greedy algorithm”: given a totally ordered set of colors, each vertex of the graph (taken in some order) is...
Determinants, Paths, and Plane Partitions (1989)
Introduction In studying representability of matroids, Lindstrom [42] gave a combinatorial interpretation to certain determinants in terms of disjoint paths in digraphs. In a previous paper [25], the...
Generalized rook polynomials and orthogonal polynomials (1989)
Abstract. We consider several generalizations of rook polynomials. In particular we develop analogs of the theory of rook polynomials that are related to general Laguerre and Charlier polynomials in...
Enumerative Applications Of Symmetric Functions (1987)
This paper consists of two related parts. In the first part the theory of D-finite power series in several variables and the theory of symmetric functions are used to prove P-recursiveness for...
Enumerative applications of symmetric functions (1987)
first part the theory of D-finite power series in several variables and the theory of symmetric functions are used to prove P-recursiveness for regular graphs and digraphs and related objects, that...
Counting three-line Latin rectangles (1985)
A k × n Latin rectangle is a k × n array of numbers such that (i) each row is a permutation of [n] ={1, 2,...,n} and (ii) each column contains distinct entries. If the first row is 12 ···n, the...