Anwendung der doppelten Abz. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei j [mm] \in \mathbb [/mm] N und bezeichne t(j) die Anzahl der Teiler von j. Bezeichne weiters t´(n) die durchschnittliche Anzahl der Teiler der Zahlen von 1 bis n, also
t´(n):= [mm] \bruch{1}{n}*\summe_{i=1}^{n}t(i).
[/mm]
Zeige:
t´(n):= [mm] \bruch{1}{n}*\summe_{i=1}^{n}\lfloor \bruch{n}{i} \rfloor
[/mm]
(Dies ist eine Anwendung der Regel von der doppelten Abzählung) |
Ich habe in meinem Skriptum die Regel v. der doppelten Abzählung wiefolgt definiert:
Seien zwei endliche Mengen S,T gegeben, und sei ~ eine Relation zwischen S und T. Für jedes s [mm] \in [/mm] S bezeichne r(s) die Anzahl der Elemente t [mm] \in [/mm] T, für die s~t gilt; und ebenso bezeichne r(t) für jedes t [mm] \in [/mm] T die Anzahl der Elemente [mm] s\in [/mm] S, für die s~t gilt. Dann gilt:
[mm] \summe_{s \in S}r(s) [/mm] = [mm] \summe_{t \in T}r(t)
[/mm]
Und wir haben auch die harmonische Zahl definiert:
[mm] H_n [/mm] := [mm] \summe_{i=1}^{n} \bruch{1}{i} [/mm] ~ log(n)+ [mm] \gamma [/mm] + [mm] \bruch{1}{2n}
[/mm]
Für ein wenig Hilfe bei dem Beispiel wäre ich euch sehr verbunden.
|
|
| |
|
Hat denn niemand einen Vorschlag?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:46 Di 12.10.2010 | | Autor: | wauwau |
betrachte mal die folg. Tabelle
[mm] \vmat{ d,j & 1 & 2 & 3 & 4 & 5 & 6&7&8&9 \\ 1&1&1&1&1&1&1&1&1&1\\2&&1&&1&&1&&1\\3&&&1&&&1&&&1\\4&&&&1&&&&1\\5&&&&&1\\6&&&&&&1\\7&&&&&&&1\\8&&&&&&&&1\\9&&&&&&&&&1 }
[/mm]
in der Spalten j steht genau bei jenen Zeilen eine 1, die eine Teiler von j sind.
d.h. die Spaltensummen sind die anzahl der Teiler von j
Summierst du nun über alle Teiler von j=1,n (in unserem Fall 9), das heißt über alle spalten, so kannst du auch über alle Zeilen summieren.
(= doppelte Abzählung)
Die Zeilensumme der Zeile i ist aber genau [mm] $\lfloor\frac{n}{i} \rfloor$
[/mm]
|
|
|
| |
|
Vielen Dank erstmal für die Information. Ich frage mich nun trotzdem wie ich auf [mm] \lfloor\frac{n}{i} \rfloor [/mm] komme.
Wenn ich über alle Spalten bzw. Zeilen in unserem Falle (also 9 summiere) erhalte ich [mm] \bruch{23}{9}. [/mm] Wie kann ich es anschreiben, dass die Zeilensumme der Zeile i genau [mm] \lfloor\frac{n}{i} \rfloor [/mm] ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:10 Di 12.10.2010 | | Autor: | wauwau |
lass einmal das 1/n weg!
Die Summe der Zeilensummen ist gleich die Summe der Spaltensummen
spaltensumme der spalte j = t(j)
zeilensumme:
in der i-ten Zeile steht alle i spalten eine 1
daher ist die anzahl der 1 (damit die Summe) von der 1 bis zur n-ten Spalte genau [ [mm] $\bruch{n}{i}$ [/mm] ]
und dann summierst du nun über alle Zeilen von i=1,n
|
|
|
| |
|
Also würde das dann so aussehen:
[mm] \summe_{i=1}^{n} [\bruch{n}{i}] [/mm] = [mm] [\bruch{n}{1}]+[\bruch{n}{2}]+[\bruch{n}{3}]+...+[\bruch{n}{i}] [/mm] = [mm] \summe_{j=1}^{n}t(j)
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:44 Di 12.10.2010 | | Autor: | wauwau |
exakt...
|
|
|
| |
|
Somit ist das Beispiel auch komplett gelöst, verstehe ich das richtig?
Vielen Dank für deine Hilfe.
Lg und schönen Abend noch.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:19 Mi 13.10.2010 | | Autor: | wauwau |
genau
|
|
|
|
