Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 070.01101
Autor: Erdös, Pál; Rényi, Alfréd
Title: On some combinatorial problems. (In English)
Source: Publ. Math., Debrecen 4, 398-405 (1956).
Review: Un système (k,n) est un ensemble contenant Ck(n) combinaisons, avec répétition, e n éléments distincts k à k, telles que deux éléments quelconques figurent dans une combinaison au moins (k,n = 2,3,...). Le système (k,n) est optime si (1) Ck (n) = n(n-1)/ [k(k-1)]. Dans le cas général, le premier membre est plus grand que le second. Un système (k,n) optime est aussi un balanced incomplete block design [Cf. K.R.Nair, Sankhya 6, 255-259 (1943; Zbl 060.34105)] de n variétés réparties en b = n(n-1)/[k(k-1)] blocs de k éléments et où toute paire de variétés apparait une fois dans un seul bloc. Théorème I: Si: k = p\alpha = Cte,(p premier) la limite de Ck(n)/[n(n-1)] pour n infinie est 1/[k(k-1)]. Théorème II: Dans un papier précédent [Mat. Lapok 6, 151-163 (1955)] Alfred Rényi avait conjecturé que, en désignant par Dk(n) la longueur de la séquence la plus courte formée avec les éléments 1,2,3,...n, dans laquelle deux éléments quelconques i,j (1 \leq i < j \leq n) figurent au moins une fois dans une position telle qu'ils soient séparés par au plus k nombres, Dk(n)/n2 avait une limite pour n infini quelque fût k = 2,3,.... Pour k = 2 ou 3, la limite est 1/[2(k-1)]. L'existence de cette limite est ici démontrée pour toute valeur de k. La preuve utilise un lemme de T. Szele [Mat. Fiz. Lapok 50, 223-256 (1943; Zbl 061.41309)].
Reviewer: A.Sade
Classif.: * 05B05 Block designs (combinatorics)
00A07 Problem books
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag