Πόσες διαφορετικές παραστάσεις;

#1

Δίνεται η παράσταση

$\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}$

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;

taratoris · #2

Έστω

ο αριθμός των παραστάσεων όταν έχουμε

στοιχεία.

Τότε προφανώς K_1=K_2=1

διότι μπορούμε να ομαδοποιήσουμε

και

στοιχεία με μοναδικό τρόπο.

Για

στοιχεία ισχύει $K_n=\sum_{i=1}^{n-1}K_iK_{n-i}$ . Ο λόγος είναι οτι μπορούμε να διαλέξουμε με n-1

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

Επαγωγικά μπορούμε να δείξουμε οτι $K_n=\frac{1}{n}{2n-2 \choose n-1}$ .

#3

Βαγγέλη, πάτησες μπανανόφλουδα.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

taratoris · #4

Γειά σου Δημήτρη, το σκέφτηκα αυτό που λες και έχεις δίκαιο. Η λογική μου είναι πως αν και δημιουργούν το ίδιο κλάσμα ΚΑΤΟΠΙΝ αλγεβρικών χειρισμών, θα θεωρούσα αυτές τις δύο ως διαφορετικές παραστάσεις. Για παράδειγμα

και $\frac{1}{\frac{1}{x}}$ είναι ισοδύναμες παραστασεις αλλά δεν είναι ίδιες παραστάσεις.

Θα προσπαθήσω να παραθεσω λύση για το πρόβλημα όπου λαμβάνονται ως ίδιες δυο ισοδύναμες παραστάσεις.

nikkru · #5

Demetres έγραψε:Δίνεται η παράσταση

$\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}$

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

taratoris · #6

Η σωστή απάντηση (όπως υπέδειξε και ο nikkru) είναι $2^{n-2}$ .

Η απόδειξη έχει ως εξής:

Θα δείξουμε οτι χρησιμοποιώντας τις παρενθέσεις με όλους τους δυνατούς τρόπους μπορούμε να δημιουργήσουμε όλα τα κλάσματα που έχουν το a_1

στον αριθμητή και το a_2

στον παρονομαστή. Εφόσον υπάρχουν n-2

στοιχεία πλην των a_1

και

, και εφόσνον έχουμε την επιλογή να τοποθετήσουμε κάθε στοιχείο είτε στον αριθμητή είτε στον παρονομαστή βλέπουμε οτι έχουμε $2^{n-2}$ παραστάσεις. (Μπορούμε εύκολα να δείξουμε επαγωγικά οτι τα a_1

και

πρέπει υποχρεωτικά να είναι στον αριθμητή και παρονομαστή αντίστοιχα.)

Θα αποδείξουμε την προτασή μας με επαγωγή στο

. Βλέπουμε οτι η υπόθεσή μας ισχύει για n=2

. Έστω οτι ισχύει για κάθε $n \leq k-1$ . Θα δείξουμε οτι ισχύει για n=k

Έστω οτι θέλουμε να δημιουργήσουμε ένα κλάσμα της μορφής $\frac{a_1 x}{a_2 y a_k}$ όπου κάθε a_i

με $3\leq i \leq k-1$ ανήκει είτε στο

είτε στο

.

