Die Mathe-Redaktion - 16.12.2019 05:58 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 442 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Binomialverteilungen: Formel zur Verteilung (unter Bedingungen) gesucht
Druckversion
Druckversion
Antworten
Antworten
Autor
Schule Binomialverteilungen: Formel zur Verteilung (unter Bedingungen) gesucht
Schneeeule
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-18 19:34


Hallo liebes Forum,

folgendes Problem habe ich bzw. ist eine Lösung gesucht wie folgt…

Ziel bzw. gesucht ist:
… die exakte binomiale Verteilung von Zeichen („A“, „B“, „C“) an ihrer Position in Zeichenreihen zu ermitteln. Dabei werden für die Zeichenreihen Vorgaben/Bedingungen vorgegeben (Mindest- und Maximalvorkommen mehrerer Positionen).

Hierzu suche ich die Formel zur Ermittlung jeder Zeichenposition („Koordinatenfeld“) anhand einer theoretisch unbegrenzten Anzahl zu setzender Vorgaben.

Als Erklärung habe ich unten etwas ausführlicher ein grafisches Beispiel dargestellt (es ist zwar sehr ausführlich, aber so lässt es sich m. E. am besten darstellen und jeder Vorschlag einer rechnerischen Lösung könnte daran direkt selbst kontrolliert werden).

„Bekannt“ ist:
1.        Die Summe jeder Zeile ist immer gleich. (also die Zeichen A+B+C)
2.        Alle Werte sind nichtnegative, ganze Zahlen.
3.        Es können ausschließlich dort Min/Max-Vorgaben gemacht werden, wo auch im Hauptplan ein „X“ gesetzt worden ist.
4.        Je Min/Max-Vorgabe darf je Zeile maximal ein Kreuz als Bedingung stehen (kein Kreuz ist auch möglich).
5.        Es handelt sich (natürlich) um eine rein binomiale Verteilung  (grafisch gut durch das Pascalsche Dreieck vorstellbar).

Hierzu nachfolgend einige konkrete Beispiele.


Beispiele:

Erklärung:

Vorgegeben ist ein „Hauptplan“ mit 9 Zeichenpositionen (Zeilen) sowie der Festlegung, auf welcher Position die Zeichen „A“, B“, „C“ grundsätzlich erlaubt sind. (Am Beispiel: Zeichen „A“ kann in einer Reihe an Position 1 bis 9 stehen, Zeichen „C“ aber nur an Position 1-6 einer Reihe.)

Bild 1:


(Das rechte Bild mit den „Koordinaten“ gilt nur zum Verständnis, damit man später immer genau weiß, über welches Feld man spricht.)

Ohne irgendwelche Vorgaben ließen sich daraus 2.916 mögliche Reihen bilden (3^6 * 2^2) , die z. B. nacheinander so aussehen können (Position 1 – 9 von links nach rechts dargestellt):
Reihe 1. A,A,A,A,A,A,A,A,A
2. B,A,A,A,A,A,A,A,A
3. C,A,A,A,A,A,A,A,A
4. A,B,A,A,A,A,A,A,A
5. B,B,A,A,A,A,A,A,A
6. C,B,A,A,A,A,A,A,A
7. A,C,A,A,A,A,A,A,A
8. B,C,A,A,A,A,A,A,A
… usw
2916. C,C,C,C,C,C,B,B,A

Würde man jetzt „auszählen“, wie oft jedes Zeichen an welcher Position steht, erhält man folgendes Bild 2:


Neben dem Hauptplan werden dann zusätzliche Vorgaben gesetzt, welche Zeichen wie oft Minimal/Maximal an einer gewissen Position vorkommen dürfen.
Als ganz einfaches Beispiel hierfür (Bild 3):


Würde man jetzt auf Koordinatenfeld 23 oder 24 noch ein „x“ ergänzen, aber alle anderen Vorgaben so lassen, so würden sich die Verteilungen entsprechend verdoppeln oder verdreifachen (Bild 4):


