Generalized Path Pairs and Fuss-Catalan Triangles

zbMATH Open1470.05032arXiv2007.01892MaRDI QIDQ5000295FDOQ5000295

Publication date: 12 July 2021

Abstract: Path pairs are a modification of parallelogram polyominoes that provide yet another combinatorial interpretation of the Catalan numbers. More generally, the number of path pairs of length

n

and distance

d e l t a

corresponds to the

(n - 1, d e l t a - 1)

entry of Shapiro's so-called Catalan triangle. In this paper, we widen the notion of path pairs

(g a m m a_{1}, g a m m a_{2})

to the situation where

g a m m a_{1}

and

g a m m a_{2}

may have different lengths, and then enforce divisibility conditions on runs of vertical steps in

g a m m a_{2}

. This creates a two-parameter family of integer triangles that generalize the Catalan triangle and qualify as proper Riordan arrays for many choices of parameters. In particular, we use generalized path pairs to provide a new combinatorial interpretation for all entries in every proper Riordan array

m a t h c a l R (d (t), h (t))

of the form

d (t) = C_{k} (t)^{i}

,

h (t) = t k e r n + 1 p t C_{k} (t)^{k}

, where

1 l e q i l e q k

and

C_{k} (t)

is the generating function for some sequence of Fuss-Catalan numbers (some

k g e q 2

). Closed formulas are then provided for the number of generalized path pairs across an even broader range of parameters, as well as for the number of weak path pairs with a fixed number of non-initial intersections.

Full work available at URL: https://arxiv.org/abs/2007.01892

Recommendations

zbMATH Keywords

Riordan arrays Fuss-Catalan numbers path pairs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Polyominoes (05B50)

Cites Work

Cited In (3)

This page was built for publication: Generalized Path Pairs and Fuss-Catalan Triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000295)