nicht angemeldet
Hello,
Ups, es ist doch fakultät(n-1)
Wie kann man darauf nun auf einen Blick kommen?
Harzliche Grüße aus http://www.annerschbarrich.de
Tom
Hehe, also (n-1)! isses nicht. Das kann man sich für das überschaubare Beispiel von 4 Matrosen und 4 Matten vergegenwärtigen ( da gibt es 9 Möglichkeiten ).
Nach Engagieren meines Mathenachbarn kamen wir auf folgende Lösung, die mit ziemlich hoher Wahrscheinlichkeit stimmt:
b(0) = 1
b(n) = n! - sum[k=1...n] { (n über k) * b(n-k) }
Naja, da kommt man jetzt nicht so leicht drauf, is klar ;) Die n! am Anfang repräsentieren alle Permutationen. Von diesen ziehen wir nun die ab, bei denen mind. 1 Matrose auf seiner Matte liegt (das ab dem Summensymbol). In der Summe wird die Anzahl der Permutationen dafür berechnet, dass genau k=1 bis k=n Matrosen ihre Matte finden. Nun bekomme ich mit (n über k) genau die Anzahl von Belegungen, dass genau k Matten richtig belegt sind. Diese muss ich dann noch mal nehmen mit der Anzahl der Permutationen, dass die übrigen n-k falsch belegten Matten auf b(n-k)-verschiedene Art und Weisen komplett falsch belegt sind (Rekursion).
So kommt man auf folgenden Java-Code, der noch den Erwartungswert für die durchschnittl. richtig belegten Matten ausgibt.
---------------------
public class matrosen
{
public matrosen(){}
public static int fak( int n )
{
if( n == 0) return 1;
else
{
for( int i = n-1; i>1; i-- ) n *= i;
return n;
}
}
public static int ueber( int n, int k )
{
return ( fak(n) / ( fak(n-k)*fak(k) ) );
}
public static int jo( int n )
{
if( n == 0 ) return 1;
else
{
int erg = 0;
for( int i=1; i<=n; i++ ) erg += ueber( n, i ) * jo( n-i );
erg = fak(n) - erg;
return erg;
}
}
public static int ew( int n )
{
int erg = 0;
for( int i=0; i<=n; i++ ) erg += ueber(n,i) * jo(i) * (n-i);
erg /= fak(n);
return erg;
}
public static void main( String args[] )
{
for( int i=0; i<=5; i++ )
{
System.out.println( i+" Matrosen koennen auf "+jo(i)+" moegliche Art und Weisen auf "+i+" Matten verteilt werden, sodass keiner seine eigene Matte belegt." );
System.out.println( "Durchschnittlich belegen "+ew(i)+" von "+i+" Matrose(n) ihre eigenen Matten.\n" );
}
}
}
--------------------------
Greets, *jiriki*