Wenn dann bei einer Vorgabe z. B. das Minimum=2 und Maximum=4 ist, dann addieren sich die einzelnen binomialen Verteilungen für jeweils 2, 3 und 4, z. B. (Bild 5):


Außerdem: Wenn es sich bei zwei Zeichen (z. B. „A“; „B“) um eine einfache Binomialverteilung mit Minimum=Maximum (bei der Vorgabe) handelt und ein weiteres Zeichen kommt hinzu („C“) , dann hatte „weird“ hierfür bereits einen Formelansatz gefunden: LinkFormeldarstellung gesucht (für Summen-Zahlentabelle)).
(Danke nochmal hierfür!)
Diese Situation kann man so darstellen (Bild 6):


So weit ist das Prinzip bestimmt klar.  :-)



Jetzt kommt die eigentliche Schwierigkeit und das Problem für die Errechnung einer Verteilung:
Statt nur einer Vorgabe werden mehrere Vorgaben gesetzt!

Grafisch sieht das dann so aus (Bild 7):



Dies bedeutet z. B. bei Vorgabe 1, dass von dessen Kreuzchen in den Koordinatenfeldern 1, 4 und 7 das Zeichen „A“ exakt 2mal vorkommen soll.
Dies hat zur Folge, dass es weniger Ergebnisreihen geben wird und Auswirkungen auf die binomialen Verteilungen in vielen oder allen Koordinatenfeldern hat.

Die Formel zur Errechnung genau dieser exakten Verteilung je Koordinatenfeld ist nun gesucht (egal wie viele Vorgaben gleichzeitig gelten sollen).
In der zu findenden Formel können alle denkbaren bekannten Variablen mit verwendet werden (z. B. Anzahl sich überdeckender Kreuze [hier: Koordinatenfeld 1] oder auch Leerpositionen bei Vorgaben) – der „Phantasie“ sind da keine Grenzen gesetzt.

(Ich persönlich könnte mir gut vorstellen, dass ein „eleganter“ Weg zur Lösungsfindung der Formel so geht, dass die Formel z. B. immer von Vorgabe zu Vorgabe rechnet.
Das heißt, es wird erst die Binomialverteilung ohne Vorgaben und dann die Verteilung je Koordinatenfeld nach Setzung der ersten Vorgabe ausgerechnet.
Dann folgt die zweite Vorgabe, welche sich auf die bereits errechnete Verteilung bezieht, und es wird eine neue Verteilung berechnet.
Dann weiter mit Vorgabe Nr. 3 usw.
Mit solch einer Vorgehensweise bräuchte man dann keine riesige Formel, sondern für jede Berechnung stets nur eine vorher vorgegebene Verteilung, auf welche sich dann eine neue Vorgabe beziehen soll.
Allerdings ist es lediglich eine Idee – ich bin ich mir nicht sicher, ob dieser Ansatz richtig ist.)


Lösungsbeispiele:

Damit etwaige Interessierte und Helfer zur Lösung „probieren“ und sehen können, ob ihre Formel stimmt, habe ich mal nachfolgend alle Kombinationen der obigen drei Vorgaben ausgezählt und die finalen Verteilungen dargestellt (Vorgabe 1 = orange, Vorgabe 2 = grün, Vorgabe 3 = blau) – Bild 8:


Ich denke, es ist ein sehr kniffliges, aber dennoch lösbares Problem. Irgendeine Rechenmöglichkeit/Formel muss es da geben.
Wenn jemand helfen könnte, würde ich mich sehr freuen.  :-)

(Gern mit konkretem Zahlenbeispiel anhand einer Formel – da lässt es sich gut nachvollziehen)

Vielen Dank im Voraus für Eure Hilfe!!
Liebe Grüße, Schneeeule

PS: Wenn noch ein weiteres ausführliches Beispiel mit Lösungen benötigt wird, kann ich das gern einbinden.
Gern auch auf Nachfrage zu einer ganz bestimmten Konstellation, welche ich „auszählen“ lasse und die Verteilung dann poste.












  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6110
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-11-19 13:18


