forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 22 Σεπ 2017, 20:57

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 2 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: βοηθεια σε ασκηση
ΔημοσίευσηΔημοσιεύτηκε: 06 Μαρ 2016, 23:20 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 16 Ιούλ 2011, 15:43
Δημοσ.: 221
έστω Ν στρατιώτες πυροβολούν Ν κατάδικους. 1. Κάθε στρατιώτης πυροβολεί ακριβώς ένα κατάδικο και είναι 100% εύστοχος. 2. Κανένας κατάδικος δεν πυροβολείται από περισσότερους από ένα στρατιώτη . Ποια η πιθανότητα k στρατιώτες να πυροβολήσουν τους κατάδικους που είναι απέναντι τους; Δηλαδή, ποια η πιθανότητα μια τυχαία μετάθεση να έχει k σταθερά σημεία;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: βοηθεια σε ασκηση
ΔημοσίευσηΔημοσιεύτηκε: 13 Μαρ 2016, 21:53 
Χωρίς σύνδεση

Εγγραφη: 11 Δεκ 2014, 19:45
Δημοσ.: 48
Αρχικά ας θυμηθούμε ποιό είναι το πλήθος των μεταθέσεων w \in \mathfrak{S}_{n} χωρίς σταθερά σημεία. Ας συμβολίσουμε το πλήθος αυτό με D_{n}. Για να υπολογίσουμε το D_{n} θα χρησιμοποιήσουμε την αρχή εγκλεισμού-αποκλεισμού :
Για υποσύνολα A_{1}, A_{2}, \cdots, A_{n} πεπερασμένου συνόλου X ισχύει \#(X \setminus \bigcup_{i=1}^{n}A_{i}) = \sum_{I \subseteq [n]}(-1)^{\#I} \#\bigcap_{i \in I}A_{i}, όπου κατά σύμβαση έχουμε \bigcap_{i \in I}A_{i} = X, για I = \varnothing.
Για να την εφαρμόσουμε, ας θέσουμε A_{i} =\{ w \in \mathfrak{S}_{n} : w(i) = i\}, για i \in [n]. Έτσι D_{n} = \# (\mathfrak{S}_{n} \setminus \bigcup_{i=1}^{n}A_{i}). Μένει να παρατηρήσουμε τώρα ότι για κάθε υποσύνολο I \subseteq [n] η τομή \bigcap_{i \in I}A_{i} είναι ίση με το σύνολο των μεταθέσεων της \mathfrak{S}_{n} για τις οποίες καθένα από τα στοιχεία του I είναι σταθερό σημείο. Με άλλα λόγια, αν \#I = k, τότε \#\bigcap_{i \in I}A_{i} = (n-k)!, όσες δηλαδή είναι οι μεταθέσεις του συνόλου [n] \setminus I. (Θυμίσου ότι η ομάδα των μεταθέσεων ενός συνόλου δεν εξαρτάται από τη φύση των στοιχείων του συνόλου αυτού, αλλά από το πλήθος των στοιχείων του) Άρα,

D_{n} = \sum_{I \subseteq [n]}(-1)^{\#I} \#\cap_{i \in I}A_{i} = \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} (n-k)! = \sum_{k=0}^{n} (-1)^{k}\frac{n!}{k!}.

και γι αυτό D_{n} = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^{n}}{n!}). (πώς προέκυψε ο διωνυμικός συντελεστής \binom{n}{k} στο παραπάνω ανάπτυγμα;)

Τώρα ας υπολογίσουμε το πλήθος των μεταθέσεων w \in \mathfrak{S}_{n} με k σταθερά σημεία. Παρατηρούμε ότι υπάρχουν \binom{n}{k} διαφορετικοί τρόποι για να επιλέξουμε το σύνολο των σταθερών σημείων μιας μετάθεσης w \in \mathfrak{S}_{n} (γιατί;). Για κάθε τέτοια επιλογή συνόλου k σταθερών σημείων, θέλουμε οι υπόλοιπες είσοδοι της μετάθεσης να μη σχηματίσουν κανένα σταθερό σημείο, το οποίο μπορεί να γίνει με D_{n-k} τρόπους, όσες δηλαδή είναι οι μεταθέσεις του [n-k] (τα k σημεία που λείπουν αντιστοιχούν στα σταθερά σημεία της μετάθεσης που επιλέξαμε) χωρίς κανένα σταθερό σημείο. Άρα, από τη πολλαπλασιαστική αρχή έπεται ότι το ζητούμενο πλήθος είναι
\binom{n}{k}D_{n-k} = \binom{n}{k}(n-k)! (1- \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^{n-k}}{(n-k)!}).

_________________
"Problems worthy of attack prove their worth by fighting back" -Paul Erdős


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 2 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group