A combinatorial interpretation of the recurrence fn+1 = 6fn − fn−1

Bonin et al. (1993) recalled an open problem related to the recurrence relation verified by NSW numbers. The recurrence relation is the following: f_n+1 = 6f_n − f_n−1, with f₁ = 1 and f₂ = 7, and no combinatorial interpretation seems to be known. In this note, we define a regular language L whose number of words having length n is equal to f_n+1. Then, by using L we give a direct combinatorial proof of the recurrence.     

Riordan paths and derangements

Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and -avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schröder numbers.     

On a Formula for the Kostka Numbers

From Kostant’s multiplicity formula for general linear groups, one can derive a formula for the Kostka numbers. In this note we give a combinatorial proof of this formula. Received January 7, 2005     

Bit strings withoutq-separation

LetB(n, q) denote the number of bit strings of lengthn withoutq-separation. In a bit string withoutq-separation no two 1's are separated by exactlyq – 1 bits.B(n, q) is known to be expressible in terms of a product of powers of Fibonacci numbers. Two new and independent proofs are given. The first proof is by combinatorial enumeration, while the second proof is inductive and expressesB(n, q) in terms of a recurrence relation.     

Simplicial trees are sequentially Cohen–Macaulay

This paper uses dualities between facet ideal theory and Stanley–Reisner theory to show that the facet ideal of a simplicial tree is sequentially Cohen–Macaulay. The proof involves showing that the Alexander dual (or the cover dual, as we call it here) of a simplicial tree is a componentwise linear ideal. We conclude with additional combinatorial properties of simplicial trees.     

The multidimensional cube recurrence

We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky, Speyer, and Fock and Goncharov and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips. We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians IG(n−1,2n). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.     

Jumping coefficients and spectrum of a hyperplane arrangement

In an earlier version of this paper written by the second named author, we showed that the jumping coefficients of a hyperplane arrangement depend only on the combinatorial data of the arrangement as conjectured by Mustaţǎ. For this we proved a similar assertion on the spectrum. After this first proof was written, the first named author found a more conceptual proof using the Hirzebruch–Riemann–Roch theorem where the assertion on the jumping numbers was proved without reducing to that for the spectrum. In this paper we improve these methods and show that the jumping numbers and the spectrum are calculable in low dimensions without using a computer. In the reduced case we show that these depend only on fewer combinatorial data, and give completely explicit combinatorial formulas for the jumping coefficients and (part of) the spectrum in the case the ambient dimension is 3 or 4. We also give an analogue of Mustaţǎ’s formula for the spectrum.     

Book Review

Many linear recurrence relations for combinatorial numbers depending on two indices – like, e.g. the Stirling numbers – can be transformed into a sequence of linear differential equations (of first order) for the corresponding generating functions. In this paper, the most general sequence of such differential equations is considered where the coefficient functions are assumed to be analytic. Using an Ansatz of factoring the sought-for solution into the product of two functions each satisfying a particular associated differential equation, an explicit solution is derived. Some concrete examples are treated. Furthermore, first results for sequences of linear differential equations of second-order are presented and the difficulties of treating the higher order case within the above mentioned method are discussed.     

Combinatorial numbers in binary recurrences

We give several effective and explicit results concerning the values of some polynomials in binary recurrence sequences. First we provide an effective finiteness theorem for certain combinatorial numbers (binomial coefficients, products of consecutive integers, power sums, alternating power sums) in binary recurrence sequences, under some assumptions. We also give an efficient algorithm (based on genus 1 curves) for determining the values of certain degree 4 polynomials in such sequences. Finally, partly by the help of this algorithm we completely determine all combinatorial numbers of the above type for the small values of the parameter involved in the Fibonacci, Lucas, Pell and associated Pell sequences.      

Divided Differences and Combinatorial Identities

We present an algebraic theory of divided differences which includes confluent differences, interpolation formulas, Liebniz's rule, the chain rule, and Lagrange inversion. Our approach uses only basic linear algebra. We also show that the general results about divided differences yield interesting combinatorial identities when we consider some suitable particular cases. For example, the chain rule gives us generalizations of the identity used by Good in his famous proof of Dyson's conjecture. We also obtain identities involving binomial coefficients, Stirling numbers, Gaussian coefficients, and harmonic numbers.     

Partially 2-colored permutations and the Boros–Moll polynomials

We find a combinatorial setting for the coefficients of the Boros–Moll polynomials P _m (a) in terms of partially 2-colored permutations. Using this model, we give a combinatorial proof of a recurrence relation on the coefficients of P _m (a). This approach enables us to give a combinatorial interpretation of the log-concavity of P _m (a) which was conjectured by Moll and confirmed by Kauers and Paule.     