Ich möchte anmerken, dass man mit einer Formel, die die Anzahl der Möglichkeiten bestimmt das Erfüllbarkeitsproblem (SAT) lösen kann.
Jede Variable ist eine Zeile, es gibt zwei Spalten für negiert und nicht-negiert und man hat für jede Zeile eine Vorgabe, dass genau eine der beiden Spalten besetzt sein muss. Danach kann man mit weiteren Vorgaben beliebige Klauseln bilden, in dem man bei allen vorkommenden Variablen bei negiert/nicht-negiert das passende Kreuz setzt und dann fordert, dass mindestens ein Kreuz in der Lösung vorkommt.
Das so modellierte SAT-Problem ist genau dann erfüllbar, wenn die Zahl der Lösungen größer als 0 ist.

Das heißt _nicht_, dass es keine "Formel" zur Bestimmung der Zahl der Lösungen gibt. Aber es heißt, dass die Berechnung dieser Formel voraussichtlich nicht in Polynomialzeit möglich ist (SAT ist NP-vollständig, läge SAT in P, dann wäre P=NP, was vermutlich nicht der Fall ist). Zumindest ist bislang kein Polynomialzeitalgorithmus bekannt.



  Profil  Quote  Link auf diesen Beitrag Link
Schneeeule
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2019
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-11-19 19:35






Vielen Dank für Deine Antwort und Hinweis!

Ich denke jedoch nicht (mehr), dass es sich um ein Art SAT-Problem handelt (bzw. nur, wenn mehrere Vorgaben gleichzeitig gemacht werden müssten).
Auf Deinen Hinweis hin (dass es NP-vollständig ist, wenn praktisch unendlich viele Variablen bzw. oben von mir geschrieben "Vorgaben" existieren) ist mir noch eine Idee gekommen.

Und zwar möchte ich meine Idee der Lösungsfindung noch einmal aufgreifen, wonach lediglich eine bestimmte Basisverteilung vorgegeben ist und eine einzige Vorgabe (Binomialverteilung) dem gegenübergesetzt wird.
Nur mittels dieser einen Vorgabe kann man dann daraus die finale Verteilung berechnen.

Ich habe das gegengeprüft, indem ich eine bestimmte Basisverteilung eingeladen habe (ohne das bekannt ist, warum sich diese so zusammen setzt wie sie ist - dies ist egal) und dann die einschränkende Vorgabe (Binomialverteilung) darauf angewendet.
Die Ergebnisse der finalen Verteilung lassen sich daraus ableiten.

Dadurch, dass es also immer die gleiche Berechnung ist, sollte die Komplexität der im Eingangspost gesuchten Formel deutlich einfacher sein als (von mir) vorher noch angenommen.
Gern noch einmal anhand einiger Beispiele, was ich meine bzw. zum selbst Probieren.
Das Vorgehen ist von links nach rechts immer identisch (1. beliebige Basisverteilung vorgeben, 2. Vorgabe machen, welche für sich eine Binomialverteilung darstellt*; 3. Ausgabeverteilung wird anhand der Basis- sowie Binomialverteilung berechnet - diese Formel/Zusammenhang ist gesucht):






* mit den oben genannten Bedingungen (je Zeile maximal ein Zeichen erlaubt und auch nur dort, wo an gleicher Position ein Wert in der Basisverteilung enthalten ist)
Alle Tips zur Bildung der Binomialverteilungen bleiben natürlich gültig und helfen bestimmt.


Ich würde mich sehr über Ideen zur Formelbildung freuen, wie man aus der festgeschriebenen Basisverteilung und einer vorgegebenen Binomialverteilung (als Bedingung) daraus die finale Zeichenverteilung ableiten könnte.


Danke vorab für jede Hilfe und Herzliche Grüße!
Schneeeule



  Profil  Quote  Link auf diesen Beitrag Link
Schneeeule hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]