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

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

Примеры

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

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

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

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

$${n \choose k}.$$

Следовательно, общее количество возможных комитетов представляет собой сумму биномиальных коэффициентов по $k=0,1,2,\dots ,n$. Приравнивание двух выражений дает тождество

$$\sum _{k=0}^{n}{n \choose k}=2^{n},$$

частный случай биномиальной теоремы . Подобный метод двойного счета можно использовать для доказательства более общего тождества.

$$\sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}$$

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

Основная статья: Лемма о рукопожатии

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

Чтобы доказать это двойным счетом, пусть $d(v)$ быть степенью вершины $v$. Количество инцидентов вершин и ребер в графе можно подсчитать двумя разными способами: путем суммирования степеней вершин или путем подсчета двух инцидентов для каждого ребра. Поэтому

$$\sum _{v}d(v)=2e$$

где $e$это количество ребер. Таким образом, сумма степеней вершин представляет собой четное число , чего не могло бы произойти, если бы нечетное число вершин имело нечетную степень. Этот факт вместе с этим доказательством появляется в статье Леонарда Эйлера 1736 года о семи мостах Кенигсберга, которая впервые положила начало изучению теории графов .

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

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

Добавление направленного края в корневой лес

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

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

Другой способ подсчитать эти последовательности ребер — рассмотреть возможность добавления ребер по одному в пустой граф и подсчитать количество вариантов, доступных на каждом шаге. Если кто-то добавил коллекцию $n-k$ уже ребра, так что граф, образованный этими ребрами, представляет собой корневой лес с $k$ деревья, есть $n(k-1)$ выбор следующего ребра для добавления: его начальной вершиной может быть любая из $n$ вершины графа, а его конечная вершина может быть любой из $k-1$корни, отличные от корня дерева, содержащего начальную вершину. Следовательно, если перемножить количество вариантов первого шага, второго шага и т. д., общее количество вариантов составит

$$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.$$

Приравнивание этих двух формул для количества последовательностей ребер приводит к формуле Кэли:

$$\displaystyle T_{n}n!=n^{n-2}n!$$

и

$$\displaystyle T_{n}=n^{n-2}.$$

Как описывают Айгнер и Циглер, формулу и доказательство можно обобщить для подсчета количества корневых лесов с $k$ деревья, для любого $k$.

См. также

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

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

Связанные темы

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

Ссылки

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