Moments of combinatorial and Catalan numbers

In this paper we obtain the moments {Φm}_m?0 defined by

     

Shortened recurrence relations for Bernoulli numbers

Starting with two little-known results of Saalschütz, we derive a number of general recurrence relations for Bernoulli numbers. These relations involve an arbitrarily small number of terms and have Stirling numbers of both kinds as coefficients. As special cases we obtain explicit formulas for Bernoulli numbers, as well as several known identities.     

A general two-term recurrence

We give a short proof of a recent result of Mansour et al. (2012) [1] concerning the recurrence u(n,k)=u(n−1,k−1)+(_an−1+_bk)u(n−1,k)$u(n,k)=u(n-1,k-1)+(a_{n-1}+b_k)u(n-1,k)$.     

New identities in the Catalan triangle

In this paper we prove new identities in the Catalan triangle whose (n,p) entry is defined by

     

Identities for generalized Fibonacci numbers: a combinatorial approach

This note shows a combinatorial approach to some identities for generalized Fibonacci numbers. While it is a straightforward task to prove these identities with induction, and also by arithmetical manipulations such as rearrangements, the approach used here is quite simple to follow and eventually reduces the proof to a counting problem.     

Sums of powers of Catalan triangle numbers

In this paper, we consider combinatorial numbers ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$, mentioned as Catalan triangle numbers where $C_{m,k}?\left(\genfrac{}{}{0ex}{}{m?1}{k}\right)?\left(\genfrac{}{}{0ex}{}{m?1}{k?1}\right)$. These numbers unify the entries of the Catalan triangles $B_{n,k}$ and $A_{n,k}$ for appropriate values of parameters $m$ and $k$, i.e., $B_{n,k}=C_{2n,n?k}$ and $A_{n,k}=C_{2n+1,n+1?k}$. In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers $C_n$ that is $C_{2n,n?1}=C_{2n+1,n}=C_n$.We present identities for sums (and alternating sums) of $C_{m,k}$, squares and cubes of $C_{m,k}$ and, consequently, for $B_{n,k}$ and $A_{n,k}$. In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$ and harmonic numbers ${\left(H_n\right)}_{n\ge 1}$. Finally, in the last section, new open problems and identities involving ${\left(C_n\right)}_{n\ge 0}$ are conjectured.     

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.     

A combinatorial proof of associativity of Ore extensions

We use a counting argument to show that Ore extensions are associative.     

A general two-term recurrence and its solution

We find a general explicit formula for all sequences satisfying a two-term recurrence of a certain kind. This generalizes familiar formulas for the Stirling and Lah numbers.     

A combinatorial approach to cartograms

A homeomorphism from ² to itself distorts metric quantities, such as distance and area. We describe an algorithm that constructs homeomorphisms with prescribed area distortion. Such homeomorphisms can be used to generate cartograms, which are geographic maps purposely distorted so their area distributions reflects a variable different from area, as for example population density. The algorithm generates the homeomorphism through a sequence of local piecewise linear homeomorphic changes. Sample results produced by the preliminary implementation of the method are included.     

On recurrences for sums of powers of binomial coefficients

The recurrence for sums of powers of binomial coefficients is considered and a lower bound for the minimal length of the recurrence is obtained by using the properties of congruence.

Video abstract

For a video summary of this paper, please visit http://www.youtube.com/watch?v=jwy6B4aYR-Q.     

Combinatorial sums and finite differences

We present a new approach to evaluating combinatorial sums by using finite differences. Let and be sequences with the property that Δb_k=a_k for k?0. Let , and let . We derive expressions for g_n in terms of h_n and for h_n in terms of g_n. We then extend our approach to handle binomial sums of the form , , and , as well as sums involving unsigned and signed Stirling numbers of the first kind, and . For each type of sum we illustrate our methods by deriving an expression for the power sum, with a_k=k^m, and the harmonic number sum, with a_k=H_k=1+1/2+?+1/k. Then we generalize our approach to a class of numbers satisfying a particular type of recurrence relation. This class includes the binomial coefficients and the unsigned Stirling numbers of the first kind.     

Regular-SAT: A many-valued approach to solving combinatorial problems

Regular-SAT is a constraint programming language between CSP and SAT that—by combining many of the good properties of each paradigm—offers a good compromise between performance and expressive power. Its similarity to SAT allows us to define a uniform encoding formalism, to extend existing SAT algorithms to Regular-SAT without incurring excessive overhead in terms of computational cost, and to identify phase transition phenomena in randomly generated instances. On the other hand, Regular-SAT inherits from CSP more compact and natural encodings that maintain more the structure of the original problem. Our experimental results—using a range of benchmark problems—provide evidence that Regular-SAT offers practical computational advantages for solving combinatorial problems.     

Computation methods for combinatorial sums and Euler‐type numbers related to new families of numbers

The aim of this article is to define some new families of the special numbers. These numbers provide some further motivation for computation of combinatorial sums involving binomial coefficients and the Euler kind numbers of negative order. We can show that these numbers are related to the well‐known numbers and polynomials such as the Stirling numbers of the second kind and the central factorial numbers, the array polynomials, the rook numbers and polynomials, the Bernstein basis functions and others. In order to derive our new identities and relations for these numbers, we use a technique including the generating functions and functional equations. Finally, we give not only a computational algorithm for these numbers but also some numerical values of these numbers and the Euler numbers of negative order with tables. We also give some combinatorial interpretations of our new numbers. Copyright © 2016 John Wiley & Sons, Ltd.     

A combinatorial proof of a theorem of Freund

In 1989, Robert W. Freund published an article about generalizations of the Sperner lemma for triangulations of n-dimensional polytopes, when the vertices of the triangulations are labeled with points of Rn. For y∈Rn, the generalizations ensure, under various conditions, that there is at least one simplex containing y in the convex hull of its labels. Moreover, if y is generic, there is generally a parity assertion, which states that there is actually an odd number of such simplices.For one of these generalizations, contrary to the others, neither a combinatorial proof, nor the parity assertion were established. Freund asked whether a corresponding parity assertion could be true and proved combinatorially.The aim of this paper is to give a positive answer, using a technique which can be applied successfully to prove several results of this type in a very simple way. We prove actually a more general version of this theorem. This more general version was published by van der Laan, Talman and Yang in 2001, who proved it in a non-combinatorial way, without the parity assertion.     

p-Catalan numbers and squarefree binomial coefficients

In this paper, we consider the generalized Catalan numbers , which we call s-Catalan numbers. For p prime, we find all positive integers n such that p^q divides F(p^q,n), and also determine all distinct residues of , q?1. As a byproduct we settle a question of Hough and the late Simion on the divisibility of the 4-Catalan numbers by 4. In the second part of the paper we prove that if pq?99999, then is not squarefree for n?τ₁(p^q) sufficiently large (τ₁(p^q) computable). Moreover, using the results of the first part, we find n<τ₁(p^q) (in base p), for which may be squarefree. As consequences, we obtain that is squarefree only for n=1,3,45, and is squarefree only for n=1,4,10.     

Generalized Bessel numbers and some combinatorial settings

Stirling numbers and Bessel numbers have a long history, and both have been generalized in a variety of directions. Here, we present a second level generalization that has both as special cases. This generalization often preserves the inverse relation between the first and second kind, and has simple combinatorial interpretations. We also frame the discussion in terms of the exponential Riordan group. Then the inverse relation is just the group inverse, and factoring inside the group leads to many results connecting the various Stirling and Bessel numbers.