Elemente der Mathematik
- 1 :
- 2 :
- 3 :
- 4 :
- 5 : 1
- 6 : 2
- 7 : 3
- 8 : 4
- 9 : 5
- 10 : 6
- 11 : 7
- 12 : 8
- 13 : 9
- 14 : 10
- 15 : 11
- 16 : 12
- 17 : 13
- 18 : 14
- 19 : 15
- 20 : 16
- 21 : 17
- 22 : 18
- 23 : 19
- 24 : 20
- 25 : 21
- 26 : 22
- 27 : 23
- 28 : 24
- 29 : 25
- 30 : 26
- 31 : 27
- 32 : 28
- 33 : 29
- 34 : 30
- 35 : 31
- 36 : 32
- 37 : 33
- 38 : 34
- 39 : 35
- 40 : 36
- 41 : 37
- 42 : 38
- 43 : 39
- 44 : 40
- 45 : 41
- 46 : 42
- 47 : 43
- 48 : 44
- 49 : 45
- 50 : 46
- 51 : 47
- 52 : 48
- 53 : 49
- 54 : 50
- 55 : 51
- 56 : 52
- 57 : 53
- 58 : 54
- 59 : 55
- 60 : 56
- 61 : 57
- 62 : 58
- 63 : 59
- 64 : 60
- 65 : 61
- 66 : 62
- 67 : 63
- 68 : 64
- 69 : 65
- 70 : 66
- 71 : 67
- 72 : 68
- 73 : 69
- 74 : 70
- 75 : 71
- 76 : 72
- 77 : 73
- 78 : 74
- 79 : 75
- 80 : 76
- 81 : 77
- 82 : 78
- 83 : 79
- 84 : 80
- 85 : 81
- 86 : 82
- 87 : 83
- 88 : 84
- 89 : 85
- 90 : 86
- 91 : 87
- 92 : 88
- 93 : 89
- 94 : 90
- 95 : 91
- 96 : 92
- 97 : 93
- 98 : 94
- 99 : 95
- 100 : 96
- 101 : 97
- 102 : 98
- 103 : 99
- 104 : 100
- 105 : 101
- 106 : 102
- 107 : 103
- 108 : 104
- 109 : 105
- 110 : 106
- 111 : 107
- 112 : 108
- 113 : 109
- 114 : 110
- 115 : 111
- 116 : 112
- 117 : 113
- 118 : 114
- 119 : 115
- 120 : 116
- 121 : 117
- 122 : 118
- 123 : 119
- 124 : 120
- 125 : 121
- 126 : 122
- 127 : 123
- 128 : 124
- 129 : 125
- 130 : 126
- 131 : 127
- 132 : 128
- 133 : 129
- 134 : 130
- 135 : 131
- 136 : 132
- 137 : 133
- 138 : 134
- 139 : 135
- 140 : 136
- 141 : 137
- 142 : 138
- 143 : 139
- 144 : 140
- 145 : 141
- 146 : 142
- 147 : 143
- 148 : 144
Scan
Volltext
Seite 137 : 133
Kieme Mitteilungen
133
fe - Tuples of the First n Natural Numbers
In connection with the problems of infinite sets investigated by Erdos and Hajnal m [1], Erdos proposed a problem of the Ä-tuples of a finite set. This problem m its most general form can be formulated as follows Take a system of Ä-tuples of the first n natural numbers Suppose that the set of the i^-st, tg-nd, . . , г^-th (/< Â — 1) numbers of an trary /г-tupie of the system does not coincide with the set of the /i-st, ]2~^^> • • • » U~^^ numbers of another Ä-tupie of the system. At most how many Â-tuples can the system contain ? In this paper we solve the problem m a special case.
Denote by / {n, k) the maximal number of Ä-tuples which can be chosen from the first n numbers (1 < Ä < n) such that the last k — 1 numbers of a Ä-tuple do not coincide with the first k — 1 numbers of another selected Ä-tuple.
It IS trivial that f{n, 1) = n.
It will be proved that if Ä > 2 then
, , ,, v" (n-l-2m\
f { n . k ) = 2; k-1 )■
The proof uses induction onn. li n = k, f [k, k) = 1 li n — k -\- 1, only the Ä-tuple of the first and the Ä-tuple of the last k numbers cannot be selected at the same time, consequently f(k-\-l,k)=^k Thus the statement holds for n ~ k, k -\- 1, and it may be supposed that n > k + 2 and it holds for the numbers less than n.
Put N = {1, 2, ... , n) and M = {2, 3, . . ,n — 1). Consider a maximal system 9^ of Ä-tuples of N, satisfying the condition. Denote by л; a [k — 2)-tuple, x с N and x с M will mean that the elements of н are m N and M, respectively. Divide the {k — 1)-tu pies of N into two classes ^ and 5B. If a (Â; — 1)-tuple consists of the first k — 1 elements of a Ä-tuple of 9^, then put the {k — 1)-tupie into %, otherwise into S. Denote by cil{x) the number of (k ~ 1)-tuples of ^, the last k — 2 elements of which form x, and similarly ß(H) denotes the number of (k — 1)-tuples of 58, the first k — 2 elements of which form x. Because of the maximality oi ^ li x consists of the last k — 2 elements of a (^ — 1)-tuple of Щ and it IS at the same time the set of the first к — 2 elements of a (Ä — 1)-tuple of Ъ, then ?l contains the Ä-tuple which is the union of these two {k — 1)-tuples It is obvious that this IS a unique representation of the elements of 9^1 as certain unions of elements of Ш and Ф. Consequently
f ( n , k ) =2Ja { x ) ß { x ) .
xcN
If X contains 1, ol{x) = 0 and if x contains n, ß(x) = 0. Thus it can be supposed that X с M m the sum above. On the other hand li x с M, the (k — 1)-tuple consisting of 1 and of the elements of x must belong to % So if a'(«) denotes the number of {k ~ 1)-tuples of 41 m M, having x as the 1st Ä; — 2 elements, then (x{x) = ol'(x) -f- 1. The number ß'{x) is defined similarly and ß(x) = ß'(x) -f- 1. But then
f ( n , k) ^2Joc(x) ß(x) =2J(ol'(x) + 1) (ГМ + 1)
xQM hQM
= y«.'(x) /3» + X'KM + /*'M) +2*1 < /(" - 2. Ä) + ( ь I ? ) нам кем "CM ^ '
Seiten
Export
Einzelbilder herunterladen
Bilddaten
Info
Titel
Metadaten
Übergeordnetes Werk
Jahr
Digitalisierungsdatum
Verlag
Sprache
Bereitgestellt von
Hilfe
Über TIFY
TIFY ist ein schlanker und für Mobilgeräte optimierter IIIF-Dokumentenbetrachter, veröffentlicht unter der GNU Affero General Public License 3.0.