Guten Tag,
ich hab da mal n kleines problem mit ner aufgabe:
Seien k, n und r elemnt der nat. zahlen.
Bestimmen Sie die Anzahl der k-elementigen Teilmengen S von {1, . . . , n}, deren Elemente alle voneinander einen Abstand größer als r habe (d. h. für alle i, j element S gilt |j − i| > r).
wie muss ich da ran gehen, in welche richtung sollte die lsg. aussehen?
ich hab echt keinen plan, also bitte helft mir…
Seien k, n und r elemnt der nat. zahlen.
Bestimmen Sie die Anzahl der k-elementigen Teilmengen S von
{1, . . . , n}, deren Elemente alle voneinander einen Abstand
größer als r habe (d. h. für alle i, j element S gilt |j − i|
> r).
folgende Ideen:
Sei S_n die Menge {1, . . . , n} und A_r_k = die Anzahl der k-elementigen Teilmengen S_n. Dann:
je kleiner n und je größer k und r, desto weniger Mengen gibt es.
insb. folgt aus 1), dass A_r_k=0 falls r>n oder k>n
Für r=1 und k=n ist die Lösung trivial
sei X_k_r eine k-elementige Teilmenge von S_n, so das gilt: max(X)=max(S_n)-k*r. Sei f: X->S_n mit (x_1,…,x_k) -> (x_1,x_2+r,…,x_k+k*r). Dann ist f(X_k_r) eine Teilmengr von S_n mit den gwünschten Eigenschaften.
Jetzt musst du nur noch überlegen, wieviele solche Mengen X_k_r es gibt.