Συνδυαστική

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

Αρχείο:Arbores.jpg

Δέντρο με οθόνες που εμφανίζει ένα πρόγραμμα στην οθόνη του υπολογιστή.

Έστω ένα σύνολο στοιχείων Α, το οποίο έχει ν στοιχεία. Έστω ένας δοσμένος αριθμός κ και μια τυχαία κ-άδα (α₁,α₂,...,α_κ). Έστω το σύνολο Α' των κ-άδων για τους οποίους ισχύει η πρόταση Π. Η συνδυαστική ασχολείται με την εύρεση του πλήθους των στοιχείων του Α', όταν η πρόταση Π αναφέρεται σε διάταξη μεταξύ των στοιχείων του Α. Αυτό γίνεται σε συνδυασμό με κάποια διαγράμματα που ονομάζονται δέντρα.

Σφάλμα στη δημιουργία μικρογραφίας:

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

Βασικός κανόνας απαρίθμησης:

Έστω ότι υπάρχουν κ περιπτώσεις, όπου η πρώτη περίπτωση έχει λ₁ υποπεριπτώσεις, η δεύτερη λ₂ υποπεριπτώσεις,...,η κ-οστή λ_κ υποπεριπτώσεις. Τότε το σύνολο όλων των περιπτώσεων είναι

${\lambda }_1+{\lambda }_2+{\lambda }_3+\cdots +{\lambda }_{\kappa }$

Κανόνας γινομένου:

Αρχείο:Δέντρο ίσων υποπεριπτώσεων.PNG

Δέντρο, όπου οι αντίστοιχοι κόμβοι έχουν ίσο αριθμό υποπεριπτώσεων.

Έστω ότι μια κ-άδα (α₁,α₂,...,α_κ), όπου υπάρχουν λ₁ περιπτώσεις για το α₁, λ₂ περιπτώσεις για το α₂,...,λ_κ περιπτώσεις για το α_κ. έστω επιπλέον, ότι η κάθε περίπτωση είναι εντελώς ανεξάρτητη από τις υπόλοιπες. Τότε υπάρχουν συνολικά: ${\lambda }_1\cdot {\lambda }_2\cdot {\lambda }_3\cdots {\lambda }_{\kappa }$ συνολικές περιπτώσεις κ-άδων.

Τύποι της Συνδιαστικής

• Μεταθέσεις των ν στοιχείων: $M_{\nu }=\nu !$
• Διατάξεις των μ στοιχείων σε ν θέσεις (χωρίς επανάληψη): ${\mathrm{\Delta }}_{\nu }^{\mu }=\frac{\mu !}{(\mu -\nu )!}$
• Διατάξεις των μ στοιχείων σε ν θέσεις (με επανάληψη): ${\mathrm{E}}_{\nu }^{\mu }={\mu }^{\nu }$
• Συνδυασμοί των ν στοιχείων ανά μ: $(\genfrac{}{}{0ex}{}{\nu }{\mu })=\frac{\nu !}{\mu !\cdot (\nu -\mu )!}$

Ερωτήσεις

Εμπέδωσης

• Τι σχέση έχουν οι ιδιότητες της βασικής αρχής απαρίθμησης με τις ιδιότητες της πρόσθεσης;
• Αν στο βασικό κανόνα απαρίθμησης ο αριθμός των υποπεριπτώσεων κάθε περίπτωσης είναι λ τι μπορούμε να συμπεράνουμε;
• Τι σχέση έχει η βασική αρχή απαρίθμησης με τον κανόνα του γινομένου;
• Τι σχέση έχουν οι ιδιότητες του κανόνα του γινομένου με τις ιδιότητες του γινομένου;
• Αν στον κανόνα του γινομένου ο αριθμός των περιπτώσεων σε κάθε α_μ είναι λ τι μπορούμε να συμπεράνουμε;
• Τι σχέση υπάρχει μεταξύ του κανόνα του γινομένου με τον κανόνα που ανακαλύψατε στο παραπάνω ερώτημα και ποιες είναι οι διαφορές του με τους δύο προηγούμενους κανόνες;

Αποδεικτικές

Έστω Α σύνολο κ στοιχείων και Β το σύνολο των λ-άδων των στοιχείων του, όπου λ<κ.

• Ποιος είναι ο αριθμός των στοιχείων του Β;
• Αν στο παραπάνω πρόβλημα θέσουμε λ=κ τι προκύπτει;
• Ποιος τύπος ισχύει αν μας ενδιαφέρει η διάταξη των στοιχείων στην κ-άδα και ποιος αν δεν μας ενδιαφέρει;
• Τι μπορούμε να συμπεράνουμε, αν δε μας ενδιαφέρει η θέση των στοιχείων στην κ-άδα; Ποια σχέση ή πράξη το περιγράφει και ποιες οι ιδιότητές της;

Ερευνητικές

• Βρείτε εφαρμογές των τύπων που ανακαλύψατε. Ποια ή ποιες επιστήμες χρησιμοποιούν τη συνδυαστική;
• Με ποια γεωμετρική σχέση μοιάζει ο κανόνας του γινομένου για κ=2; Τι μπορούμε να συμπεράνουμε από αυτό;
• Τι σχέση έχει η συνδυαστική με το δυναμοσύνολο;