Faktorisierung Primz.-Produkt < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:24 So 26.06.2005 | | Autor: | dh_zm |
Hallo,
also hier erstmal die Aufgabe:
-----------------------------------------------
Es seien
$ [mm] p_{1}, p_{2}, [/mm] ... , [mm] p_{n} [/mm] $
n verschiedene Primzahlen. Wieviel Möglichkeiten gibt es, das Produkt
$ [mm] p_{1} [/mm] * [mm] p_{2} [/mm] * ... * [mm] p_{n} [/mm] $
in zwei oder mehr Faktoren, jeder größer als 1, zu zerlegen, wobei die Reihenfolge der Faktoren keine Rolle spielt?
-----------------------------------------------
Sah auf den ersten Blick für mich garnicht so schwierig aus, war es dann aber doch... :)
Hier mein Ansatz:
Ich habe eine n-Menge von (versch.) Primzahlen.
Diese n-Menge Zerlege ich in 2 od. mehr Mengen (die Faktoren).
Einfachster Fall: ich zerlege die n-Menge in n 1-Megen, d.h. meine Faktoren sind die Primzahlen selbst. Da die Reihenfolge der Faktoren aber keine Rolle spielt, teile ich durch
$ n! $
Anzahl der Möglichkeiten für diesen Fall (Multinomialkoeffizient):
$ [mm] \frac{n!}{ \underbrace{1! * 1! * ... * 1!}_{n\ mal} } [/mm] * [mm] \frac{1}{n!} [/mm] = [mm] \begin{pmatrix} n \\ 0 \end{pmatrix} [/mm] = 1 $
Weiterer einfacher Fall: ich zerlege die n-Menge in eine 1-Menge und eine (n-1)-Menge, d.h. meine Faktoren sind eine Primzahl und der Rest.
Anzahl der Möglichkeiten für diesen Fall (Multinomialkoeffizient):
$ [mm] \frac{n!}{1! * (n-1)!} [/mm] = [mm] \begin{pmatrix} n \\ 1 \end{pmatrix} [/mm] = n $
So kann man ja jetzt weitermachen, d.h. ich nehme dann 2 Primzahlen und den Rest usw.
Das Problem ist aber, dass ich auch als Zerlegung das Produkt 2er Primzahlen und der Rest nehmen kann usw.
Ab da blick ich dann nicht mehr durch, denn einige Möglichkeiten überschneiden sich.
Nehmen wir als beispiel mal n=4 und als Primzahlen 2,3,5,7:
2 * 3 * 5 * 7
-----------
2 * 105
3 * 70
5 * 42
7 * 30
-----------
2 * 3 * 35 (es geht aber auch 6 * 35)
2 * 5 * 21 (es geht aber auch 10 * 21)
2 * 7 * 15 (es geht aber auch 14 * 15)
3 * 5 * 14 (es geht aber auch 15 * 14 - Überschneidet sich mit oben)
3 * 7 * 10 (es geht aber auch 21 * 10 - Überschneidet sich mit oben)
-----------
5 * 7 * 6
man erhät also 16 Möglichkeiten, abzüglich der 2 doppelten ergibt 14.
Die 16 Möglichkeiten sind genau
[mm] \begin{pmatrix} 4 \\ 0 \end{pmatrix} + \begin{pmatrix} 4 \\ 1 \end{pmatrix} + \begin{pmatrix} 4 \\ 2 \end{pmatrix} + \begin{pmatrix} 4 \\ 3 \end{pmatrix} + \begin{pmatrix} 4 \\ 4 \end{pmatrix} = 2^4
[/mm]
Meine Vermutung ist also, dass ich über die n-te Zeile im Pascalschen Dreieck aufsummiere ( $ [mm] =2^n [/mm] $ )und dann die doppelten Fälle abziehe, aber wie bekomme ich die Anzahl der doppelten (sich überschneidenden) Möglichkeiten heraus?
Für Hilfe wäre ich sehr dankbar!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Daniel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:56 So 26.06.2005 | | Autor: | DaMenge |
Hallo Daniel,
ich erdreiste mir mal eine Antwort, obwohl ich von dem Inhalt nicht wirklich viel Ahnung habe (deshalb auch nur teilweise beantwortet):
> -----------------------------------------------
> Es seien
>
> [mm]p_{1}, p_{2}, ... , p_{n}[/mm]
>
> n verschiedene Primzahlen. Wieviel Möglichkeiten gibt es,
> das Produkt
>
> [mm]p_{1} * p_{2} * ... * p_{n}[/mm]
>
> in zwei oder mehr Faktoren, jeder größer als 1, zu
> zerlegen, wobei die Reihenfolge der Faktoren keine Rolle
> spielt?
> -----------------------------------------------
Wir nehmen erstmal an, man will genau k Faktoren haben, dann suchst du also die Anzahl der Partitionen der Menge N (=n elementige Menge) in genau k nicht-leere Teilmengen - dies ist soweit ich weiss S(n,k) die Stirlingzahl zweiter Art:
siehe zum Beispiel ![[]](/images/popup.gif) HIER (PDF) (Seite 34 §8.2)
Hinweis: Eine Partition P ist eine Menge von Teilmengen, d.h. die Reihenfolge der Teilmengen in P spielt keine Rolle.
Nun musst du zum Schluss noch über alle k von 2 bis n summieren, wie du in obigen PDF siehst, wäre die Summe von 1 bis n gerade die Bell-Zahl.
D.h. du musst von der Bel-zahl [mm] B_n [/mm] noch S(n,1) abziehen und hast dein Ergebnis, weil aber S(n,1)=1 (nur ganz N ist die eine Partition), ist dein Ergebnis: $ [mm] (B_n [/mm] -1) $ wobei [mm] B_n [/mm] die n-te Bell-Zahl ist.
ich hoffe, ich liege nicht zu sehr daneben
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:45 Mo 27.06.2005 | | Autor: | dh_zm |
Danke für die Antworten!
jetzt im nachhinein sieht es garnicht mehr so schwer aus, wenn man auf die stirling-zahlen gestoßen wurde... :)
aber hinterher sieht ja alles leichter aus :)
|
|
|
| |
|
| Status: |
(Antwort) noch nicht fertig  | | Datum: | 07:50 Mo 27.06.2005 | | Autor: | Dreieck |
Hi Daniel!
> Es seien
>
> [mm]p_{1}, p_{2}, ... , p_{n}[/mm]
>
> n verschiedene Primzahlen. Wieviel Möglichkeiten gibt es,
> das Produkt
>
> [mm]p_{1} * p_{2} * ... * p_{n}[/mm]
>
> in zwei oder mehr Faktoren, jeder größer als 1, zu
> zerlegen, wobei die Reihenfolge der Faktoren keine Rolle
> spielt?
> -----------------------------------------------
>
> Sah auf den ersten Blick für mich garnicht so schwierig
> aus, war es dann aber doch... :)
Ist auch gar nicht schwierig.
Formulieren wir die Aufgabe anders:
Wie viele Moeglichkeiten gibt es mit n (paarweise-verschiedenen) Primzahlen eine Zahl zu bilden, das waere dann der eine Faktor (der andere ergibt sich automatisch durch die uebriggeblibenen Primfaktoren). Wir duerfen nur nie alle Primzahlen verwenden oder auch nie keine, da die Faktoren ja immer groesser 1 sein sollen.
Diese Aufgabe koennen wir wieder umformulieren:
Wie viele n-stellige Zahlen kann man im Binaersystem bilden (1 bedeutet dann Primzahl als Faktor dabei, 0 Primazahl im zweiten Faktor), wobei die Zahl [mm]\underbrace{111...1}_{n-mal}[/mm] und die Zahl [mm]\underbrace{000...0}_{n-mal}[/mm] nicht dabei sein duerfen:
es gibt also [mm]2^n[/mm] binaere Zahlen, die n-stellig sind, jetzt muessen wir noch die 2 "verbotenen Zahlen" abziehen und schliesslich durch 2 dividieren, da jeder Fall doppelt vorkommt. wirerhalten
[mm] \frac{2^n - 2}{2} = 2^{n-1} - 1 [/mm] Moeglichkeiten
mist, hab zu spaet gelesen, dass in der Angabe 2 oder mehr Faktoren steht, mein Gedankenmuell gilt ja nur fuer 2 Faktoren.
sorry.
lG
Peter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:51 Mo 27.06.2005 | | Autor: | Dreieck |
Hi!
Wenn man versucht alle Faktoren beispielsweise fuer 6 paarweise-verschiedenen Primzahlen zu finden, gibts 5 verschiedene Anzahlen von Faktoren: 2,3,4,5,6
Schaun wir uns die Faelle genauer an:
2 Faktoren:
[mm]\frac{6!}{5!1!} + \frac{6!}{4!2!} + \frac{6!}{3!2!} [/mm]
[mm] = 6 + 15 +10 = 31\,[/mm]
(bzw [mm] 2^{6-1} - 1 = 31 [/mm] damit ich meine vorigen Ueberlegungen einfliessen lassen kann  )
3 Faktoren:
[mm]\frac{6!}{4!1!1!2!} + \frac{6!}{3!2!1!} + \frac{6!}{2!2!2!3!} [/mm]
[mm] = 15 + 60 +15 = 90\,[/mm]
4 Faktoren:
[mm]\frac{6!}{3!1!1!1!3!} + \frac{6!}{2!2!1!1!2!2!} [/mm]
[mm] = 20 + 45 = 65\,[/mm]
5 Faktoren:
[mm]\frac{6!}{2!1!1!1!1!4!} [/mm]
[mm] = 15\,[/mm]
6 Faktoren:
[mm] 1\,[/mm]
und die Summe dieser Zahlen [mm]31+90+65+15+1 = 202[/mm] entspricht ja der Bell-Zahl [mm]B_6 -1 \,[/mm]
Die Begruendung findet sich gut erklaert in DaMenge's pdf (haett ichs bloss schon vor meiner ersten Antwort gelesen ).
Somit ist, wie DaMenge schon gesagt hat, die Anzahl der Moeglichkeiten das Produkt [mm]p_1*p_2*p_3*...*p_n\,[/mm] von [mm]n\,[/mm] paarweise-verschiedenen Primzahlen [mm]p_i\,[/mm] in 2 oder mehr Faktoren zu zerlegen, gleich [mm]B_n - 1[/mm].
lG
Peter
|
|
|
|
