Ακολουθία Γκουλντ

Τρίγωνο του Πασκάλ, σειρές 0 έως 7. Ο αριθμός των περιττών ακεραίων αριθμών στη σειρά i είναι ο i -οστός αριθμός στην ακολουθία του Γκουλντ.

Η ακολουθία του Γκουλντ είναι μια ακέραια ακολουθία που πήρε το όνομά της από τον Χένρυ Γ. Γκουλντ και μετράει πόσοι περιττοί αριθμοί υπάρχουν σε κάθε σειρά του τριγώνου του Πασκάλ. Αποτελείται μόνο από δυνάμεις του δύο και αρχίζει ως εξής:[1][2]

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, ... (ακολουθία A001316 στην OEIS).

Παραδείγματος χάριν, ο έκτος αριθμός στην ακολουθία είναι 4, επειδή υπάρχουν τέσσερις περιττοί αριθμοί στην έκτη σειρά του τριγώνου του Πασκάλ (οι τέσσερις έντονοι αριθμοί στην ακολουθία 1, 5, 10, 10, 5, 1).

Πρόσθετες ερμηνείες

Το αυτο-ομοειδές πριονωτό σχήμα της ακολουθίας του Γκουλντ

Η nth τιμή στην ακολουθία (ξεκινώντας από n = 0) δίνει την υψηλότερη δύναμη του 2 που διαιρεί τον κεντρικό διωνυμικό συντελεστή , και δίνει τον αριθμητή του (σε μορφή κλάσματος με τους χαμηλότερους συντελεστές)[1].

Τρίγωνο Σιερπίνσκι που παράγεται από τον Κανόνα 90, ή σημειώνοντας τις θέσεις των περιττών αριθμών στο τρίγωνο του Πασκάλ. Η ακολουθία του Γκουλντ μετράει τον αριθμό των ζωντανών κυττάρων σε κάθε σειρά αυτού του μοτίβου.

Το τρίγωνο Σιερπίνσκι που δημιουργείται από τον κανόνα 90, ή σημειώνοντας τις θέσεις των περιττών αριθμών στο τρίγωνο του Πασκάλ. Η ακολουθία του Γκουλντ μετράει τον αριθμό των ζωντανών κυττάρων σε κάθε σειρά αυτού του μοτίβου.

Η ακολουθία του Γκουλντ δίνει επίσης τον αριθμό των ζωντανών κυττάρων στην nth γενιά του κυτταρικού αυτομάτου του Κανόνα 90 ξεκινώντας από ένα μόνο ζωντανό κύτταρο[1][3] Έχει ένα χαρακτηριστικό αυξανόμενο πριονωτό σχήμα που μπορεί να χρησιμοποιηθεί για την αναγνώριση φυσικών διεργασιών που συμπεριφέρονται παρόμοια με τον Κανόνα 90[4].

Σχετικές ακολουθίες

Οι δυαδικοί λογάριθμοι (εκθέτες σε δυνάμεις του δύο) της ακολουθίας του Γκουλντ σχηματίζουν μια ακέραια ακολουθία,

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... (ακολουθία A000120 στην OEIS)

στην οποία η nth τιμή δίνει τον αριθμό των μη μηδενικών bits στη δυαδική αναπαράσταση του αριθμού n, που μερικές φορές γράφεται σε μαθηματικό συμβολισμό ως .[1][2] Ισοδύναμα, η nth τιμή στην ακολουθία του Γκουλντ έχει ως εξής

Εάν πάρουμε την ακολουθία των εκθετών modulo δύο προκύπτει η ακολουθία Θουέ-Μορς.[5]

Τα επιμέρους αθροίσματα της ακολουθίας του Γκουλντ,

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... (ακολουθία A006046 στην OEIS)

μετρήστε όλους τους περιττούς αριθμούς στις πρώτες n σειρές του τριγώνου του Πασκάλ. Αυτοί οι αριθμοί αυξάνονται αναλογικά με , αλλά με μια σταθερά αναλογικότητας που ταλαντεύεται μεταξύ 0.812556... και 1, περιοδικά ως συνάρτηση του log n.[6][7]

Αναδρομική κατασκευή και αυτο-ομοιότητα

Οι πρώτες 2i τιμές στην ακολουθία του Γκουλντ μπορούν να κατασκευαστούν με την αναδρομική κατασκευή των πρώτων 2i − 1 τιμών και στη συνέχεια με τη συνένωση των διπλών των πρώτων 2i − 1 τιμών. Παραδείγματος χάριν, η συνένωση των τεσσάρων πρώτων τιμών 1, 2, 2, 2, 4 με τα διπλά τους 2, 4, 4, 4, 8 παράγει τις οκτώ πρώτες τιμές. Λόγω αυτής της κατασκευής διπλασιασμού, η πρώτη εμφάνιση κάθε δύναμης του 2i σε αυτή την ακολουθία βρίσκεται στη θέση 2i − 1.[1]