Combinatorial characterizations of K-matrices

e present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Pták on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that any simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.     

The Legendre–Stirling numbers

The Legendre–Stirling numbers are the coefficients in the integral Lagrangian symmetric powers of the classical Legendre second-order differential expression. In many ways, these numbers mimic the classical Stirling numbers of the second kind which play a similar role in the integral powers of the classical second-order Laguerre differential expression. In a recent paper, Andrews and Littlejohn gave a combinatorial interpretation of the Legendre–Stirling numbers. In this paper, we establish several properties of the Legendre–Stirling numbers; as with the Stirling numbers of the second kind, they have interesting generating functions and recurrence relations. Moreover, there are some surprising and intriguing results relating these numbers to some classical results in algebraic number theory.     

Combinatorial telescoping for an identity of Andrews on parity in partitions

Recently Andrews proposed a problem of finding a combinatorial proof of an identity on the q-little Jacobi polynomials. We give a classification of certain triples of partitions and find bijections based on this classification. By the method of combinatorial telescoping for identities on sums of positive terms, we establish a recurrence relation that leads to the identity of Andrews.     

A Proof of the Murnaghan–Nakayama Rule Using Specht Modules and Tableau Combinatorics

Annals of Combinatorics - The Murnaghan–Nakayama rule is a combinatorial rule for the character values of symmetric groups. We give a new combinatorial proof by explicitly finding the trace...     

Enumeration via ballot numbers

Several interesting combinatorial coefficients such as the Catalan numbers and the Bell numbers can be described either via a 3-term recurrence or as sums of (weighted) ballot numbers. This paper gives some general results connecting 3-term recurrences with ballot sequences with several applications to the enumeration of various combinatorial instances.     

Touchard–Riordan formulas, T-fractions, and Jacobi’s triple product identity

Touchard–Riordan-like formulas are certain expressions appearing in enumeration problems and as moments of orthogonal polynomials. We begin this article with a new combinatorial approach to prove such formulas, related to integer partitions. This gives a new perspective on the original result of Touchard and Riordan. But the main goal is to give a combinatorial proof of a Touchard–Riordan-like formula for q-secant numbers discovered by the first author. An interesting limit case of these objects can be directly interpreted in terms of partitions, so that we obtain a connection between the formula for q-secant numbers, and a particular case of Jacobi’s triple product identity. Building on this particular case, we obtain a “finite version” of the triple product identity. It is in the form of a finite sum which is given a combinatorial meaning, so that the triple product identity can be obtained by taking the limit. Here the proof is non-combinatorial and relies on a functional equation satisfied by a T-fraction. Then from this result on the triple product identity, we derive a whole new family of Touchard–Riordan-like formulas whose combinatorics is not yet understood. Eventually, we prove a Touchard–Riordan-like formula for a q-analog of Genocchi numbers, which is related with Jacobi’s identity for (q;q)³ rather than the triple product identity.     

A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

Context-free grammars for triangular arrays

We consider context-free grammars of the form G = {f → fb1+b2+1ga1+a2, g → fb1 ga1+1},where ai and bi are integers sub ject to certain positivity conditions. Such a grammar G gives rise to triangular arrays {T(n, k)}0≤k≤n satisfying a three-term recurrence relation. Many combinatorial sequences can be generated in this way. Let Tn (x) =∑nk=0T(n, k)xk. Based on the differential operator with respect to G, we define a sequence of linear operators Pn such that Tn+1(x) = Pn(Tn(x)). Applying the characterization of real stability preserving linear operators on the multivariate polynomials due to Borcea and Br?ndén, we obtain a necessary and sufficient condition for the operator Pn to be real stability preserving for any n. As a consequence, we are led to a sufficient condition for the real-rootedness of the polynomials defined by certain triangular arrays, obtained by Wang and Yeh.Moreover, as special cases we obtain grammars that lead to identities involving the Whitney numbers and the Bessel numbers.     

Investigating undergraduate students’ proof schemes and perspectives about combinatorial proof

Combinatorics is an area of mathematics with accessible, rich problems and applications in a variety of fields. Combinatorial proof is an important topic within combinatorics that has received relatively little attention within the mathematics education community, and there is much to investigate about how students reason about and engage with combinatorial proof. In this paper, we use Harel and Sowder’s (1998) proof schemes to investigate ways that students may characterize combinatorial proofs as different from other types of proof. We gave five upper-division mathematics students combinatorial-proof tasks and asked them to reflect on their activity and combinatorial proof more generally. We found that the students used several of Harel and Sowder’s proof schemes to characterize combinatorial proof, and we discuss whether and how other proof schemes may emerge for students engaging in combinatorial proof. We conclude by discussing implications and avenues for future research.