Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Inklusion-Exklusions-Prinzip genau s Eigenschaften

Inklusion-Exklusions-Prinzip genau s Eigenschaften

Universität / Fachhochschule

Binomialkoeffizienten

Inklusion-Exklusion

Tags: Binomialkoeffizient, Inklusion-Exklusion

Melila aktiv_icon

11:06 Uhr, 15.04.2022

Ich versuche die Verallgemeinerung des Inklusion-Exklusions-Prinzip mit genau s Eigenschaften zu verstehen. Dazu schau ich mir ein Beispiel an und zwar: Wie viele Möglichkeiten gibt es, dass genau s Personen (von insgesamt n Personen) ihren Mantel zurückbekommen (die ihre Mäntel vorher abgegebenen haben zufällig wieder ausgegeben werden)?

Man kann auch Teilmengen von der Menge N={1,...,n}(Anzahl der Personen definieren) und zwar:

N_{1}

= {Person 1 an Stelle 1} (d.h. Person eins bekommt seinen Mantel zurück, da er an der ersten Stelle ist, bei den anderen ist es egal ob sie in der Menge zurückbekommen oder nicht.)

N_{2}

= {Person 1 an Stelle 1} (d.h. Person zwei bekommt seinen Mantel zurück, da er an der zweite Stelle ist, bei den anderen ist es egal ob sie in der Menge zurückbekommen oder nicht.)
Das kann man so weiter führen bis.

N_{n}

= {Person n an Stelle n} (d.h. Person n bekommt seinen Mantel zurück)

Wenn man das definiert habe ich für die Anzahl, dass genau s Personen ihren Mantel zurück bekommen mit der folgenden Summe berechnet wird:

\sum_{t = s}^{n} (- 1)^{t - s} (\binom{t}{s}) (\binom{n}{t}) (n - t)!

.
Die

(\binom{n}{t}) (n - t)!

sind doch die derangements.
Aber wie kann ich hier die

(\binom{t}{s})

interpretieren und verstehen.
Also ich brauche keine Mathematische Herleitung, nur eine Intuitive Erklärung wie ich die Formel interpretieren kann.

Vielen Dank

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

HAL9000

18:18 Uhr, 15.04.2022

Für das von dir geschilderte Mantelproblem bedarf es keines verallgemeinerten Inklusion-Exklusions-Prinzips, das "normale" genügt:

1) Wir betrachten den Fall, dass die

(n - s)

Personen

1, \dots, n - s

ihren Mantel NICHT bekommen, die

s

Personen

n - s + 1, \dots, n

hingegen schon. Das ergibt mit der Inklusion-Exklusions-Formel die Anzahl

N_{1} = \sum_{j = 0}^{n - s} {(- 1)}^{j} (\begin{array}{c} n - s \\ j \end{array}) \cdot (n - s - j)! = (n - s)! \cdot \sum_{j = 0}^{n - s} \frac{{(- 1)}^{j}}{j!}

2) Die Betrachtung 1) kann man wiederholen für jede andere Zuteilung der

s

Positionen für die "richtigen" Mäntel auf

1, \dots, n

. Da hier Disjunktheit vorliegt, gilt somit einfach

N_{2} = (\begin{array}{c} n \\ s \end{array}) \cdot N_{1} = \frac{n!}{s!} \cdot \sum_{j = 0}^{n - s} \frac{{(- 1)}^{j}}{j!}

für die von dir gesuchte Anzahl. Das stimmt mit Indexverschiebung

j = t - s

exakt mit deiner Formel überein. ;-)

Melila aktiv_icon

00:42 Uhr, 17.04.2022

Vielen Dank.
Aber ich wollte keine Mathematische Herleitung (ich kenn die bereits schon). Ich wollte nur eine intuitive Erklärung meiner Formel. Dadurch kann ich immernoch nicht meine eigene Formel interpretieren.

Kartoffelchipsman aktiv_icon

02:25 Uhr, 17.04.2022

Zunächst mal überzeuge ich mich, kleinschrittig notiert,

dass Deine und HALs Formel äquivalent sind,

was mit Deiner Frage zwar erstmal nichts zu tun hat,

aber Ordnung muss sein...

\sum_{t = s}^{n} {(- 1)}^{t - s} \cdot (\begin{matrix} t \\ s \end{matrix}) \cdot (\begin{matrix} n \\ t \end{matrix}) \cdot (n - t)!

= \sum_{t = 0}^{n - s} {(- 1)}^{t} \cdot (\begin{matrix} t + s \\ s \end{matrix}) \cdot (\begin{matrix} n \\ t + s \end{matrix}) \cdot (n - t - s)!

= \frac{n!}{s!} \cdot \sum_{t = 0}^{n - s} {(- 1)}^{t} \cdot \frac{(t + s)!}{t!} \cdot \frac{1}{(n - t - s)! \cdot (t + s)!} \cdot (n - t - s)!

