Двойной счет (метод доказательства)

Тип метода доказательства

В комбинаторике двойной подсчет , также называемый подсчетом двумя способами , является комбинаторным методом доказательства , показывающим, что два выражения равны, демонстрируя, что они являются двумя способами подсчета размера одного множества . В этом методе, который ван Линт и Уилсон (2001) называют «одним из важнейших инструментов в комбинаторике», ^[1] описывается конечное множество с двух точек зрения, что приводит к двум различным выражениям для размера множества. Поскольку оба выражения равны размеру одного и того же множества, они равны друг другу.

Примеры

Умножение (натуральных чисел) коммутирует

Это простой пример двойного счета, часто используемый при обучении умножению маленьких детей. В этом контексте умножение натуральных чисел вводится как повторное сложение, а затем показывается, что оно коммутативно , путем подсчета двумя разными способами количества элементов, расположенных в прямоугольной сетке. Предположим, что сетка имеет строки и столбцы. Сначала мы подсчитываем элементы, суммируя строки элементов в каждой, затем во второй раз суммируя столбцы элементов в каждой, тем самым показывая, что для этих конкретных значений и , . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n\times m=m\times n}$

Формирование комитетов

Один из примеров метода двойного подсчета подсчитывает количество способов, которыми комитет может быть сформирован из людей, позволяя любому количеству людей (даже нулю из них) быть частью комитета. То есть, подсчитывается количество подмножеств , которые может иметь набор из -элементов. Один из методов формирования комитета заключается в том, чтобы попросить каждого человека выбрать, присоединяться к нему или нет. У каждого человека есть два выбора — да или нет — и эти выборы независимы от выборов других людей. Поэтому существуют возможности . В качестве альтернативы можно заметить, что размер комитета должен быть некоторым числом от 0 до . Для каждого возможного размера количество способов, которыми комитет людей может быть сформирован из людей, является биномиальным коэффициентом . Поэтому общее количество возможных комитетов является суммой биномиальных коэффициентов по . Приравнивание двух выражений дает тождество как частный случай биномиальной теоремы . Похожий метод двойного подсчета может быть использован для доказательства более общего тождества ^[2] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2\times 2\times \cdots 2=2^{n}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ $${\displaystyle {n \choose k}.}$$ ${\displaystyle k=0,1,2,\dots ,n}$ $${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n},}$$ $${\displaystyle \sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}}$$

Лемма о рукопожатии

Другая теорема, которая обычно доказывается с помощью аргумента двойного подсчета, гласит, что любой неориентированный граф содержит четное число вершин нечетной степени . То есть число вершин, имеющих нечетное число инцидентных ребер, должно быть четным. Говоря более разговорным языком, в группе людей, некоторые из которых пожимают друг другу руки, четное число людей должно пожать нечетное число рук другим людям; по этой причине результат известен как лемма о рукопожатии .

Чтобы доказать это двойным подсчетом, пусть будет степенью вершины . Количество инцидентностей вершины-ребра в графе можно подсчитать двумя способами: суммируя степени вершин или подсчитывая две инцидентности для каждого ребра. Следовательно, где - число ребер. Сумма степеней вершин, следовательно, является четным числом , что не могло бы произойти, если бы нечетное число вершин имело нечетную степень. Этот факт, с этим доказательством, появляется в статье Леонарда Эйлера 1736 года о семи мостах Кенигсберга, которая впервые положила начало изучению теории графов . ${\displaystyle d(v)}$ ${\displaystyle v}$ $${\displaystyle \sum _{v}d(v)=2e}$$ ${\displaystyle e}$

Подсчет деревьев

Формула Кэли подразумевает, что существует 1 = 2 ^{2 − 2} дерева на двух вершинах, 3 = 3 ^{3 − 2} дерева на трех вершинах и 16 = 4 ^{4 − 2} дерева на четырех вершинах.

Добавление направленного ребра к корневому лесу

Какое количество различных деревьев можно сформировать из набора различных вершин? Формула Кэли дает ответ . Айгнер и Циглер (1998) перечисляют четыре доказательства этого факта; они пишут о четвертом, доказательстве с двойным подсчетом, принадлежащем Джиму Питману, что оно «самое красивое из всех». ^[3] ${\displaystyle T_{n}}$ ${\displaystyle n}$ ${\displaystyle T_{n}=n^{n-2}}$

Доказательство Питмана подсчитывает двумя разными способами количество различных последовательностей направленных ребер, которые можно добавить к пустому графу на вершинах, чтобы сформировать из него корневое дерево . Направленные ребра направлены от корня. Один из способов сформировать такую ​​последовательность — начать с одного из возможных некорневых деревьев, выбрать одну из его вершин в качестве корня и выбрать одну из возможных последовательностей, в которую следует добавить ее (направленные) ребра. Таким образом, общее количество последовательностей, которые можно сформировать таким образом, равно . ^[3] ${\displaystyle n}$ ${\displaystyle T_{n}}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle n-1}$ ${\displaystyle T_{n}n(n-1)!=T_{n}n!}$

