Gouldsche 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:

Die selbstähnliche Sägezahnform der Gouldschen Folge.

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 $n$ ist, bereits J. W. L. Glaisher im Jahre 1899 bekannt.

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

Weitere Interpretationen

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

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. Sie hat eine charakteristische exponentiell wachsende Sägezahnform, die verwendet werden kann, um physikalische Prozesse zu identifizieren, die sich ähnlich wie Regel 90 verhalten.

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 $\#_{1}(n)$ dargestellt wird. Äquivalent dazu ist der n-te Wert in Gouldschen Folge

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

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

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.

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}$.

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. 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.