Πρόβλημα πιθανοτήτων/συνδυαστικής (όχι προγραμματισμός)

[thomason993]

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

Θέλω να υπολογίσω πόσες πιθανές διατάξεις/συνδυασμοί Ν θετικών ακεραίων αριθμών (δλδ από το 1 έως το Ν) υπάρχουν με την προϋπόθεση οτι  στην Ν-οστή θέση δεν μπορεί να τοποθετηθεί ο αριθμός Ν και χωρίς να επαναλαμβάνονται αριθμοί.

Δλδ, για Ν=5, μερικές αποδεκτές διατάξεις είναι: 2-1-4-5-3 και 5-3-2-1-4

Ενώ μερικές μη αποδεκτές διατάξεις είναι: 1-3-5-2-4 και 2-1-4-5-2

Ο τρόπος σκέψης μου μέχρι τώρα είναι κάπως έτσι: αν έχω Ν θέσεις στις οποίες θέλω να βάλω αριθμούς τότε η 1η θέση μπορεί να πάρει Ν-1 επιλογές (απο 2 έως Ν), η 2η θέση Ν-1 επιλογές (αν έχω χρησιμοποιήσει το 2 στην 1η θέση) ή Ν-2 (αν δεν έχω χρησιμοποιήσει το 2 στην 1η θέση) και πάει λέγοντας.. αλλά κάπου το χάνω και μπερδεύομαι. Θέλω η απάντηση να είναι συναρτήσει του Ν.

Όποιος μπορεί να μου πει την λύση, ας μου εξηγήσει και το πως το υπολόγισε.

Επεξ/σία 14 Φεβρουαρίου 2019 από thomason993

[archer100]

2 ώρες πριν, thomason993 είπε

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

Θέλω να υπολογίσω πόσες πιθανές διατάξεις/συνδυασμοί Ν θετικών ακεραίων αριθμών (δλδ από το 1 έως το Ν) υπάρχουν με την προϋπόθεση οτι  στην Ν-οστή θέση δεν μπορεί να τοποθετηθεί ο αριθμός Ν και χωρίς να επαναλαμβάνονται αριθμοί.

Δλδ, για Ν=5, μερικές αποδεκτές διατάξεις είναι: 2-1-4-3-5 και 5-3-2-1-4

Ενώ μερικές μη αποδεκτές διατάξεις είναι: 1-3-5-2-4 και 2-1-4-5-2

Ο τρόπος σκέψης μου μέχρι τώρα είναι κάπως έτσι: αν έχω Ν θέσεις στις οποίες θέλω να βάλω αριθμούς τότε η 1η θέση μπορεί να πάρει Ν-1 επιλογές (απο 2 έως Ν), η 2η θέση Ν-1 επιλογές (αν έχω χρησιμοποιήσει το 2 στην 1η θέση) ή Ν-2 (αν δεν έχω χρησιμοποιήσει το 2 στην 1η θέση) και πάει λέγοντας.. αλλά κάπου το χάνω και μπερδεύομαι. Θέλω η απάντηση να είναι συναρτήσει του Ν.

Όποιος μπορεί να μου πει την λύση, ας μου εξηγήσει και το πως το υπολόγισε.

Το πληθος ολων των μεταθεσεων ειναι Μ = Ν!

Απο αυτες θελουμε μονο οσες πληρουν το κριτηριο που εθεσες.

Η πιθανοτητα για καποια μεταθεση να πληροι το κριτηριο προκυπτει με την εξης λογικη:

 

Ρκ: Το κ στοιχειο να μην ειναι κ: 1 μειον την πιθανοτητα να μην εχει ηδη τοποθετηθει το κ σε προηγουμενη θεση  επι την πιθανοτητα να υπαρχει ακομα διαθεσιμο  και να τοποθετηθει το κ στη συγκεκριμενη θεση 1/(Ν -κ+1) 

......

Πολλαπλασιαζεις τα ανωτερω για ολα τα κ απο 1 εως Ν και παιρνεις το Ρ

Αρα ολοι οι επιθυμητοι συνδυασμοι ειναι Ρ * Ν

 

Επεξ/σία 13 Φεβρουαρίου 2019 από archer100

[pmav99]

Έστω ότι έχεις n=4 αριθμούς. Οι συνδυασμοί είναι
 

n! = 4! = 24

Πιο συγκεκριμένα αυτοί:

