Fixpunktfreie Permutation: Wie hoch ist die Chance mehrfach dem selben Partner zugelost zu werden?

Schlangenmensch

Hallo zusammen,

ich sitze (vor allem spaßeshalber) an folgender Überlegung:

Ich habe 44 Leute zufällig aufgeteilt auf 22 Paare. Wenn ich die Aufteilung wiederhole, wie hoch ist die Chance, dass ein Paar mehrfach auftaucht.

Also, ich habe eine initiale Verteilung. Da kann noch kein Paar doppelt vorkommen. Dann bei der 2. Ziehung habe ich eine Chance von
$p=\frac{!22}{22!}\approx 0.37$ dass kein Paar doppelt ist.
Also, ist die Chance, dass mindestens ein Paar doppelt ist:
$1-p \approx 0.63$
Bei 22 Paaren, ist die Wahrscheinlichkeit, dass es ein bestimmtes Paar trifft dann
$0.63/22 \approx 0.028$
Beim der nächsten Runde, wäre die Wahrscheinlchkeit, dass es genau dieses Paar wieder trifft dann
$0.028 * 0.028 = 0.000784$

Passt das bis hier?

Wo ich grade ein bisschen auf dem Schlauch stehe, wenn ich n mal durchwürfel, wie hoch ist die Wahrscheinlichkeit, dass ein Paar x-mal vorkommt (muss nicht im Stück sein )?

Man, habe ich lange keine Kombinatorik mehr gebraucht....

wob

Moin,

kannst du mir erklären, was !22 ist? 22! kenne ich. Aber die Schreibweise mit ! vor der Zahl ist habe ich noch nie gesehen.

Ich habe mal einen kleinen Simulator geschrieben. Komme damit bei 44 Personen aber auf eine Wahrscheinlichkeit von 40%, dass es ein Paar doppelt gibt.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

int main(int argc, char **argv) {
    if (argc < 2) {
        std::cerr << "Bitte nPersonen (und optional nRuns) übergeben!\n";
        return 2;
    }
    auto nPersonen = std::stoi(argv[1]);
    if (nPersonen & 1) {
        std::cerr << "Personenzahl muss gerade sein.\n";
        return 2;
    }
    auto nRuns = (argc > 2) ? std::stoi(argv[2]) : 10 * nPersonen;

    std::vector<int> personen(nPersonen);
    std::iota(begin(personen), end(personen), 0);

    std::mt19937 pseudorandom(std::random_device{}());

    int n0 = 0, nHasMatch = 0;
    for (int iRun = 0; iRun < nRuns; ++iRun) {
        std::shuffle(begin(personen), end(personen), pseudorandom);

        int nMatches = 0;
        for (size_t i = 0; i < personen.size(); i += 2) {
            if (personen[i + 1] < personen[i])
                std::swap(personen[i + 1], personen[i]);
            if (((personen[i] & 1) == 0) && (personen[i] + 1 == personen[i + 1])) {
                ++nMatches;
                break;  // wenn man an der Anzahl interessiert ist, dieses break entfernen
            }
        }

        if (nMatches)
            ++nHasMatch;
        else
            ++n0;
    }
    std::cout << "Kein Match: " << n0 << ", Match: " << nHasMatch << ", d.h. "
              << (100.0 * nHasMatch / (nHasMatch + n0)) << "% Fälle mit Match.\n";
}

Schlangenmensch

!n ist die Subfakultät:
${!}n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = n! \cdot \left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+ \cdots +(-1)^n\frac{1}{n!}\right)$ (https://de.wikipedia.org/wiki/Subfakultät).

Ich glaube, meine Grundannehme, das Problem über die Fixpunktfreie Permutation lösen zu können, war falsch. Das würde stimmen, wenn ich z.B. 22 Tanzpaare aus Männern und Frauen habe und dazu annehme, dass ein Paar aus einem Mann und einer Frau besteht.

Danke für die Simulation, hatte ich auch drüber nachgedacht, wäre wahrscheinlich einfacher und schneller gewesen, als meine theroetischen Überlegungen.

wob

Wenn $p = \frac{!n}{n!}$ bei $n$ Paaren wäre und du $n=2$ einsetzt, dann käme da $p=1/2$ raus.

Du kannst aber die Paare nur so losen:

(1 2) (3 4)
(1 3) (2 4)
(1 4) (2 3)

Es gibt also drei Möglichkeiten zu losen - die Wahrscheinlichkeit ist hier offensichtlich 1/3, dass man mindestens 1 doppeltes Paar hat (und in diesem Fall hat man dann auch gleich 2 gleiche Paare).