Generalized Pascal triangles. Decidability results. (English) Zbl 0607.05002

Korec, Ivan

Acta Math. Univ. Comenianae 46-47, 93-130 (1985).

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

Keywords:

Generalized Pascal triangles