Δευτέρα 30 Οκτωβρίου 2023

Επιλογή υποσυνόλου

Με πόσους τρόπους μπορούμε να επιλέξουμε ένα υποσύνολο του συνόλου 
 $\big\{1, 2, 3, . . ., 11\big\}$ 
που δεν περιέχει τρεις διαδοχικούς ακέραιους αριθμούς;
Αναρτήθηκε από στις 30.10.23
Ετικέτες

3 σχόλια:

  1. papadim31 Οκτωβρίου 2023 στις 10:59 π.μ.

    Αν Α(ν) το πλήθος των υποσυνόλων του συνόλου Σ={1,2,3,..,ν} που δεν περιέχουν τρεις διαδοχικούς ακέραιους, ισχύει η αναδρομική σχέση:
    Α(ν)=Α(ν-3)+Α(ν-2)+Α(ν-1) (1)
    (αρκεί να σκεφτούμε ότι καθένα από τα υποσύνολα του Σ ΔΕΝ περιέχει το στοιχείο ν, ή το ν-1, ή το ν-2, είναι αδύνατο να περιέχει και τα τρία)
    Αρχική συνθήκη:
    Α(0)=2^0=1
    Α(1)=2^1=2
    Α(2)=2^2=4
    (κάθε σύνολο με ν στοιχεία έχει 2^ν στο πλήθος υποσύνολα)
    Με λίγες επαναλήψεις βάσει της (1), εύκολα βρίσκουμε τα Α(3), Α(4), κ.ο.κ. και γρήγορα καταλήγουμε σε Α(11)=927

    ΑπάντησηΔιαγραφή
  2. Ανώνυμος31 Οκτωβρίου 2023 στις 12:29 μ.μ.

    Εξαιρετικός Papadim! (As usual…)
    Όπως θα έλεγε κι ο μεγάλος Τριμπονάτσι (μακρινός ναπολιτάνος ξάδερφος του Φιμπονάτσι) 😊
    https://oeis.org/A000073
    ΓΡ

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. papadim31 Οκτωβρίου 2023 στις 2:07 μ.μ.

      Ευχαριστώ Γιώργη!!
      Συμπάθα με πάντως, που από τις 'νόθες' συγγένειες προτιμώ τις εκλεκτικές. Την 'ν στοιχεία => 2^ν υποσύνολα' και τη Φιμπονάτσι τις έμαθα ή τις σπούδασα καλύτερα από αναρτήσεις Ριζόπουλου, τον παλιό καλό καιρό. Οπότε από Tribonacci προτιμώ να την πω Rizo-nacci!😉

      Διαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)