matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-NumerikFaktorisierung Primz.-Produkt
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Uni-Numerik" - Faktorisierung Primz.-Produkt
Faktorisierung Primz.-Produkt < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Faktorisierung Primz.-Produkt: Anzahl solcher Möglichkeiten?
Status: (Frage) beantwortet Status 
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

        
Bezug
Faktorisierung Primz.-Produkt: Antwort
Status: (Antwort) fertig Status 
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 []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

Bezug
                
Bezug
Faktorisierung Primz.-Produkt: Danke!
Status: (Mitteilung) Reaktion unnötig Status 
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 :)

Bezug
        
Bezug
Faktorisierung Primz.-Produkt: fuer 2 Faktoren
Status: (Antwort) noch nicht fertig Status 
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

Bezug
        
Bezug
Faktorisierung Primz.-Produkt: DaMenge hat recht
Status: (Antwort) fertig Status 
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





Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]