Συνδυαστική

Από Βικιεπιστήμιο
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

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

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

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

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

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

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

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

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

Έστω ότι μια κ-άδα (α12,...,ακ), όπου υπάρχουν λ1 περιπτώσεις για το α1, λ2 περιπτώσεις για το α2,...,λκ περιπτώσεις για το ακ. έστω επιπλέον, ότι η κάθε περίπτωση είναι εντελώς ανεξάρτητη από τις υπόλοιπες. Τότε υπάρχουν συνολικά: συνολικές περιπτώσεις κ-άδων.

Τύποι της Συνδιαστικής[επεξεργασία]

  • Μεταθέσεις των ν στοιχείων:
  • Διατάξεις των μ στοιχείων σε ν θέσεις (χωρίς επανάληψη):
  • Διατάξεις των μ στοιχείων σε ν θέσεις (με επανάληψη):
  • Συνδυασμοί των ν στοιχείων ανά μ:

Ερωτήσεις[επεξεργασία]

Εμπέδωσης[επεξεργασία]

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

Αποδεικτικές[επεξεργασία]

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

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

Ερευνητικές[επεξεργασία]

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