Eulerian Numbers -- Πόσες Μεταθέσεις Έχουν Ακριβώς k Ανοδικά Βήματα;

Προσοχή στο όνομα: Τα Eulerian numbers δεν πρέπει να συγχέονται με τους εντελώς διαφορετικούς Euler numbers (χωρίς "-ian") — μια άσχετη ακολουθία που ορίζεται μέσω του αναπτύγματος Taylor της \(\text{sech}(x)\) και σχετίζεται με εναλλασσόμενες μεταθέσεις. Ίδιο όνομα προέλευσης, τελείως διαφορετικά μαθηματικά αντικείμενα.

📘 Ο Ορισμός

Πάρε μια μετάθεση των αριθμών \(1,2,\ldots,n\). Ένα «ανοδικό βήμα» (ascent) είναι μια θέση όπου ένα στοιχείο είναι μεγαλύτερο από το προηγούμενό του. Ο Eulerian number \(\left\langle {n\atop k}\right\rangle\) μετράει πόσες από τις \(n!\) μεταθέσεις των \(1,\ldots,n\) έχουν ακριβώς \(k\) τέτοια ανοδικά βήματα.

🧩 Ένα Παράδειγμα

Πάρε τις μεταθέσεις του \(\{1,2,3,4\}\) — υπάρχουν \(4!=24\) συνολικά. Ανάμεσά τους, 11 έχουν ακριβώς 2 ανοδικά βήματα — για παράδειγμα, η μετάθεση \(2,4,1,3\) έχει ανοδικά βήματα στις θέσεις \(2\to4\) και \(1\to3\), άρα ακριβώς 2.

Πράγματι, αν μοιράσουμε όλες τις 24 μεταθέσεις ανάλογα με τον αριθμό ανοδικών βημάτων τους (0, 1, 2, ή 3), παίρνουμε: \(1, 11, 11, 1\) — που αθροίζουν στο \(24\), όπως πρέπει.

📐 Ο Τύπος

Οι Eulerian numbers δίνονται από τον τύπο (μέσω αρχής εγκλεισμού-αποκλεισμού):

\[ \left\langle {n\atop k}\right\rangle = \sum_{i=0}^{k} (-1)^i \binom{n+1}{i}(k+1-i)^n \]

🔺 Το Τρίγωνο των Eulerian Numbers

Παραθέτοντας τα Eulerian numbers γραμμή-γραμμή (για \(k=0,1,\ldots,n-1\)) σχηματίζεται ένα τρίγωνο, ανάλογο του τριγώνου του Pascal:

n=1:   1
n=2:   1  1
n=3:   1  4  1
n=4:   1 11 11  1
n=5:   1 26 66 26  1
n=6:   1 57 302 302 57  1

Κάθε γραμμή είναι συμμετρική, και το άθροισμά της ισούται πάντα με \(n!\) — αφού κάθε μετάθεση ανήκει ακριβώς σε μία κατηγορία, ανάλογα με τον αριθμό ανοδικών βημάτων της.

🎨 Κατανομή Υπολοίπων (mod 2 έως 11)

Αυτό το διάγραμμα δείχνει πόσο συχνά τα Eulerian numbers αφήνουν κάθε δυνατό υπόλοιπο, όταν διαιρεθούν με 2, 3, 4, ..., ως και το 11. Κάθε γραμμή αντιστοιχεί σε ένα διαιρέτη (mod), και κάθε κελί σε ένα πιθανό υπόλοιπο. Το χρώμα κάθε κελιού δείχνει πόσο πάνω ή κάτω από την «ισοκατανομή» βρίσκεται η συχνότητα εκείνου του υπολοίπου: το βαθύ κόκκινο σημαίνει πολύ πιο συχνό απ' όσο θα περίμενε κανείς τυχαία, το βαθύ μπλε πολύ πιο σπάνιο, ενώ τα ανοιχτόχρωμα κελιά είναι κοντά στο αναμενόμενο \(1/n\). Παρατηρείς ότι το υπόλοιπο 0 (η στήλη "rem=0") είναι σχεδόν πάντα έντονα κόκκινο — δηλαδή, ένα μεγάλο ποσοστό Eulerian numbers διαιρείται ακριβώς με κάθε mod, πολύ πιο συχνά απ' όσο θα περίμενε κανείς από τυχαίους αριθμούς.

📉 Πολλαπλάσια Πρώτων Αριθμών

Αυτό το γράφημα εξετάζει, για κάθε πρώτο αριθμό \(p\) από το 2 έως το 71, τι ποσοστό των αριθμών Eulerian numbers είναι πολλαπλάσιο του \(p\) — υπολογισμένο πάνω σε ένα δείγμα 76.701 τιμών (από αριθμούς Eulerian numbers με \(n\) έως και \(10^{1000}\)). Η μαύρη καμπύλη δείχνει την «αναμενόμενη» αναλογία \(1/p\) αν τα Eulerian numbers συμπεριφέρονταν σαν τυχαίοι ακέραιοι. Οι κόκκινες κουκκίδες, το πραγματικό ποσοστό, βρίσκονται συστηματικά πάνω από την καμπύλη — δηλαδή τα Eulerian numbers είναι πιο πιθανό να διαιρούνται από μικρούς πρώτους απ' όσο θα περίμενε κανείς από τυχαίους αριθμούς, μια ακόμη ένδειξη της ιδιαίτερης δομής πίσω από αυτή την ακολουθία.

Πηγές: Numbers Aplenty · Wikipedia · MathWorld · OEIS A008292

📘

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →