Gouldsche Folge

Die selbstähnliche Sägezahnform der Gouldschen Folge.

Die Gouldsche Folge (englisch Gould’s sequence [guːldz ˈsiːkwəns]) ist eine ganzzahlige, nach Henry W. Gould benannte Folge, die die ungeraden Zahlen in jeder Zeile des Pascalschen Dreiecks zählt. Sie besteht ausschließlich aus Zweierpotenzen und beginnt mit:^[1][2]

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, … Folge A001316 in OEIS

Zum Beispiel ist die sechste Zahl in dieser Folge die 4, weil es vier ungerade Zahlen in der sechsten Zeile des Pascalschen Dreiecks gibt, die vier markierten Zahlen in der Folge 1, 5, 10, 10, 5, 1.

Geschichte

Die Folge ist nach Henry W. Gould benannt, der sie in den frühen 1960er Jahren studierte. Allerdings war die Tatsache, dass diese Zahlen Zweierpotenzen darstellen, wobei der Exponent der n-ten Zahl gleich der Anzahl der Einsen in der binären Darstellung von ${\displaystyle n}$ ist, bereits J. W. L. Glaisher im Jahre 1899 bekannt.^[3][4]

Der Nachweis, dass die Zahlen in Gouldschen Folge Zweierpotenzen darstellen, wurde als Aufgabe in der William Lowell Putnam Mathematical Competition von 1956 gestellt.^[5]

Weitere Interpretationen

Der n-te Wert in der Folge, ausgehend von n = 0), ergibt die höchste Zweierpotenz, die den mittleren Binomialkoeffizienten ${\displaystyle {\tbinom {2n}{n}}}$, und den Zähler von ${\displaystyle 2^{n}/n!}$ (ausgedrückt als vollständig gekürzter Bruch), teilt.^[1]

Sierpinski-Dreieck, das durch Regel 90 erzeugt wird, oder durch Markieren der Positionen ungerader Zahlen im Pascalschen Dreieck. Die Gouldsche Folge zählt die Anzahl der lebenden Zellen in jeder Zeile dieses Musters.

Die Gouldsche Folge ergibt auch die Anzahl der lebenden Zellen in der n-ten Generation des zellulären Automaten der Regel 90, ausgehend von einer einzigen lebenden Zelle.^[1][6] Sie hat eine charakteristische exponentiell wachsende Sägezahnform, die verwendet werden kann, um physikalische Prozesse zu identifizieren, die sich ähnlich wie Regel 90 verhalten.^[7]

Verwandte Folgen

Die binären Logarithmen (Exponenten der Zweierpotenzen) der Gouldschen Folge bilden selbst eine ganzzahlige Folge,

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, … Folge A000120 in OEIS,

