forum.math.uoa.gr

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

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




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 11 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 06 Απρ 2017, 01:19 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Παράθεση:
Θεώρημα

Για υποσύνολα A_1,A_2, ...,A_n πεπερασμένου συνόλου S έχουμε:

\#\left (S- \bigcup_{i=1}^{n}A_i \right )=\sum_{1\leq i_1<i_2<...<i_k\leq n }(-1)^k\#A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}}


Δυσκολεύομαι να καταλάβω τι λέει το αθροισμα. Εννοώ καταλαβαίνω τι λεει η αρχή εγκλεισμού απόκλεισμού, αλλά δεν μπορώ να κατανοήσω πως δουλεύει το άθροισμα αυτό στο δεξί μέλος.

Έκανα μια προσπάθεια μήπως καταφέρω να το φέρω στην μορφή αυτή φτιάχνοντας τετοια αθροίσματα , αλλά πάλι δεν καταλαβα.
Μπορεί κάποιος να το εξηγήσει

Εικόνα


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 06 Απρ 2017, 10:43 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Ή έστω κανένα link για να καταλάβω τον συμβολισμό αυτού του αθροίσματος.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 06 Απρ 2017, 13:22 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 25 Σεπ 2007, 17:31
Δημοσ.: 4227
Όλοι οι δυνατοί συνδυασμοί από το 1 εώς το ν, ανά 1 εώς ν διχως επανάληψη
εναλάξ - και +
πχ για το 1,2,3
είναι τα
(1,2,3) συνδυαμός ν ανα ν=3
(1,2) (1,3), (2, 3) συνδυαμός ν=3 ανα ν-1=2
(1) (2), (3) συνδυαμός ν=3 ανα ν-2=1

_________________
https://www.youtube.com/watch?v=wbZuBDJVHEI


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 06 Απρ 2017, 14:03 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Ας πούμε ότι n=1
έχουμε ότι:

\#\left (S- A_1 \right )=\#S-\#A_1

Από τον τυπο, σε εκεινο το άθροισμα πως προκύπτει το \#S ?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 06 Απρ 2017, 19:08 
Χωρίς σύνδεση

Εγγραφη: 11 Δεκ 2014, 19:45
Δημοσ.: 48
Παρατήρησε ότι στο δεξί μέλος της αρχής Ε.-Α. το άθροισμα τρέχει πάνω από όλα τα υποσύνολα του [n].
Πιο συγκεκριμένα, αν είχαμε n=3, τότε

για k=0 έχουμε κατά σύμβαση A_{i_{1}} \cup \cdots A_{i_{k}} = S (αυτό περιέχεται στην εφώνηση του θεωρήματος!)

για k =1 έχουμε 3 υποσύνολα με ένα στοιχείο, οπότε 1 \leq i_{1} \leq 3 και γι αυτό εμφανίζονται τα A_{1}, A_{2}, A_{3}

για k=2 έχουμε 3 υποσύνολα με δυο στοιχεία, οπότε τα (i_{1}, i_{2}) με 1 \leq i_{1} < i_{2} \leq 3 είναι τα (1,2), (1,3) και (2,3) και γι αυτό εμφανίζονται τα A_{1} \cap A_{2}, A_{1} \cap A_{3}, A_{2} \cap A_{3}

τέλος, για k=3 έχουμε 1 υποσύνολο με τρία στοιχεία, οπότε τα (i_{1}, i_{2}, i_{3}) με 1 \leq i_{1} < i_{2} < i_{3}\leq 3 είναι μόνο ένα το (1,2,3) και έτσι εμφανίζεται το A_{1} \cap A_{2} \cap A_{3}.

Με άλλα λόγια αυτό που λέμε είναι ότι η αρχή Ε.-Α. μπορεί να πάρει την μορφή

\#(S \setminus \bigcup_{i=1}^{n}A_{i}) = \sum_{I \subseteq [n]} (-1)^{\#I} \#\bigcap_{i \in I}A_{i}.

Ο παραπάνω τύπος δεν είναι τίποτα άλλο από μια συμπαγή μορφή του εξής τύπου
\#(S \setminus \bigcup_{i=1}^{n}A_{i}) = \#S - \sum_{k=1}^{n}\#A_{k} + \sum_{1 \leq i < j \leq n} \#(A_{i} \cap A_{j}) - \cdots + (-1)^{n}\#(A_{1} \cap \cdots \cap A_{n})

Μπορείς να συμβουλευτείς τις σημειώσεις του Αθανασιάδη για τα διακριτά μαθηματικά στο κεφάλαιο 1.4.

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 07 Απρ 2017, 00:09 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Φίλε σε ευχαριστώ πάρα πολυ, επιτέλους το κατάλαβα!! το εξήγησες πολύ αναλυτικά!!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 10 Απρ 2017, 17:24 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 31 Αύγ 2010, 23:42
Δημοσ.: 120
γιατι στις σημειωσεις αθανασιαδη ο τυπος στο δεξιο μελος εχει διπλο αθροισμα ενω στις τωρινες σημειωσεις μονο?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 13 Απρ 2017, 12:42 
Χωρίς σύνδεση