Другой способ подсчета этих последовательностей ребер — рассмотреть добавление ребер по одному к пустому графу и подсчитать количество вариантов, доступных на каждом шаге. Если уже добавлен набор ребер, так что граф, образованный этими ребрами, представляет собой корневой лес с деревьями, есть варианты для следующего ребра, которые нужно добавить: его начальная вершина может быть любой из вершин графа, а его конечная вершина может быть любым из корней, кроме корня дерева, содержащего начальную вершину. Поэтому, если умножить количество вариантов с первого шага, второго шага и т. д., общее количество вариантов будет Приравнивание этих двух формул для количества последовательностей ребер приводит к формуле Кэли: и Как описывают Айгнер и Циглер, формулу и доказательство можно обобщить для подсчета количества корневых лесов с деревьями для любого . ^[3] ${\displaystyle n-k}$ ${\displaystyle k}$ ${\displaystyle n(k-1)}$ ${\displaystyle n}$ ${\displaystyle k-1}$ $${\displaystyle \prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}$$ $${\displaystyle \displaystyle T_{n}n!=n^{n-2}n!}$$ $${\displaystyle \displaystyle T_{n}=n^{n-2}.}$$ ${\displaystyle k}$ ${\displaystyle k}$

Смотрите также

Дополнительные примеры

• Тождество Вандермонда — еще одно тождество сумм биномиальных коэффициентов, которое можно доказать двойным подсчетом. ^[4]
• Квадратное пирамидальное число . Равенство между суммой первых квадратных чисел и кубическим многочленом можно показать, дважды подсчитав тройки чисел , и , где больше любого из двух других чисел. ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle z}$
• Неравенство Любелла–Ямамото–Мешалкина . Доказательство Любелла этого результата для семейств множеств представляет собой аргумент двойного счета для перестановок , используемый для доказательства неравенства , а не равенства.
• Теорема Эрдёша–Ко–Радо , верхняя граница пересекающихся семейств множеств, доказанная Дьюлой О. Х. Катоной с использованием неравенства двойного подсчёта. ^[3]
• Доказательства малой теоремы Ферма . Доказательство делимости двойным подсчетом: для любого простого и натурального числа существуют слова длины над алфавитом из -символов, имеющие два или более различных символа. Их можно сгруппировать в наборы слов, которые можно преобразовать друг в друга циклическими сдвигами ; эти наборы называются ожерельями . Следовательно, (число ожерелий) и делится на . ^[4] ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle A^{p}-A}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle A^{p}-A=p\cdot {}}$ ${\displaystyle p}$
• Доказательства квадратичной взаимности . Доказательство Эйзенштейна выводит еще один важный факт теории чисел путем двойного подсчета точек решетки в треугольнике.

Похожие темы

• Биективное доказательство . В то время как двойной подсчет подразумевает подсчет одного множества двумя способами, биективные доказательства предполагают подсчет двух множеств одним способом, показывая, что их элементы соответствуют друг другу.
• Принцип включения-исключения — формула для размера объединения множеств , которая вместе с другой формулой для того же объединения может использоваться как часть аргумента о двойном подсчете.

Примечания

1. Ван Линт и Уилсон 2001.
2. Гарбано, Малерба и Левинтер 2003; Клавжар 2006).
3. Айгнер и Циглер 1998.
4. Джоши 2015.

Ссылки

• Айгнер, Мартин; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ , Springer-Verlag. Двойной счет описан как общий принцип на стр. 126; доказательство Питмана с двойным счетом формулы Кэли находится на стр. 145–146; неравенство Катоны с двойным счетом для теоремы Эрдёша–Ко–Радо находится на стр. 214–215.
• Эйлер, Л. (1736), «Решение проблемы ad geometriam situs pertinentis» (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Перепечатано и переведено в Biggs, NL; Lloyd, EK; Wilson, RJ (1976), Graph Theory 1736–1936 , Oxford University Press.
• Гарбано, М. Л.; Малерба, Дж. Ф.; Левинтер, М. (2003), «Гиперкубы и треугольник Паскаля: история двух доказательств», Mathematics Magazine , 76 (3): 216–217, doi :10.2307/3219324, JSTOR  3219324.
• Джоши, Марк (2015), «Двойной подсчет», Proof Patterns , Springer International Publishing, стр. 11–17, doi :10.1007/978-3-319-16250-8_2, ISBN 978-3-319-16249-2
• Клавжар, Санди (2006), «Подсчет гиперкубов в гиперкубах», Дискретная математика , 306 (22): 2964–2967, doi : 10.1016/j.disc.2005.10.036.
• ван Линт, Якобус Х.; Уилсон, Ричард М. (2001), Курс комбинаторики , Cambridge University Press, стр. 4, ISBN 978-0-521-00601-9.