Η ακολουθία του Γκουλντ, η ακολουθία των εκθετών της και η ακολουθία των Θουέ-Μορς είναι όλες αυτο-ομοειδείς: έχουν την ιδιότητα ότι η υποακολουθία των τιμών σε ζυγές θέσεις σε ολόκληρη την ακολουθία ισούται με την αρχική ακολουθία, μια ιδιότητα που μοιράζονται επίσης με ορισμένες άλλες ακολουθίες, όπως η διατομική ακολουθία του Στερν[3][8][9] Στην ακολουθία του Γκουλντ, οι τιμές σε περιττές θέσεις είναι διπλάσιες των προκατόχων τους, ενώ στην ακολουθία των εκθετών, οι τιμές σε περιττές θέσεις είναι ένα συν τις προκατόχους τους.

Ιστορία

Η ακολουθία πήρε το όνομά της από τον Χένρυ Γ. Γκουλντ, ο άνθρωπος που τη διερεύνησε στις αρχές της δεκαετίας του 1960. Ωστόσο, το γεγονός ότι οι αριθμοί αυτοί είναι δυνάμεις του δύο, με τον εκθέτη του nth αριθμού να ισούται με τον αριθμό των μονάδων στη δυαδική αναπαράσταση του n, ήταν ήδη γνωστό στον J. W. L. Glaisher το 1899[10][11].

Η απόδειξη ότι οι αριθμοί στην ακολουθία του Γκουλντ είναι δυνάμεις του δύο δόθηκε ως πρόβλημα στον Μαθηματικό Διαγωνισμό Γουίλιαμ Λόουελ Πούτναμ του 1956[12].

Δείτε επίσης

Παραπομπές

  1. ↑ 1,0 1,1 1,2 1,3 1,4 The On-Line Encyclopedia of Integer Sequences
  2. ↑ 2,0 2,1 Pólya, George; Tarjan, Robert E.; Woods, Donald R. (2009), Notes on Introductory Combinatorics, Progress in Computer Science and Applied Logic, 4, Springer, σελ. 21, ISBN 9780817649531, https://books.google.com/books?id=K-bDBAAAQBAJ&pg=PA21 .
  3. ↑ 3,0 3,1 Wolfram, Stephen (1984), «Geometry of binomial coefficients», American Mathematical Monthly 91 (9): 566–571, doi:10.2307/2323743 .
  4. ↑ Claussen, Jens Christian; Nagler, Jan; Schuster, Heinz Georg (2004), «Sierpinski signal generates 1/f α spectra», Physical Review E 70 (3): 032101, doi:10.1103/PhysRevE.70.032101, PMID 15524560 .
  5. ↑ Northshield, Sam (2010), «Sums across Pascal's triangle mod 2», Congressus Numerantium 200: 35–52, http://digitalcommons.plattsburgh.edu/cgi/viewcontent.cgi?article=1008&context=mathematics_facpubs, ανακτήθηκε στις 2016-09-10 .
  6. ↑ Harborth, Heiko (1976), «Number of odd binomial coefficients», Proceedings of the American Mathematical Society 62 (1): 19–22, doi:10.2307/2041936 .
  7. ↑ Larcher, G. (1996), «On the number of odd binomial coefficients», Acta Mathematica Hungarica 71 (3): 183–203, doi:10.1007/BF00052108 .
  8. ↑ Gilleland, Michael, Some Self-Similar Integer Sequences, OEIS, https://oeis.org/selfsimilar.html, ανακτήθηκε στις 2016-09-10 .
  9. ↑ Schroeder, Manfred (1996), «Fractals in Music», στο: Pickover, Clifford A., επιμ., Fractal Horizons, New York: St. Martin's Press, σελ. 207–223 . As cited by Gilleland.
  10. ↑ Granville, Andrew (1992), «Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle», American Mathematical Monthly 99 (4): 318–331, doi:10.2307/2324898 .
  11. ↑ Glaisher, J. W. L. (1899), «On the residue of a binomial-theorem coefficient with respect to a prime modulus», The Quarterly Journal of Pure and Applied Mathematics 30: 150–156, https://books.google.com/books?id=j7sKAAAAIAAJ&pg=PA150 . See in particular the final paragraph of p. 156.
  12. ↑ Gleason, Andrew M.; Greenwood, R. E.; Kelly, Leroy Milton, επιμ.. (1980), The William Lowell Putnam Mathematical Competition: Problems and Solutions: 1938–1964, Mathematical Association of America, σελ. 46, ISBN 9780883854624, https://books.google.com/books?id=1zmhHT7lIc0C&pg=PA46 .