Последовательность Гулда - Goulds sequence

Треугольник Паскаля, строки с 0 по 7. Количество нечетных целых чисел в строке я это я-е число в последовательности Гулда.
В самоподобный пилообразная форма последовательности Гулда

Последовательность Гулда является целочисленная последовательность названный в честь Генри В. Гулд что считает нечетные числа в каждом ряду Треугольник Паскаля. Он состоит только из силы двух, и начинается:[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, ... (последовательность A001316 в OEIS )

Например, шестое число в последовательности - 4, потому что в шестой строке треугольника Паскаля четыре нечетных числа (четыре жирных числа в последовательности 1, 5, 10, 10, 5, 1).

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

В п-ое значение в последовательности (начиная с п = 0) дает наибольшую степень двойки, которая делит центральный биномиальный коэффициент , и это дает числитель (выражается в виде дроби в наименьшем значении).[1]

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

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

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

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

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, ... (последовательность A000120 в OEIS )

в которой пth значение дает количество ненулевых битов в двоичное представление числа п, иногда записываемый в математических обозначениях как .[1][2] Эквивалентно п-ое значение в последовательности Гулда равно

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

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

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, ... ( последовательность A006046 в OEIS )

посчитайте все нечетные числа в первом п ряды треугольника Паскаля. Эти числа растут пропорционально , но с константой пропорциональности, которая периодически колеблется между 0,812556 ... и 1 в зависимости от бревно п.[6][7]

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

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

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

История

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

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

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

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