Υποσύνολα που δεν περιέχουν διαδοχικούς αριθμούς

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #1

Πόσα υποσύνολα του συνόλου $\left\{ 1,2,....,n\right\}$ υπάρχουν που δεν περιέχουν δύο διαδοχικούς αριθμούς;

∫ot.T. · #2

Ονομάζουμε $a_{n},b_{n}$ το πλήθος των υποσυνόλων του [n]

, χωρίς διαδοχικά στοιχεία, που περιέχουν το {n}

και δεν περιέχουν το {n}

αντίστοιχα.
Ζητάμε το $c_{n}=a_{n}+b_{n}$

Παρατηρούμε ότι $a_{n+1}=b_{n}+1$ και $b_{n+1}=a_{n}+b_{n}$

Αυτό συμβαίνει διότι τα υποσύνολα που περιέχουν το {n+1}

σίγουρα δεν θα περιέχουν το {n}

οπότε εξαιρώντας το {n+1}

λαμβάνουμε όλα τα υποσύνολα που μετρήθηκαν στο $b_{n}$ . Προσθέτουμε επίσης

για το υποσύνολο {n+1}

.

Η δεύτερη σχέση προκύπτει αφού τα υποσύνολα που δεν περιέχουν το {n+1}

είναι όλα τα υποσύνολα του [n]

ώστε να μην υπάρχουν διαδοχικά στοιχεία.

Από αυτές τις δύο σχέσεις εύκολα έχουμε $c_{n+1}=c_{n}+c_{n-1}+1$ με $c_{1}=1, c_{2}=2$

Θέτουμε $f_{n}=c_{n}+1$ για να έχουμε την μορφή της ακολυθίας fibonacci, αλλά λόγω των αρχικών συνθηκών προκύπτει

$c_{n}=F_{n+2}-1$ όπου $F_{n}$ ο

-οστός όρος της ακολυθίας fibonacci.

Υποσύνολα που δεν περιέχουν διαδοχικούς αριθμούς

Υποσύνολα που δεν περιέχουν διαδοχικούς αριθμούς

Re: Υποσύνολα που δεν περιέχουν διαδοχικούς αριθμούς

Μέλη σε σύνδεση