Τότε ξέρουμε οτι υπάρχει παράσταση A=((((...)))

που δημιουργεί το κλάσμα $\frac{a_1 x}{a_2 y}$ λόγω της επαγωγικής υπόθεσης.

Σε αυτή την περίπτωση η παράσταση $B=A\textdiv / a_k$ δημιουργεί το ζητούμενο κλάσμα.

Έστω οτι θέλουμε να δημιουργήσουμε ένα κλάσμα της μορφής $\frac{a_1 x a_k a_{k-1}...a_{k-i+1}}{a_2 y a_{k-i}}$ όπου $i \geq 1$ και κάθε a_j

με $3\leq j \leq k-i$ ανήκει είτε στο

είτε στο

.

Τότε ξέρουμε οτι υπάρχει παράσταση A=((((...)))

που δημιουργεί το κλάσμα $\frac{a_1 x}{a_2 y a_{k-i}}$ λόγω της επαγωγικής υπόθεσης. Τότε θέτοντας όπου $a_{k-i}$ την τιμή $(((...(a_{k-i}/a_{k-i+1})/a_{k-i+2})...)a_{k})=\frac{a_{k-i}}{a_{k-i+1}a_{k-i+2}...a_{k}}$ στην

δημιουργούμε το ζητούμενο κλάσμα.

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

Δημήτρη δεν βρήκα πως να γράψω το σύμβολο της διαίρεσης που χρησιμοποιείς οπότε χρησιμοποίησα απλώς /

nikkru · #7

Demetres έγραψε:Δίνεται η παράσταση

$\displaystyle{ x_1 \div x_2 \div \cdots \div x_n}$

Μπορούμε να τοποθετήσουμε παρενθέσεις με όποιο τρόπο θέλουμε. Πόσες διαφορετικές παραστάσεις προκύπτουν αν τοποθετήσουμε παρενθέσεις με όλους τους δυνατούς τρόπους;

Καλημέρα,
ας παραθέσω άλλη μια λύση.

Προφανώς οι $\displaystyle{ x_1 , x_2$ όπου και να τοποθετήσουμε παρενθέσεις δεν αλλάζουν θέσεις, ο x_1

είναι πάντα στον αριθμητή και ο x_2

στον παρονομαστή του τελικού απλού κλάσματος.
Τους υπόλοιπους n-2

όρους μπορούμε να τους έχουμε στον αριθμητή ή στον παρονομαστή του τελικού απλού κλάσματος άρα υπάρχουν $2^{n-2}$ διαφορετικές παραστάσεις( θεωρούμε όλα τα x_i

διαφορετικά μεταξύ τους και παραβλέπουμε τις τυχόν απλοποιήσεις ).

Η διαδικασία είναι η εξής:

Ξεκινάμε από το δεξιό μέρος της παράστασης και κινούμενοι προς τα αριστερά:
βάζουμε δεξιά παρένθεση μετά από κάθε $\displaystyle{ x_i }$ που συναντάμε και θέλουμε να είναι στον αριθμητή
ενώ πριν από κάθε x_i

που συναντάμε και θέλουμε να είναι στον παρονομαστή βάζουμε όσες αριστερές παρενθέσεις χρειάζονται για να συμπληρώσουν τις δεξιές παρενθέσεις που έχουμε ήδη βάλει.
Η διαδικασία τελειώνει όταν φτάσουμε σε όρο που θέλουμε να είναι στον παρονομαστή και έχει μόνο δεξιά του όρους που θέλουμε να είναι στον αριθμητή.

Π.χ. στην παράσταση $\displaystyle{ 1 \div 2 \div 3 \div 4 \div 5\div 6 \div 7\div 8}$ αν θέλουμε να έχουμε στον αριθμητή τους 4,5,7

γράφουμε: $\displaystyle{ 1 \div 2 \div ((3 \div 4) \div 5)\div (6 \div 7)\div 8}$

#8

taratoris έγραψε: Δημήτρη δεν βρήκα πως να γράψω το σύμβολο της διαίρεσης που χρησιμοποιείς οπότε χρησιμοποίησα απλώς /

Με το \div. Αν πάρεις το βελάκι πάνω από τον τύπο, τότε φαίνεται ο κώδικας του latex που χρησιμοποιήθηκε.

Δίνω και την δική μου απόδειξη:

Αναγκαστικά το x_1

είναι στον αριθμητή και το x_2

στον παρονομαστή. Θα δείξω επαγωγικά ότι μπορώ να έχω οποιοδήποτε κλάσμα που να έχει το x_1

στον αριθμητή και το x_2

στον παρονομαστή.

Για n=2

προφανώς ισχύει. Έστω λοιπόν ότι ισχύει για n=k

. Έστω

και ότι θέλω να φτιάξω ένα συγκεκριμένο κλάσμα

το οποίο να έχει το x_1

στον αριθμητή και το x_2

στον παρονομαστή.

Αν για αυτό το κλάσμα υπάρχει δείκτης

ώστε το

να βρίσκεται στον παρονομαστή και το $x_{i+1}$ στον αριθμητή τότε ξεκινάω με τις παρενθέσεις
$\displaystyle{ (x_1 \div \cdots \div x_{i-1}) \div (x_i \div \cdots \div x_{k+1})}$
Από την επαγωγική υπόθεση μπορώ να βάλω παρενθέσεις στο πρώτο κομμάτι ώστε τα x_j

με

να βρίσκονται στην ίδια θέση όπως στο κλάσμα

. Επίσης μπορώ να βάλω παρενθέσεις στο δεύτερο κομμάτι ώστε τα x_j

με $j \geqslant i$ να βρίσκονται σε αντίθετη θέση από ότι στο

. Το τελικό αποτέλεσμα θα είναι το επιθυμητό.

Αν τώρα δεν υπάρχει τέτοιος δείκτης

αυτό σημαίνει ότι θέλω να φτιάξω το κλάσμα $\displaystyle{ \frac{x_1}{x_2 \cdots x_{k+1}}.}$ Αυτό όμως μπορεί να φτιαχτεί ως εξής:

$\displaystyle{ (\cdots((x_1 \div x_2) \div x_3) \div \cdots \div x_{k+1})}$

Πόσες διαφορετικές παραστάσεις;

Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

Re: Πόσες διαφορετικές παραστάσεις;

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