Bijektion gesucht

13.05.2019, 11:52

Mathematiker9998

Bijektion gesucht

Meine Frage:
Hallo,

ich habe folgendes Problem:

Gegeben sind alle Binaerzahlen mit n Stellen und einer beliebigen, aber festen Anzahl k an Einsen (z.B. für n=4 und k=2: 1001, 1100, 0011, 0110, 1010, 0101). Bezeichne diese Mengen als M(n;k). Ich suche nun eine Bijektion zwischen den M(n;k) und den natürlichen Zahlen (z.B. für n=4 und k=2: 0, 1, 2, 3, 4, 5). Ich möchte die Elemente der Mengen M(n;k) also durchnummerieren. Das ganze soll in ein Programm umgesetzt werden, daher wäre es sinnvoll eine (kompakte!) Zuordnungsvorschrift anzugeben.

Meine Ideen:
Leider habe ich keine Idee, ich hab schon versucht mit Modulo-Tabellen zu arbeiten, bin daran aber gescheitert.

13.05.2019, 12:24

HAL 9000

Auf diesen Beitrag antworten »

Nun, es ist $\begin{eqnarray*} |M(n;k)|=\binom{n}{k} \end{eqnarray*}$ . "Durchnummerieren" ist schwierig, aber alle Varianten algorithmisch ausgeben ist nicht so schwer, im Pseudocode

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

M(n, k, string)
{
   if (n == 0)
   {
       print(string);
   }
   else
   {
       if (k < n)
       {
           M(n-1, k, string + "0");
       }
       if (k > 0)
       {
           M(n-1, k-1, string + "1");
       }
   }
}

Aufruf dieser rekursiven Funktion mit M(n,k,""); erlaubt ist natürlich nur $\begin{eqnarray*} 0\leq k\leq n \end{eqnarray*}$ .

Neue Frage »

Antworten »

Bijektion gesucht

Verwandte Themen