Τρίτη 4 Απριλίου 2023

Δενδροδιάγραμμα

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

Δηλαδή 
$A\geq  B$, $A\geq  C$, $C\geq  D$, $C\geq  E$, και $A, B, C, D, E\in S$. 
(Επιτρέπεται μια τιμή από το $S$ να εμφανίζεται περισσότερες από μία φορές.) 
Με πόσους τρόπους μπορεί να είναι το δέντρο έτσι αριθμημένο, χρησιμοποιώντας μόνο τιμές που επιλέγονται από το σύνολο $S = {1, . . . , 6}$;

2 σχόλια:

  1. Για C=6, υπάρχουν 6 επιτρεπτά ζευγάρια τιμών (Α,B) και 6×6=36 επιτρεπτά ζευγάρια τιμών (C,D), άρα συνολικά 6×36=216 διατάξεις.
    Για C=5, υπάρχουν 6+5=11 επιτρεπτά ζευγάρια τιμών (Α,B) και 5×5=25 επιτρεπτά ζευγάρια τιμών (C,D), άρα συνολικά 11×25=275 διατάξεις.
    Για C=4, υπάρχουν 6+5+4=15 επιτρεπτά ζευγάρια τιμών (Α,B) και 4×4=16 επιτρεπτά ζευγάρια τιμών (C,D), άρα συνολικά 15×16=240 διατάξεις.
    Για C=3, υπάρχουν 6+5+4+3=18 επιτρεπτά ζευγάρια τιμών (Α,B) και 3×3=9 επιτρεπτά ζευγάρια τιμών (C,D), άρα συνολικά 18×9=162 διατάξεις.
    Για C=2, υπάρχουν 6+5+4+3+2=20 επιτρεπτά ζευγάρια τιμών (Α,B) και 2×2=4 επιτρεπτά ζευγάρια τιμών (C,D), άρα συνολικά 20×4=80 διατάξεις.
    Για C=1, υπάρχουν 6+5+4+3+2+1=21 επιτρεπτά ζευγάρια τιμών (Α,B) και 1×1=1 επιτρεπτό ζευγάρι τιμών (C,D), άρα συνολικά 21×1=21 διατάξεις.
    Γενικό σύνολο: 216+275+240+162+80+21=994 επιτρεπτές διατάξεις

    ΑπάντησηΔιαγραφή