Степень тройки
В математикe «степень трех» — это число вида 3n, где n — это целое число, то есть результат возведение в степень с числом три в качестве возводителя в степень и целым числом n в качестве экспонента. Первые десять неотрицательных степеней из трех равны:
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 и т. д. (последовательность A000244 в OEIS)
Приложения[править]
Степени трех обозначают место в троичной системе счисления.[1]
Теория графов[править]
В теории графов степени тройки отображаются в зависимости Муна-Мозера 3 n/ 3 от числа максимального независимого множества n-вершин графа,[2] = и во временном анализе алгоритма Брона — Кербоша для нахождения этих множеств.[3] Несколько важных сильно регулярных графов также имеют число вершин, равное трем, включая Граф Брауэра — Хемерса (81 вершина), Граф Берлекэмпа — ван Линта — Зейделя (243 вершины) и Граф Геймса (729 вершин).[4]
Перечислительная комбинаторика[править]
В перечислительной комбинаторике есть 3 n подписанный наборе множества n элементов. В комбинаторике многогранников гиперкуб и все другие многогранники Ханнера имеют число граней (не считая пустого множества в качестве грани), равное трем. Например, 2-куб, или квадрат, имеет 4 вершины, 4 ребра и 1 грань, а 4 + 4 + 1 = 32. Гипотеза Калаи 3 d утверждает, что это минимально возможное число граней для центрально-симметричного многогранника.[5]
Обратная степень трех длин[править]
В занимательной математике и Фрактал обратная степень трех длин встречается в конструкциях, ведущих к снежинке Коха,[6] Канторово множество,[7] Ковер Серпинского и Губка Менгера, в количестве элементов на этапах построения Треугольника Серпинского и во многих формулах, связанных с этими множествами. Существуют 3 n возможные состояния в головоломке n-диске Ханойская башня или вершины в связанном с ней Ханойском графе.[8] В задачах на взвешивание с w шагами взвешивания возможны 3 w возможные исходы (последовательности, в которых весы наклоняются влево или вправо или остаются сбалансированными); степени трех часто возникают в были найдены решения этих головоломок, и было высказано предположение, что (по аналогичным причинам) степени трех могли бы составить идеальную систему монет.[9]
Совершенные постоянные числа[править]
В теории чисел все степени тройки равны совершенному тотиентному числу.[10] Суммы различных степеней троичности образуют Последовательность Стэнли, лексикографически наименьшую последовательность, которая не содержит арифметической прогрессии из трех элементов.[11] В гипотезе Пола Эрдеша утверждается, что эта последовательность не содержит степени двойки, кроме 1, 4 и 256.[12]
Число Грэма[править]
Число Грэма, огромное число, возникающее из математического доказательства в теории Рэмси, является (в версии, популяризированной Мартином Гарднером) степенью трех. Однако при фактической публикации доказательства Рональдом Грэмом использовалось другое число, которое является степенью двойки и намного меньше.[13]
См. также[править]
Источники[править]
- ↑ «», DOI 10.5951/В.15.8.0718
- ↑ Moon, J. W. & Moser, L. (1965), "«On cliques in graphs»", Израильский математический журнал Т. 3: 23–28, DOI 10.1007/BF02760024
- ↑ Tomita, Etsuji; Tanaka, Akira & Takahashi, Haruhisa (2006), "«The worst-case time complexity for generating all maximal cliques and computational experiments»", Theoretical Computer Science Т. 363 (1): 28–42, DOI 10.1016/j.tcs.2006.06.015
- ↑ Графики Брауэра-Хемерса и Геймса смотрите здесь Bondarenko, Andriy V. & Radchenko, Danylo V. (2013), "«On a family of strongly regular graphs with »", Journal of Combinatorial Theory, Series B Т. 103 (4): 521–531, DOI 10.1016/j.jctb.2013.05.005. For the Berlekamp-van Lint-Seidel and Games graphs, see van Lint, J. H. & Brouwer, A. E. (1984), "Strongly regular graphs and partial geometries", in Jackson, David M. & Vanstone, Scott A., «Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982», London: Academic Press, сс. 85–122
- ↑ Kalai, Gil (1989), "«The number of faces of centrally-symmetric polytopes»", Graphs and Combinatorics Т. 5 (1): 389–391, DOI 10.1007/BF01788696
- ↑ von Koch, Helge (1904), "«На непрерывной кривой без касательной, полученной с помощью элементарной геометрической конструкции»", Arkiv för Matematik Т. 1: 681–704, <https://babel.hathitrust.org/cgi/pt?id=inu.30000100114564;view=1up;seq=673>
- ↑ See, e.g., Mihăilă, Ioana (2004), "«Рациональные значения множества Кантора»", Математический журнал колледжа Т. 35 (4): 251–255, DOI 10.2307/4146907
- ↑ Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš & Petr, Ciril (2013), "2.3 Hanoi graphs", «The tower of Hanoi—myths and maths», Basel: Birkhäuser, сс. 120–134, ISBN 978-3-0348-0236-9, DOI 10.1007/978-3-0348-0237-6
- ↑ Telser, L. G. (1995-10), "«Optimal denominations for coins and currency»", Economics Letters Т. 49 (4): 425–427, DOI 10.1016/0165-1765(95)00691-8
- ↑ Iannucci, Douglas E.; Deng, Moujie & Cohen, Graeme L. (2003), "«On perfect totient numbers»", Journal of Integer Sequences Т. 6 (4): Article 03.4.5, <https://cs.uwaterloo.ca/journals/JIS/VOL6/Cohen2/cohen50.html>
- ↑ Шаблон:Cite OEIS
- ↑ Gupta, Hansraj (1978), "«Powers of 2 and sums of distinct powers of 3»", Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika (no. 602–633): 151–158 (1979)
- ↑ Gardner, Martin (1977-11), "«In which joining sets of points leads into diverse (and diverting) paths»", Scientific American Т. 237 (5): 18–28, DOI 10.1038/scientificamerican1177-18