in welcher der n-te Wert die Anzahl der gesetzten Bits in der binären Darstellung der Zahl n ergibt, die manchmal in der mathematischen Notation als ${\displaystyle \#_{1}(n)}$ dargestellt wird.^[1][2] Äquivalent dazu ist der n-te Wert in Gouldschen Folge

${\displaystyle 2^{\#_{1}(n)}.}$

Wenn man die Folge der Exponenten modulo zwei nimmt, ergibt sich die Thue–Morse Folge.^[8]

Die Partialsummen der Gouldschen Folge,

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, … Folge A006046 in OEIS

zählen alle ungeraden Zahlen in den ersten n Reihen des Pascalschen Dreiecks. Diese Zahlen wachsen proportional zu ${\textstyle n^{\log _{2}3}\approx n^{1.585}}$, aber mit einer Proportionalitätskonstante die zwischen 0,812556… und 1 periodisch als Funktion von ${\textstyle \log n}$ oszilliert.^[9][10]

Rekursive Konstruktion und Selbstähnlichkeit

Die ersten ${\textstyle 2^{i}}$ Werte der Gouldschen Folge können durch die rekursive Konstruktion der ersten ${\textstyle 2^{i-1}}$Werte und der Verkettung der Zweifachen der ersten ${\textstyle 2^{i-1}}$ Werte konstruiert werden. Zum Beispiel erzeugt die Verkettung der ersten vier Werte 1, 2, 2, 4 mit ihren Zweifachen 2, 4, 4, 8 die ersten acht Werte. Wegen dieser verdoppelnden Konstruktion erfolgt das erste Auftreten jeder Zweierpotenz ${\textstyle 2^{i}}$ in dieser Folge an der Position ${\textstyle 2^{i}-1}$.^[1]

Die Gouldsche Folge, die Folge der Exponenten der Zweierpotenzen und die Thue–Morse Folge sind alle selbstähnlich: Sie haben die Eigenschaft, dass die Teilfolge von Werten an geraden Positionen in der ganzen Folge gleich der ursprünglichen Sequenz ist, eine Eigenschaft, die sie auch mit einigen anderen Folgen wie zum Beispiel der Stern-Brocot-Folge teilen.^[11][12][13] In der Gouldschen Folge sind die Werte an ungeraden Stellen doppelt so groß wie ihr jeweiliger Vorgänger, während in der Folge der Exponenten die Werte an ungeraden Stellen um eins größer sind als der Vorgänger.

Einzelnachweise

1. N. J. A. Sloane: Sloane’s A001316. Gould’s sequence. In: The On-Line Encyclopedia of Integer Sequences. OEIS Foundation, abgerufen am 25. Februar 2017 (englisch). 
2. George Pólya, Robert Tarjan, Donald R. Woods: Notes on Introductory Combinatorics (= Progress in Computer Science and Applied Logic). Birkhäuser, Boston 1983, ISBN 0-8176-4953-0, S. 21, doi:10.1007/978-0-8176-4953-1 (books.google.com [abgerufen am 25. Februar 2017]). 
3. Andrew Granville: Zaphod Beeblebrox’s brain and the fifty-ninth row of Pascal's triangle. In: American Mathematical Monthly. Band 99, Nr. 4, 1992, S. 318–331, doi:10.2307/2324898. 
4. James Whitbread Lee Glaisher: On the residue of a binomial-theorem coefficient with respect to a prime modulus. In: The Quarterly Journal of Pure and Applied Mathematics. Band 30, 1899, S. 150–156 (books.google.com [abgerufen am 25. Februar 2017]). 
5. Andrew M. Gleason, R.E. Greenwood, Leroy Milton Kelly: The William Lowell Putnam Mathematical Competition: Problems and Solutions: 1938–1964. Hrsg.: Mathematical Association of America. 1980, ISBN 978-0-88385-462-4, S. 46 (books.google.com [abgerufen am 25. Februar 2017]). 
6. Stephen Wolfram: Geometry of binomial coefficients. In: American Mathematical Monthly. Band 91, Nr. 9, 1984, S. 566–571, doi:10.2307/2323743. 
7. Jens Christian Claussen, Jan Nagler, Heinz Georg Schuster: Sierpinski signal generates 1∕f ^α spectra. In: Physical Review E. Band 70, Nr. 3. American Physical Society, September 2004, S. 032101, doi:10.1103/PhysRevE.70.032101, arxiv:cond-mat/0308277, bibcode:2004PhRvE..70c2101C (4 S.). 
8. Sam Northshield: Sums across Pascal’s triangle mod 2. In: Congressus Numerantium. Band 200, 2010, S. 35–52 (digitalcommons.plattsburgh.edu [PDF; 225 kB; abgerufen am 25. Februar 2017]).  digitalcommons.plattsburgh.edu (Memento vom 10. September 2015 im Internet Archive)
9. Heiko Harborth: Number of odd binomial coefficients. In: Proceedings of the American Mathematical Society. Band 62, Nr. 1, 1976, S. 19–22, doi:10.2307/2041936. 
10. G. Larcher: On the number of odd binomial coefficients. In: Acta Mathematica Hungarica. Band 71, Nr. 3, 1996, S. 183–203, doi:10.1007/BF00052108. 
11. Stephen Wolfram: Geometry of binomial coefficients. In: American Mathematical Monthly. Band 91, Nr. 9, 1984, S. 566–571, doi:10.2307/2323743. 
12. Michael Gilleland: Some Self-Similar Integer Sequences. In: The On-Line Encyclopedia of Integer Sequences. OEIS Foundation, abgerufen am 25. Februar 2017 (englisch). 
13. Manfred Schroeder: Fractal Horizons. Hrsg.: Clifford A. Pickover. St. Martin’s Press, New York 1996, Fractals in Music, S. 207–223.