×

zbMATH — the first resource for mathematics

Generalized Pascal triangles. Decidability results. (English) Zbl 0607.05002
Generalized Pascal triangles (GPT) are created analogously as the usual Pascal triangle is. However, instead of the addition on the set N of nonnegative integers an arbitrary binary operation on a set A is used. Moreover, the left and the right margins need not be constant but they are formed by using two unary operations on A, and the top is replaced by a finite sequence of elements of A. Even if only finite sets A are considered some questions about GPT are algorithmically unsolvable. For example, it is undecidable whether an element \(\alpha\in A\) occurs in a given GPT, or whether x occurs there infinitely many times. These problems are proved to be solvable in some special cases. It is so e.g. if the set of rows of a GPT is a semilinear language or if the left and the right margins are constant and the binary operation is addition modulo a prime or if A consists of at most two elements.

MSC:
05A10 Factorials, binomial coefficients, combinatorial functions
05A99 Enumerative combinatorics
PDF BibTeX XML Cite