[(1, 2, 3, 4),
 (1, 2, 4, 3),
 (1, 3, 2, 4),
 (1, 3, 4, 2),
 (1, 4, 2, 3),
 (1, 4, 3, 2),
 (2, 1, 3, 4),
 (2, 1, 4, 3),
 (2, 3, 1, 4),
 (2, 3, 4, 1),
 (2, 4, 1, 3),
 (2, 4, 3, 1),
 (3, 1, 2, 4),
 (3, 1, 4, 2),
 (3, 2, 1, 4),
 (3, 2, 4, 1),
 (3, 4, 1, 2),
 (3, 4, 2, 1),
 (4, 1, 2, 3),
 (4, 1, 3, 2),
 (4, 2, 1, 3),
 (4, 2, 3, 1),
 (4, 3, 1, 2),
 (4, 3, 2, 1)]

Οι συνδυασμοί που στην πρώτη θέση έχουν 1 δεν μας κάνουν.

Πόσοι συνδυασμοί είναι αυτοί; Εξέφρασε τους σαν παραγοντικό.

Μετά συνέχισε στην δεύτερη θέση με τους συνδυασμούς που απομένουν και υπολόγισε πόσοι συνδυασμοί πρέπει να φύγουν. Εξέφρασε πόσοι είναι αυτοί σαν παραγοντικό

Συνέχισε με την επόμενη θέση

όταν φτάσεις στη τελευταία θέση θα δεις ότι οι συνδυασμοί που φεύγουν σε κάθε βήμα ακολουθούν ένα pattern. Το να εκφράσεις το pattern σε μία γενική σχέση είναι απλό πια.

[albNik]

υπάρχουν  N!/e  συνδυασμοί ...

δεν κάνω πλάκα 

 

Spoiler

https://en.wikipedia.org/wiki/Derangement

 

[Lanike71]

Δύσκολο πρόβλημα όντως.

Η δυσκολία είναι στο ότι έχει επικαλυπτόμενες περιπτώσεις και γι' αυτό δε μπορούμε να πούμε ξεκάθαρα βάσει n το αποτέλεσμα.

Παράδειγμα, το σετ [1,2,4,3], ποιός αριθμός είναι φάουλ; Ο 1 ή ο 2; Σε ποιό σετ αριθμών που πρέπει να διώξουμε ανήκει;

Εγώ ξεκίνησα με το σκεπτικό ότι κάθε αριθμός παίζει n! / n φορές σε κάθε θέση και τον αφαιρώ. Αλλά κατέληξα να πρέπει να αφαιρώ όλο το n! τελικά, κάτι που δεν παίζει.

Ένα ευχαριστώ στον @albNik με το λινκ του.

 

[thomason993]

Παιδιά σας ευχαριστώ για τις απαντήσεις. Απ' οτι φαίνεται το πρόβλημα είναι πιο περίπλοκο απ' οσο νόμιζα. Ήταν ερώτηση πολλαπλής σε μάθημα την εξεταστική που πέρασε και απλά είχα απορία ποιά ήταν η σωστή απάντηση (έδινε σαν επιλογές Ν-1, Ν!, Ν^2 και Άλλο, κύκλωσα το τελευταίο).

Το link που έδωσε ο φίλος παραπάνω πολύ χρήσιμο, το πιο κοντινό σε γενικό τύπο συναρτήσει του Ν απ' οτι καταλαβαίνω είναι αυτό:

 

[k33theod]

Πρώτη φορά το ακούω Derangement !n

Είδες Thomason993 την ίδια ερώτηση με σένα είχε και ο Pierre Raymond de Montmort το 1708 και έκανε 5 χρόνια να την λύσει. Εσύ μια μέρα το έιχες 😀  Αν και η πρώτη 5άδα που έχεις στις αποδεκτές διατάξεις είναι λάθος ή όχι

Επεξ/σία 14 Φεβρουαρίου 2019 από k33theod

[thomason993]

3 λεπτά πριν, k33theod είπε

Αν και η πρώτη 5άδα που έχεις στις αποδεκτές διατάξεις είναι λάθος ή όχι

Έχεις δίκιο, την ώρα που έκανα το post το μυαλό δεν δούλευε και πολύ.. Το διόρθωσα τώρα.

[k33theod]

der(1)=0, der(0)=1

der(n)=(n-1)der(n-1)+der(n-2)  Fibonacci παραλαγμένος;