Möglichkeiten Anordn.(schwer?) < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:37 Do 25.11.2010 | | Autor: | qsxqsx |
Hallo,
Ich häng hier seit unermesslich langer Zeit fest und komm nich viel weiter als das ich mehr in verwirrung komme.
Gesucht sind alle Anordnungen von Zahlen, sodass in keiner Spalte mehrmals die Gleiche Zahl auftritt. EDIT: Jede der 6 Zahlen soll einmal verwendet werden.
Tönt einfach, ich fins auf jedenfall schwierig. Hab auch schon einen Baum probiert aber das wird katastrophal...
Der erste schritt ist noch klar: Für die 1 hat man 4 Möglichkeiten, für die 2 ist es schon unklar, weil es darauf ankommt wo man die 1 vorher hingesetzt hat.
[Dateianhang nicht öffentlich]
EDIT: Aja meine Lösungsansätze, (hätt ich doch beinah vergessen...):
Ich sehe es grundsätzlich als ein "Schnittmengenproblem"
-Bekannt ist mir das Verfahren "Inklusion - Exklusion"
Dieses hat zumindest auch mit Schnittmengen zu tun, sehe aber trotzdem nicht wie das hier hin passen würde
-In jedes Feld gibt es anfangs mal 4 Möglichkeiten für eine Zahl
-Ich habe mir mal unter diese Tabelle für jede Zahl linien gemalt wo sie sein kann, und dann sieht man hald wie die sich überschneiden...vielleicht schafft das etwas mehr übersicht.
...und übrigens, ich hab mir die Aufgabe selbst erfunden. Muss aber eine Lösung geben, da sind wir sicher!
Es weiss sicher jemand weiter?
Danke sehr!
Gruss
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:37 Fr 26.11.2010 | | Autor: | ONeill |
Hi!
> Gesucht sind alle Anordnungen von Zahlen, sodass in keiner
> Spalte mehrmals die Gleiche Zahl auftritt. EDIT: Jede der 6
> Zahlen soll einmal verwendet werden.
>
> Tönt einfach, ich fins auf jedenfall schwierig. Hab auch
> schon einen Baum probiert aber das wird katastrophal...
> Der erste schritt ist noch klar: Für die 1 hat man 4
> Möglichkeiten, für die 2 ist es schon unklar, weil es
> darauf ankommt wo man die 1 vorher hingesetzt hat.
Also wenn du eine Zahl, zB die 1 in den Kästchen A-F einordnen kannst, dann hast Du waagerecht gesehen 6 Anordnungsmöglichkeiten. Kommt die zweite Zahl hinzu bleiben noch 5 Anordnungsmöglichkeiten usw.
Senkrecht kannst Du den Weg analog gehen.
Gruß Christian
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:59 Fr 26.11.2010 | | Autor: | qsxqsx |
Hallo,
Thx. Aber ich bin nicht ganz sicher was du meinst bzw. vielleicht verstehst du die Aufgabe nicht genau so wie ich?
Die 1 hat zuerst mal 4 Felder in die man sie setzen kann, nicht 6, da ja in zwei Spalten eine 1 steht...
Oder wie meinst du das?
Gruss
|
|
|
| |
|
Huhu,
> -Bekannt ist mir das Verfahren "Inklusion - Exklusion"
dann wende sie doch auch an 
Setze
[mm] A_1 [/mm] = Erste Position ist 1,2
[mm] \vdots
[/mm]
[mm] A_6 [/mm] = Sechste Position ist 6,1
Und nun kannst du ja alle Einsetzen ausser [mm] \bigcup A_i [/mm] ..... Naja, und nun Siebformel draufwerfen.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:15 Fr 26.11.2010 | | Autor: | qsxqsx |
Jaja, ist ganz einfach gelle, einfach "Siebformel" anwenden...; )
Also: [mm] A_{1} [/mm] = 5*4*4!, richtig? Ich weiss nicht so, habe jetzt wieder rumprobiert und komme auf keinen Grünen Zweig.
6! - (5*4*4*3*2)*6 + ...?
oder
6! - 5!*2*6 + 4!*6*3! - ...?
Das sind so meine Versuche.
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:31 Fr 26.11.2010 | | Autor: | Gonozal_IX |
Huhu,
> Jaja, ist ganz einfach gelle, einfach "Siebformel"
> anwenden...; )
Jo, das ist jetzt nun wirklich nicht mehr schwer......
Ein bisschen Nachdenken sollte jeder können.
>
> Also: [mm]A_{1}[/mm] = 5*4*4!, richtig? Ich weiss nicht so, habe
> jetzt wieder rumprobiert und komme auf keinen Grünen
> Zweig.
Nein.
Ok, stellen wir uns das mal als 6-Tupel vor, d.h. alle Lösungen haben die Form
[mm] $(\omega_1,\ldots,\omega_6)$
[/mm]
Alle Möglichkeiten die 6 Zahlen auf solche Tupel zu verteilen, sind nun 6!
Soweit klar?
Betrachten wir nun mal [mm] A_1
[/mm]
Dort soll die erste Zahl eine 1 oder 6 sein.
Alle Tupel haben also die Form [mm] $(1,\omega_2,\ldots,\omega_6)$ [/mm] oder [mm] $(6,\omega_2,\ldots,\omega_6)$.
[/mm]
Wieviele Tupel der Form [mm] $(1,\omega_2,\ldots,\omega_6)$ [/mm] gibt es nun? Naja, 5! da man die restlichen 5 Zahlen auf 5 Positionen verteilen kann.
Analog für das andere Tupel, d.h.
[mm] $|A_1| [/mm] = 2*5!$
Nun machst du mal weiter!
MFG,
Gono.
edit: Stelle deine Frage nächstemal bitte auch als solche, sonst übersieht man es schnell.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:42 Fr 26.11.2010 | | Autor: | qsxqsx |
> > Jaja, ist ganz einfach gelle, einfach "Siebformel"
> > anwenden...; )
>
> Jo, das ist jetzt nun wirklich nicht mehr schwer......
> Ein bisschen Nachdenken sollte jeder können.
Das sag ich jetzt nix zu.
>
> >
> > Also: [mm]A_{1}[/mm] = 5*4*4!, richtig? Ich weiss nicht so, habe
> > jetzt wieder rumprobiert und komme auf keinen Grünen
> > Zweig.
>
> Nein.
> Ok, stellen wir uns das mal als 6-Tupel vor, d.h. alle
> Lösungen haben die Form
>
> [mm](\omega_1,\ldots,\omega_6)[/mm]
>
> Alle Möglichkeiten die 6 Zahlen auf solche Tupel zu
> verteilen, sind nun 6!
> Soweit klar?
Sicher.
>
> Betrachten wir nun mal [mm]A_1[/mm]
> Dort soll die erste Zahl eine 1 oder 6 sein.
> Alle Tupel haben also die Form
> [mm](1,\omega_2,\ldots,\omega_6)[/mm] oder
> [mm](6,\omega_2,\ldots,\omega_6)[/mm].
>
> Wieviele Tupel der Form [mm](1,\omega_2,\ldots,\omega_6)[/mm] gibt
> es nun? Naja, 5! da man die restlichen 5 Zahlen auf 5
> Positionen verteilen kann.
> Analog für das andere Tupel, d.h.
>
> [mm]|A_1| = 2*5![/mm]
>
> Nun machst du mal weiter!
Sorry das ich nicht konkret mein Problem dargestellt habe. Also, so weit war ich schon, ich habe ja geschrieben: "6! - 5!*2*6 + 4!*6*3! - ...?"
Nur irgendwie wusste ich nicht mehr weiter. Aber du hast mir ja jetzt versichert das das in die richtige Richtung ging. Neuer Versuch:
1.) +6! <---> Alle Möglichkeiten.
2.) -2*5!*6 <---> Ziehe alle Möglichkeiten ab, die aufgrund der Spaltenbedingung nicht möglich sind. Mal 6 weil das 2*5! ja für jede der 6 Spalten abgezogen wird.
3.) +2*4!*6 <---> Da in 2. zuviele abgezogen wurden. Und zwar
4.) - 2*3!*6 <---> ...
5. + 2*2!*6 <---> ...
6.) - 2*1!*6 <---> ...
...= -492, kann ja nicht sein, oder?!
PS: Mit [mm] A_{1} [/mm] meinst du alle Tupel mit erster Zahl 1 oder 2 (das solltest du vielleicht nocht editieren)...
Gruss
|
|
|
| |
|
Hiho,
da scheitert es wohl einfach nur am richtigen aufschreiben.
Das meinte ich mit "nicht wirklich schwer".... sauber aufschreiben gehört anscheinend doch dazu
[mm] $\left|\bigcup_{k=1}^6 A_k\right| [/mm] = [mm] \summe_{k=1}^6|A_k| [/mm] - [mm] \summe_{1\le k < l \le 6}|A_k \cap A_l| [/mm] + [mm] \summe_{1 \le k < l < j \le 6}|A_k \cap A_l \cap A_j| [/mm] - [mm] \summe_{1 \le k < l < j < m \le 6}|A_k \cap A_l \cap A_j \cap A_m| [/mm] + [mm] \summe_{1 \le k < l < j < m < n \le 6}|A_k \cap A_l \cap A_j \cap A_m \cap A_n| [/mm] - [mm] \left|\bigcap_{k=1}^6 A_k\right|$
[/mm]
Wir hatten ja bereits festgestellt:
[mm] $|A_k| [/mm] = 2*5!$
Aus Symmetriegründen können wir bei der den nachfolgenden Summen die Werte für EINE Möglichkeit ausrechnen und dann einfach mit Anzahl der Möglichkeiten multiplizieren.
Ich machs mal am ersten Beispiel, die restlichen kannst du dann ja weiter ausführen:
[mm] $A_1 \cap A_2 [/mm] = [mm] \{\omega_1 = 1 \vee \omega_1 = 2\} \cap \{\omega_2 = 2 \vee \omega_2 = 3\}$
[/mm]
$= [mm] \{\omega_1 = 1,\omega_2 = 2\} \cap \{\omega_1=1,\omega_2 =3\} \cap \{\omega_1=2,\omega_2=2\} \cap \{\omega_1=2,\omega_2=3\}$
[/mm]
und damit:
[mm] $|A_1 \cap A_2| [/mm] = 4! + 4! + 0 + 4! = 3*4!$
Und damit folgt:
$ [mm] \summe_{1\le k < l \le 6}|A_k \cap A_l| [/mm] = [mm] \vektor{6 \\ 2} [/mm] * [mm] |A_1 \cap A_2| [/mm] = 15*3*4! [mm] \not= [/mm] 4!*6*3!$ was du raus hattest.
Also schaus dir nochmal an 
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:52 Sa 27.11.2010 | | Autor: | qsxqsx |
Danke sehr, das war sehr hilfreich. Ich habe eben das Verfahren Inklusion Exklusion noch nie konkret angewendet, habs nur so intuitiv verstanden gehabt...
Noch eine Unklarheit:
[mm] \vektor{6 \\ 2 } [/mm] = [mm] \vektor{6 \\ 4} [/mm] bzw. das entspricht der möglichkeiten Eben vier Kästchen von 6 auszusuchen. Dies Multiplitiert mit 4!. Macht mal sicher Sinn!
Jetzt aber die Multiplikation mit 3. Müsste das nicht (manchmal) eine mit 4 sein?
Ist es nicht eher so:
[mm] |A_{1} \cap A_{2}| [/mm] = $ = [mm] \{\omega_1 = 1,\omega_2 = 2\} \cup \{\omega_1=1,\omega_2 =3\} \cup \{\omega_1=2,\omega_2=2\} \cup \{\omega_1=2,\omega_2=3\} [/mm] $ = 4! + 4! + 4! + 4!
Bzw. [mm] \{\omega_1=2,\omega_2=2\} [/mm] = 4! [mm] \not= [/mm] 0
Ausserdem, selbst wenn das gleich 0 ist, so ist es zuminedest nur Null für Schnitte deren Indexe nebeneinander liegen, sich also mit einer Addition um 1 unterscheiden, nicht?!
z.B. [mm] |A_{1} \cap A_{3}| [/mm] = 4*4!, es treten ja keine gleichen Zahlen in diesen Spalten auf.
Oder?
Gruss
|
|
|
| |
|
Huhu,
> Bzw. [mm]\{\omega_1=2,\omega_2=2\}[/mm] = 4! [mm]\not=[/mm] 0
nein, denn der Fall kann nicht auftreten, da die 2 nur einmal vergeben werden kann.
> Ausserdem, selbst wenn das gleich 0 ist, so ist es
> zuminedest nur Null für Schnitte deren Indexe
> nebeneinander liegen, sich also mit einer Addition um 1
> unterscheiden, nicht?!
Korrekt, das hab ich dezent unterschlagen.
D.h. es sind doch nicht alles symmetrische Fälle..... macht die Sache zwar nicht schwieriger, nur schreibaufwendiger.
>
> z.B. [mm]|A_{1} \cap A_{3}|[/mm] = 4*4!, es treten ja keine gleichen
> Zahlen in diesen Spalten auf.
>
> Oder?
Jop, gut erkannt und zeigt, dass du die Sache verstanden hast
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:48 Sa 27.11.2010 | | Autor: | qsxqsx |
Na dann will ich mal loslegen und mich ans Ergebnis wagen, dass zu 90% aus einem Rechenfehler besteht. Es ist besser du überprüfst nicht zu genau, es geht ja nur ums Prinzip:
Lösung M der Anzahl Möglichkeiten diese 6 Zahlen anzuordnen:
M = 6! - [mm] |\bigcup_{i=1}^{6} A_{k}|
[/mm]
... = 6! - [ [2*6!] - [ 6 *4!*3 + ( [mm] \vektor{6 \\ 4} [/mm] -6 )*4!*4] + [ 2 *3!*8 + 6 *3!*4 +( [mm] \vektor{6 \\ 3} [/mm] - 8 )*3!*6] - [ 6 *2!*5 + 3 *2!*9 + 6 *2!*8] + [ 6 *1!*6] - [ 1 *0!*2] ] = ...
Abfolge ist immer die Gleiche: "rote Zahl"*"Fakultät"*"Häufigkeit"
"Rote Zahlen":
-Die Roten Zahlen geben an, wie viel mal eine Kombination von Spalten Vorkommt. Also zum Beispiel wenn 6 mal die Menge [mm] A_{k} [/mm] und [mm] A_{n} [/mm] sich nur um eins unterscheiden, also k + 1 = n, so ist die Rote Zahl eben 6. Also wenn die Spalten nebeneinander liegen.
"Fakultät":
- Die Fakultät gibt die Möglichkeiten an, die freien plätze zu besetzen.
"Häufigkeit":
- Die dritte Zahl in so einem Pack, gibt immer an, wie oft denn jetzt diese Schnittmenge entstehen kann.
Beispiel:
Sind zum Beispiel 3 Spalten immer nebeneinander, also die Rote Zahl ist gleich 6 weil es 6 Möglichkeiten gibt, 3 Spalten auszusuchen die nebeneinander sind. Die Fakultät ist gleich 3!, weil 3 freie Felder existieren, wobei die anderen 3 eben durch die 3 Spalten gebraucht werden.
Die Häufigkeit berechnet sich dann so, wenn man zum Beispiel die ersten 3 Spalten, a,b,c betrachtet:
1,2,3/1,2,4/1,3,4/2,3,4 ---> 4
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:47 Sa 27.11.2010 | | Autor: | qsxqsx |
Lustig, ich habe jetzt ein Programm geschrieben, dass es berechnet. Es kommt auf 80!!! Und die Errechnete Lösung kommt auch auf 80!!! Es stimmt sogar!!!
Danke dir!!!
Gruss
|
|
|
| |
|
Na dann ist die Frage ja beantwortet.
Prima !
War zu faul das alles bisher klein klein nachzurechnen
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:38 Sa 27.11.2010 | | Autor: | qsxqsx |
// Hier das Programm, für den ders haben will; )
#include <iostream>
using namespace std;
int main() {
int m = 0; // Möglichkeitenzähler
int arrayeins[] = {1,2,3,4,5,6};
int arrayzwei[] = {2,3,4,5,6,1};
int temparray[] = {0,0,0,0,0,0};
for(int u = 1; u < 7; u ++){
temparray[0] = u;
for(int r = 1; r < 7; r++){
temparray[1] = r;
for(int w = 1; w < 7; w++){
temparray[2] = w;
for(int q = 1; q < 7; q++){
temparray[3] = q;
for(int a = 1; a < 7; a++){
temparray[4] = a;
for(int x = 1; x < 7; x++){
temparray[5] = x;
// Array auf gleiche Zahlen vergleichen, ausfiltern
int s = 0;
for(int i = 0; i < 6; i ++){
if(arrayeins[i]==temparray[i] || arrayzwei[i]==temparray[i]){
s = s + 1;
}
}
if(s == 0) {
int c = 0;
for(int zahl = 1; zahl < 7; zahl++){
int b = 0;
while ( (temparray[b] != zahl) && (b < 7)){
b++;
}
if(b < 7){
c = c+1;
}
if(c == 6){
m = m+1;
}
}
}
}
}
}
}
}
}
cout << m;
system("PAUSE");
return 0;
}
|
|
|
|