= (\begin{matrix} n \\ s \end{matrix}) \cdot \sum_{t = 0}^{n - s} {(- 1)}^{t} \cdot \frac{(t + s)!}{t!} \cdot \frac{(n - s)!}{(n - t - s)! \cdot (t + s)!} \cdot (n - t - s)!

= (\begin{matrix} n \\ s \end{matrix}) \cdot \sum_{t = 0}^{n - s} {(- 1)}^{t} \cdot \frac{(t + s)!}{(t + s)!} \cdot \frac{(n - s)!}{(n - t - s)! \cdot t!} \cdot (n - t - s)!

= (\begin{matrix} n \\ s \end{matrix}) \cdot \sum_{t = 0}^{n - s} {(- 1)}^{t} \cdot (\begin{matrix} n - s \\ s \end{matrix}) \cdot (n - t - s)!

.

Diese letzte Formel ist, auch wegen dem drangepappten

(\begin{matrix} n \\ s \end{matrix}),

sehr schön erklärbar, wie HALs Beitrag ja zeigt

(und dazu Wikipedia: de.m.wikipedia.org/wiki/Fixpunktfreie_Permutation ) .

Bei Deiner Version würde ich es (mir) so zu erklären versuchen:

In

\sum_{t = s}^{n} {(- 1)}^{t - s} \cdot (\begin{matrix} t \\ s \end{matrix}) \cdot (\begin{matrix} n \\ t \end{matrix}) \cdot (n - t)!

bedeutet das

(\begin{matrix} n \\ t \end{matrix}) \cdot (n - t)!

jeweils (die Anzahl der Möglichkeiten),

dass

t

oder mehr Leute ihren Mantel zurückbekommen,

und in

(\begin{matrix} t \\ s \end{matrix}) \cdot (\begin{matrix} n \\ t \end{matrix}) \cdot (n - t)!

faktorisiert dann das

(\begin{matrix} t \\ s \end{matrix})

nochmal jede der

(\begin{matrix} n \\ t \end{matrix})

Auswahlen von

t

aus

n

Leuten um die

(\begin{matrix} t \\ s \end{matrix})

Möglichkeiten, darin wiederum

s

Leute zu wählen.

Die Inklusion-Exklusion (also die alternierende Summe von

s

bis

n)

schafft die "oder mehr" wieder weg, fertig.

Aber meiner Meinung nach bleibt Deine Version der Formel

trotz allem Erklärbär am Ende einfach die weniger anschauliche...

HAL9000

10:43 Uhr, 18.04.2022

> Ich wollte nur eine intuitive Erklärung meiner Formel. Dadurch kann ich immernoch nicht meine eigene Formel interpretieren.

Das klingt für micht irgendwie absurd: Wenn man selbst eine Formel aufstellt, dann sollte man sie auch erklären können. Wenn man das nicht schafft, dann sollte man versuchen, die Herleitungen anderer zu verstehen.

--------------------------------------------------------------------------------

Ok, allgemeine Situation: Seien

A_{1}, \dots, A_{n}

endliche Mengen sowie

0 \leq s \leq n

. Dann mögen alle Elemente, die in GENAU

s

der

n

Mengen

A_{1}, \dots, A_{n}

enthalten sind die Menge

B_{s}

bilden. Gemäß Prinzip von Inklusion und Exklusion kann man mit

M_{n} := {1, \dots, n}

die Formel

∣ B_{s} ∣ = ⋃_{I \subseteq M_{n}, ∣ I ∣ = s} ⋃_{J \subseteq M_{n} \ I} {(- 1)}^{∣ J ∣} \cdot ∣ ⋂_{j \in I \cup J} A_{j} ∣ (1)

.

Kann man auch umschreiben zu

∣ B_{s} ∣ = ⋃_{I \subseteq M_{n}, ∣ I ∣ = s} ⋃_{I \subseteq T \subseteq M_{n}} {(- 1)}^{∣ T ∣ - s} \cdot ∣ ⋂_{j \in T} A_{j} ∣ (2)

,

oder noch anders

∣ B_{s} ∣ = ⋃_{I \subseteq M_{n}, ∣ I ∣ = s} ⋃_{t = s}^{n} ⋃_{I \subseteq T \subseteq M_{n}, ∣ T ∣ = t} {(- 1)}^{t - s} \cdot ∣ ⋂_{j \in T} A_{j} ∣ (3)

.

Gut, das kann man natürlich erstmal beweisen, dann auch die hier vorliegende Situation anwenden, und solange rumbasteln, bis es deiner Formel entspricht. Die Frage ist, warum man so umständlich vorgehen sollte, wenn es doch auch einfacher geht?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1555217

1555108

	Status: nicht eingeloggt	Noch nicht registriert?