Εγγραφη: 11 Δεκ 2014, 19:45
Δημοσ.: 48
plk έγραψε:
γιατι στις σημειωσεις αθανασιαδη ο τυπος στο δεξιο μελος εχει διπλο αθροισμα ενω στις τωρινες σημειωσεις μονο?


Έχεις δίκιο, δε το παρατήρησα, χρειάζεται και ένα επιπλέον άθροισμα στις σημειώσεις του bodom, που να τρέχει το 0 \leq k \leq n, ακριβώς επειδή τα υποσύνολα του [n] έχουν 0, 1, \cdots, n στοιχεία.

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 15 Απρ 2017, 12:41 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Και κάτι τελευταίο αν είναι εύκολο... Στην απόδειξη που έδωσε στο μάθημα (ίδια με τις δικές του σημειώσεις απο την ιστοσελίδα του) σε ένα σημείο δεν την καταλαβαίνω.

Για αυτό πήρα ένα σύνολο S με 4 στοιχεία,
S=\{a_{11},a_{12},a_{21},a_{22}\} και προσπάθησα να εφαρμόσω πάνω σε αυτό την απόδειξη που δίνει.

Στο σημείο που έχω βάλει αστερίσκο είχε πει οτι:
"το γινόμενο αυτό μπορώ να το αναπτύξω χρησιμοποιώντας την επιμερηστική ιδιότητα"
και μετά είπε οτι
"απο κάθε παρένθεση διαλέγω είτε το 1 είτε το -x_i(x)"

Δηλαδή δυσκολεύομαι να καταλάβω πως πάει απο το

\sum_{x\in S}\prod_{i=1}^{2}(1-x_i(x)))\,\, =\,\, \sum_{x\in S}\sum_{I\subseteq [2]}(-1)^{\#I}\prod_{i\in I}x_i(x)

Εικόνα


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 15 Απρ 2017, 17:59 
Χωρίς σύνδεση

Εγγραφη: 11 Δεκ 2014, 19:45
Δημοσ.: 48
Παρατήρησε ότι για κάθε 1 \leq i \leq n, η συνάρτηση \chi_{i} δεν είναι τίποτε άλλο παρά η χαρακτηριστική συνάρτηση του A_{i}, ας τη συμβολίσουμε \chi_{A_{i}}. Τότε για $n = 3$, για παράδειγμα έχουμε

\prod_{i=1}^{3}(1-\chi_{A_{i}})= (1-\chi_{A_{1}})(1-\chi_{A_{2}})(1-\chi_{A_{3}})

= 1 - \chi_{A_{1}} - \chi_{A_{2}} - \chi_{A_{3}} + \chi_{A_{1}}\chi_{A_{2}} + \chi_{A_{1}}\chi_{A_{3}} + \chi_{A_{2}}\chi_{A_{3}} - \chi_{A_{1}}\chi_{A_{2}}\chi_{3}},

χρησιμοποιώντας επιμεριστικότητα. Παρατήρησε ότι έχουμε αμφιμονοσήμαντη αντιστοιχία μεταξύ των όρων του παραπάνω γινομένου (που έγινε άθροισμα μετά τον επιμερισμό) και των υποσυνόλων του [3], με τους συντελεστές μπροστά από κάθε προσθεταίο να είναι \pm 1 ανάλογα με το πλήθος των στοιχείων που έχει το αντίστοιχο υποσύνολο του [3].

Με άλλα λόγια, η άσκηση που πρέπει να λύσεις είναι να δείξεις ότι ο συντελεστής του x_{1}x_{2}\cdots x_{k} στο πολυώνυμο p(x_{1}, x_{2}, \cdots, x_{n}) = (1-x_{1})(1-x_{2})\cdots(1-x_{n}) \in \mathbb{R}[x_{1},\cdots,x_{n}] είναι ο (-1)^{k} ή διαφορετικά ότι

\prod_{i=1}^{n}(1-x_{i}) = 1 + \sum_{k=1}^{n}(-1)^{k}\sum_{1 \leq i_{1} < i_{2} < \cdots < i_{k} \leq n}x_{i_{1}}x_{i_{2}}\cdots x_{i_{k}}.

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ ΑΠΟΚΛΕΙΣΜΟΥ - ΘΕΩΡΗΜΑ
ΔημοσίευσηΔημοσιεύτηκε: 16 Απρ 2017, 20:52 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Φεβ 2011, 11:45
Δημοσ.: 221
Ναι, βγάζει νόημα τώρα! Κολάω πολύ σε αυτά και δεν μπορώ να περάσω σελίδα αμα δεν το έχω καταλάβει καλά!! :thumbup: Σε ευχαρστώ πολύ και πάλι για τον χρόνο σου!!!


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

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


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

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


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

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