Combinatorial proofs of the Newton–Girard and Chapman–Costas-Santos identities

In this paper we give combinatorial proofs of some well known identities and obtain some generalizations. We give a visual proof of a result of Chapman and Costas-Santos regarding the determinant of sum of matrices. Also we find a new identity expressing the permanent of sum of matrices. Besides, we give a graph theoretic proof of the Newton–Girard identity in a generalized form.     

Unimodular polynomial matrices over finite fields

Journal of Algebraic Combinatorics - We consider some combinatorial problems on matrix polynomials over finite fields. Using results from control theory, we give a proof of a result of Lieb, Jordan...     

Combinatorial proofs and generalizations of conjectures related to Euler’s partition theorem

In a recent work, Andrews gave analytic proofs of two conjectures concerning some variations of two combinatorial identities between partitions of a positive integer into odd parts and partitions into distinct parts discovered by Beck. Subsequently, using the same method as Andrews, Chern presented the analytic proof of another Beck’s conjecture relating the gap-free partitions and distinct partitions with odd length. However, the combinatorial interpretations of these conjectures are still unclear and required. In this paper, motivated by Glaisher’s bijection, we give the combinatorial proofs of these three conjectures directly or by proving more generalized results.     

On injectivity of the combinatorial Radon transform of order five

In the present work, we give a proof of the injectivity of the combinatorial Radon transform of order five.     

A Translation Method for Finding Combinatorial Bijections

Consider a combinatorial identity that can be proved by induction. In this paper, we describe a general method for translating the inductive proof into a recursive bijection. Furthermore, we will demonstrate that the resulting recursive bijection can often be defined in a direct, non-recursive way. Thus, the translation method often results in a bijective proof of the identity that helps illuminate the underlying combinatorial structures. This paper has two main parts: First, we describe the translation method and the accompanying Maple code; and second, we give a few examples of how the method has been used to discover new bijections.     

A short note on the overpartition function

In this brief note, we give a combinatorial proof of a variation of Gauss’s q-binomial theorem, and we determine arithmetic properties of the overpartition function modulo 8.     

On Some Combinatorial Result in the Theory of Automorphic Pseudo-differential Operators

We give short elementary proof of some combinatorial result in the theory of automorphic pseudodifferential operators.     

Minimalist designs

The iterative absorption method has recently led to major progress in the area of (hyper‐)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle‐divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi‐random host graphs.     

Refinements of the results on partitions and overpartitions with bounded part differences

Recently, partitions with fixed or bounded differences between largest and smallest parts have attracted a lot of attention. In this paper, we first give a simple combinatorial proof of Breuer and Kronholm’s identity. Inspired by it, we construct a useful bijection to produce refinements of the results for partitions and overpartitions with bounded differences between largest and smallest parts. Consequently, we obtain Chern’s curious identity in a combinatorial manner.     

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     

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.     

On the subset sum problem for finite fields

Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.     

Crystal interpretation of Kerov–Kirillov–Reshetikhin bijection II. Proof for $\mathfrak{sl}_{n}$ case

In proving the Fermionic formulae, a combinatorial bijection called the Kerov–Kirillov–Reshetikhin (KKR) bijection plays the central role. It is a bijection between the set of highest paths and the set of rigged configurations. In this paper, we give a proof of crystal theoretic reformulation of the KKR bijection. It is the main claim of Part I written by A. Kuniba, M. Okado, T. Takagi, Y. Yamada, and the author. The proof is given by introducing a structure of affine combinatorial R matrices on rigged configurations.     

Bijective proofs using two-line matrix representations for partitions

In this paper, we present bijective proofs of several identities involving partitions by making use of a new way for representing partitions as two-line matrices. We also apply these ideas to give a combinatorial proof for an identity related to three-quadrant Ferrers graphs.     

Multiple extensions of a finite Euler's pentagonal number theorem and the Lucas formulas

Motivated by the resemblance of a multivariate series identity and a finite analogue of Euler's pentagonal number theorem, we study multiple extensions of the latter formula. In a different direction we derive a common extension of this multivariate series identity and two formulas of Lucas. Finally we give a combinatorial proof of Lucas’ formulas.     

Abelian groups with layered tiles and the sumset phenomenon

We prove a generalization of the main theorem in Jin, The sumset phenomenon, about the sumset phenomenon in the setting of an abelian group with layered tiles of cell measures. Then we give some applications of the theorem for multi-dimensional cases of the sumset phenomenon. Several examples are given in order to show that the applications obtained are not vacuous and cannot be improved in various directions. We also give a new proof of Shnirel'man's theorem to illustrate a different approach (which uses the sumset phenomenon) to some combinatorial problems.

     

The Flagged Cauchy Determinant

We consider a flagged form of the Cauchy determinant, for which we provide a combinatorial interpretation in terms of nonintersecting lattice paths. In combination with the standard determinant for the enumeration of nonintersecting lattice paths, we are able to give a new proof of the Cauchy identity for Schur functions. Moreover, by choosing different starting and end points for the lattice paths, we are led to a lattice path proof of an identity of Gessel which expresses a Cauchy-like sum of Schur functions in terms of the complete symmetric functions.     

Counting partitions on the abacus

In 2003, Maróti showed that one could use the machinery of ℓ-cores and ℓ-quotients of partitions to establish lower bounds for p(n), the number of partitions of n. In this paper we explore these ideas in the case ℓ=2, using them to give a largely combinatorial proof of an effective upper bound on p(n), and to prove asymptotic formulae for the number of self-conjugate partitions, and the number of partitions with distinct parts. In a further application we give a combinatorial proof of an identity originally due to Gauss. Dedicated to the memory of Dr. Manfred Schocker (1970–2006)     

Free Cumulants and Enumeration of Connected Partitions

A combinatorial formula is derived which expresses free cumulants in terms of classical cumulants. As a corollary, we give a combinatorial interpretation of free cumulants of classical distributions, notably Gaussian and Poisson distributions. The latter count connected pairings and connected partitions, respectively. The proof relies on Möbius inversion on the partition lattice.     

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.