Pascal's triangle, complexity and automata
type: Item
instance of: scholarly article
title: Pascal's triangle, complexity and automata
zbMATH Open document ID: 0922.11012
author: Jean-Paul Allouche
author: Valérie Berthé
published in: Bulletin of the Belgian Mathematical Society - Simon Stevin
publication date: 1999-03-14T00:00:00Z
full work available at URL: https://eudml.org/doc/119948
review text: The aim of this paper is to study the double sequence \( s_{n,m}= \binom {n}{m} \) mod \( d\). Actually it is mainly concerned with the number \( P_{d}(u,v) \) of distinct \( u\times v \) sized rectangular blocks contained in the infinite matrix \( (s_{n,m})\). Firstly \( P_{d}(u,v) \) is proved to be multiplicative : namely, for relatively prime integers \( d_{1} \) and \( d_{2} \) one has \( P_{d_{1}d_{2}}(u,v) =P_{d_{1}}(u,v) P_{d_{2}}(u,v)\). Then, for any prime number \( d\), rather explicit formulas are given for \( P_{d}(1,v) \) hence for \( P_{d}(u,v)\). For \( d=2 \) the result is particularly explicit and simple. In the general case, let \(\omega\) denote the number of distinct prime factors of \( d\), the main result of the paper is the existence of constants \( 0<A<B \) such that \( A \sup(u,v)^{2\omega}\leq P_{d}(u,v)\leq B \sup(u,v)^{2\omega}\). In particular one recovers that the sequence \( s_{n,m} \) is automatic if and only if \( \omega=1 \) (i.e. if \( d \) is a power of a prime number). Reading this article is pleasant : proofs are explicitly written and main results come with comments on connected topics.
reviewed by: Gilles Christol
Mathematics Subject Classification ID: 11B65
Mathematics Subject Classification ID: 11B85
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 11B50
zbMATH DE Number: 1260651
zbMATH Keywords: finite automata
zbMATH Keywords: cellular automata
zbMATH Keywords: complexity of infinite sequences
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1260651