Σε κάθε κύκλο σε αυτό το δενδροδιάγραμμα πρέπει να δοθεί μια τιμή, επιλεγμένη από ένα σύνολο $S$, με τέτοιο τρόπο ώστε σε κάθε διαδρομή κάτω από το δέντρο, οι δοθείσες τιμές να μην αυξάνονται ποτέ.
Δηλαδή
$A\geq B$, $A\geq C$, $C\geq D$, $C\geq E$, και $A, B, C, D, E\in S$.
(Επιτρέπεται μια τιμή από το $S$ να εμφανίζεται περισσότερες από μία φορές.)
Με πόσους τρόπους μπορεί να είναι το δέντρο έτσι αριθμημένο, χρησιμοποιώντας μόνο τιμές που επιλέγονται από το σύνολο $S = {1, . . . , 6}$;
Για 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 επιτρεπτές διατάξεις
Όπου έχει γραφεί (C,D), διορθώνεται σε (D,E)
Διαγραφή