последовательность Гулда

Целочисленная последовательность

Треугольник Паскаля, строки с 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 ). Последовательность Гулда также является фрактальной последовательностью .

Дополнительные интерпретации

n - е значение в последовательности (начиная с n = 0 ) дает высшую степень 2, которая делит центральный биномиальный коэффициент , и дает числитель (выраженный как дробь в самых низких терминах). ^[1] ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle 2^{n}/n!}$

Треугольник Серпинского, созданный по правилу 90 или путем маркировки положений нечетных чисел в треугольнике Паскаля . Последовательность Гулда подсчитывает количество живых клеток в каждой строке этого шаблона.

Последовательность Гулда также дает количество живых клеток в n -м поколении клеточного автомата Правила 90, начиная с одной живой клетки. ^{[1] [3]} Он имеет характерную растущую пилообразную форму, которую можно использовать для распознавания физических процессов, которые ведут себя аналогично Правилу 90. ^[4]

Связанные последовательности

Двоичные логарифмы (показатели степени двойки) последовательности Гулда сами образуют целочисленную последовательность:

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... (последовательность A000120 в OEIS )

в котором n -е значение дает количество ненулевых битов в двоичном представлении числа n , иногда записываемого в математической записи как . ^{[1] [2]} Эквивалентно, n -е значение в последовательности Гулда равно ${\displaystyle \#_{1}(n)}$

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

Взятие последовательности показателей по модулю два дает последовательность Туэ – Морса . ^[5]

Частичные суммы последовательности Гулда,

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... (последовательность A006046 в OEIS )

посчитайте все нечетные числа в первых n строках треугольника Паскаля. Эти числа растут пропорционально , ​​но с константой пропорциональности, которая колеблется между 0,812556... и 1, периодически в зависимости от log n . ^{[6] [7]} ${\displaystyle n^{\log _{2}3}\approx n^{1.585}}$

Рекурсивное построение и самоподобие

Первые 2 значения ⁱ в последовательности Гулда могут быть созданы путем рекурсивного построения первых 2 ^{i - 1} значений, а затем объединения двойников первых 2 ^{i - 1} значений. Например, объединение первых четырех значений 1, 2, 2, 4 с их дублями 2, 4, 4, 8 дает первые восемь значений. Из-за этой конструкции удвоения первое появление каждой степени двойки 2 ⁱ в этой последовательности находится в позиции 2 ⁱ − 1 . ^[1]

Последовательность Гулда, последовательность ее показателей и последовательность Туэ-Морса самоподобны : они обладают тем свойством, что подпоследовательность значений в четных позициях во всей последовательности равна исходной последовательности, свойство, которое они также разделяют с некоторыми другими. последовательности, такие как двухатомная последовательность Стерна . ^{[3] [8] [9]} В последовательности Гулда значения в нечетных позициях в два раза больше своих предшественников, тогда как в последовательности показателей степени значения в нечетных позициях равны единице плюс их предшественники.

История

Последовательность названа в честь Генри Гулда , который изучал ее в начале 1960-х годов. Однако тот факт, что эти числа являются степенями двойки, причем показатель степени n -го числа равен количеству единиц в двоичном представлении n , был уже известен Дж. У. Л. Глейшеру в 1899 году. [ ^{10] [11]}

Доказательство того, что числа в последовательности Гулда являются степенями двойки, было поставлено в качестве задачи на Математическом соревновании Уильяма Лоуэлла Патнэма в 1956 году . ^[12]

Рекомендации

1. Sloane, Нью-Джерси (ред.). «Последовательность A001316 (последовательность Гулда)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
2. Полиа, Джордж ; Тарьян, Роберт Э .; Вудс, Дональд Р. (2009), Заметки по вводной комбинаторике, прогрессу в области информатики и прикладной логики, том. 4, Спрингер, с. 21, ISBN 9780817649531.
3. Вольфрам, Стивен (1984), «Геометрия биномиальных коэффициентов», American Mathematical Monthly , 91 (9): 566–571, ​​doi : 10.2307/2323743, JSTOR  2323743, MR  0764797.
4. Клауссен, Йенс Кристиан; Наглер, Ян; Шустер, Хайнц Георг (2004), «Сигнал Серпинского генерирует 1/ f ^α- спектры», Physical Review E , 70 (3): 032101, arXiv : cond-mat/0308277 , Bibcode : 2004PhRvE..70c2101C, doi : 10.1103/PhysRevE .70.032101, PMID  15524560, S2CID  39929111 .
5. Нортшилд, Сэм (2010), «Суммы по модулю треугольника Паскаля 2», Congressus Numerantium , 200 : 35–52, MR  2597704, заархивировано из оригинала 10 сентября 2015 г. , получено 10 сентября 2016 г..
6. Харборт, Хейко (1976), «Количество нечетных биномиальных коэффициентов», Труды Американского математического общества , 62 (1): 19–22, doi : 10.2307/2041936 , JSTOR  2041936, MR  0429714.
7. Ларчер, Г. (1996), «О количестве нечетных биномиальных коэффициентов», Acta Mathematica Hungarica , 71 (3): 183–203, doi : 10.1007/BF00052108, MR  1397551, S2CID  121576268.
8. Гиллеланд, Майкл, Некоторые самоподобные целочисленные последовательности, OEIS , получено 10 сентября 2016 г..
9. Шредер, Манфред (1996), «Фракталы в музыке», в Пиковере, Клиффорд А. (редактор), Fractal Horizons , Нью-Йорк: St. Martin's Press, стр. 207–223. Цитируется Гиллеландом.
10. Гранвилл, Эндрю (1992), «Мозг Зафода Библброкса и пятьдесят девятая строка треугольника Паскаля», American Mathematical Monthly , 99 (4): 318–331, doi : 10.2307/2324898, JSTOR  2324898, MR  1157222.
11. Глейшер, JWL (1899), «О вычете коэффициента биномиальной теоремы относительно простого модуля», Ежеквартальный журнал чистой и прикладной математики , 30 : 150–156. См., в частности, последний абзац стр. 156.
12. Глисон, Эндрю М .; Гринвуд, RE; Келли, Лерой Милтон , ред. (1980), Математическое соревнование Уильяма Лоуэлла Патнэма: проблемы и решения: 1938–1964, Математическая ассоциация Америки, стр. 46, ISBN 9780883854624.