gegeben ist folgende abbildung: c: N0 x N0 -> N0; (x,y) -> binokoeff(x+y+1;2) +x
wobei N0 die natürlichen Zahlen mit 0 und binokoeff(x+y+1;2) der binomialkoeffizient (x+y+1) über 2 ist
Zu zeigen ist nun, dass diese abbildung bijektiv ist. hat jemand ne idee?
2008-11-11T13:00:14Z
die frage stammt von nem übungsblatt theoretische informatik
und inzwischen weiß ich auch, dass es wohl möglich ist, das ganze direkt über die definition von injektiv und surjektiv zu zeigen und ja man muss wohl eine weile rechnen
Introspection2008-11-12T03:27:20Z
Beste Antwort
Hi, zwei Lösungsvorschläge, ein sehr kurzer und ein langer:
Der kurze: "Rate" eine Umkehrfunktion f^-1 und zeige, dass gilt: f(f^-1(n)) = n, sowie f^-1(f(x,y)) = (x,y). Dadurch zeigst du, dass sowohl f, als auch f^-1 bijektiv sind.
Der lange:
Zuerst die Surjektivität, die ist sehr einfach zu beweisen durch vollständige Induktion nach n = f(x,y):
A(n) = es gibt x und y aus N (Menge der natürlichen Zahlen inklusive 0), sodass f(x,y) = n.
Induktionsschritt A(n) -> A(n+1): Es gelte die Induktionsannahme: Es gibt x_n und y_n aus N mit n = binokoeff(x_n + y_n + 1; 2) + x_n, wobei x_n bzw. y_n das zu n gehörende x bzw. y ist.
Also gibt es für jedes n aus N ein x und y, sodass n = f(x,y). Damit ist die Surjektivität bewiesen.
Jetzt die Injektivität: Für einen einfachen Beweis sei festgehalten, dass gilt:
binokoeff(a+1; 2) = Summe_{k=1 bis a} k, also die Summe aller natürlicher Zahlen <= a.
Gezeigt wird: f(a, b) = f(c, d) => a=c und b=d:
Sei f(a, b) = f(c, d).
binokoeff(a+b+1; 2) + a = binokoeff(c+d+1; 2) + c <=> Dann gilt mit obigem Satz a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k
Wir zeigen, dass a=c gelten muss:
Sei ohne Einschränkung der Allgemeinheit a<c. Betrachte die Gleichheit
a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k. <=> Summe_{k=1 bis a+b} k = (c-a) + Summe_{k=1 bis c+d} k
Wegen a<c ist (c-a)>0, also ist die Summe auf der linken Seite größer als die auf der rechten, also gilt a+b > c+d. Subtraktion der rechten Summe bringt
Summe_{k=c+d+1 bis a+b} k = (c-a)
wobei nach obiger Herleitung die linke Summe aus mindestens einem Summanden besteht. Also:
Summe_{k=c+d+1 bis a+b} k = (c-a) <=> c+d+1 + Summe_{k=c+d+2 bis a+b} k = (c-a) <=> d+a+1 + Summe_{k=c+d+2 bis a+b} k = 0
Die linke Seite ist wegen dem "+1" aber stets größer 0 (die Summe, sowie a,b,c,d können ja nicht kleiner 0 sein, weil sie natürliche Zahlen sind). Widerspruch. Auf dieselbe Weise zeigt, man, dass a nicht größer als c sein kann. Daraus folgt: a=c.
Weiterhin gilt: a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k <=> (wegen a=c) Summe_{k=1 bis a+b} k = Summe_{k=1 bis a+d} k
=> b=d
Also gilt: f(a, b) = f(c, d) => a=c und b=d, was zu beweisen war.