10.10.2017 14:00
igorm6387 21 2600 Источник
Сочетанием из $n$ по $k$ называется выборка из $k$ элементов, взятая на множестве содержащем $n$ элементов. Один и тот же элемент нельзя выбирать несколько раз; порядок, в котором нам предъявляют решение об избранности того или иного элемента не учитывается. Число всех возможных сочетаний из $n$ по $k$ равно $С_n^k$ — коэффициенту в биноме Ньютона. Факт известный каждому школьнику: о нём можно прочитать в википедии или любом учебнике, где вообще упомянаются сочетания и комбинаторика.

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

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

Давайте начнём с конкретного примера. Возьмём сумму $(a + b)$ и возведём её в какую-то степень, например в четвёртую.

$(a + b)^4 = (a + b)(a + b)(a + b)(a + b).$


Раскроем скобки справа, при этом не будем приводить подобные слагаемые, использовать при записи степени, а так же забудем на минуту о коммутативности умножения, т.е. не будем менять порядок множителей в слагаемых:

$ (a + b)^4 = $


$ (a + b)(a + b)(a + b)(a + b) = $


$ ((a + b)(a + b))((a + b)(a + b)) = $


$ (aa + ab + ba + bb)(aa + ab + ba + bb) = $


$ aa(aa + ab + ba + bb) + ab(aa + ab + ba + bb) + $


$ ba(aa + ab + ba + bb) + bb(aa + ab + ba + bb) = $


$ aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb + $


$ baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb. $


Давайте думать о слагаемых в итоговом многочлене как о символьных строках. Мы получили 16 строк длиной 4 символа. Понять, почему именно 16 несложно. Каждый раз, когда мы умножаем на скобку, содержащую 2 слагаемых, мы увеличиваем число элементов в конечном результате в два раза. Всего мы перемножили 4 скобки с двумя слагаемыми, т.е. в итоге получили $2 \times 2 \times 2 \times 2 = 2^4 = 16$.

Будем считать, что если в строке элемент равен $a$, то он не «выбран», а если $b$, то «выбран». В таком случае строка $aaaa$ соответствует случаю, когда из 4-х элементов не выбрали ни одного, а строка $bbbb$ — случаю когда все элементы выбраны.

Предположим теперь, что мы хотим ответить на вопрос «сколькими способами можно выбрать два элемента из четырёх». С учётом нашей договорённости, всё что нам надо сделать — это посчитать количество строк, в которых ровно две буквы $b$: $aabb, abab, abba, baab, baba, bbaa$. Их ровно шесть.

Теперь вспомним о коммутативности умножения и о нотации «степень». Все эти строки можно записать как $a^2b^2$, и в исходной сумме мы получим:

$aabb + abab + abba + baab + baba + bbaa = $


$ a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 = $


$ 6a^2b^2.$


Коэффициент 6 и есть ответ на наш вопрос про количество способов выбора двух элементов. Не удивительно, ведь когда мы приводим подобные слагаемые, то подсчитываем количество множителей, в которых $a$ и $b$ входят в одинаковой степени. То есть подсчитываем число строк, в которых «выбрано» одно и то же число элементов.

Вернёмся к начальной сумме и приведём все слагаемые. Для наглядности я в явном виде буду записывать коэффициент 1 и буду использовать тот факт, что $a^0 = b^0 = 1$.

$(a + b)^4 = 1a^4b^0 + 4a^3b^1 + 6a^2b^2 + 4a^1b^3 + 1a^0b^4. $


В такой записи чтобы узнать количество способов выбора $k$ элементов из $4$ достаточно просто посмотреть на коэффициент перед слагаемым в котором $b$ входит в $k$-ой степени.

Кстати, обратите внимание, что $1 + 4 + 6 + 4 + 1 = 16 = 2^4$. Это еще одно свойство биномальных коэффициентов, которое становится очевидным, если вспомнить, что мы начинали с многочлена в котором $2^4$ слагаемых.

Для общего случая

$(a + b)^n = C_n^0a^nb^0 + C_n^1a^{n-1}b^1 + ... + C_n^na^0b^n$



$\sum_{k=0}^{n}{C_n^k} = 2^n.$


Нотация очень простая: у $C$ снизу стоит $n$ — степень скобки, сверху $k$ — степень, в которой в слагаемом стоит $b$.

Или, как мы теперь знаем, $n$ это количество элементов в множестве, из которого мы делаем выборку, $k$ — количество элементов, которые мы выбираем.

Добавлю, что обычно определение биномального коэффициента даётся не через произведение $a$ и $b$, а через произведение $(1 + х)^n$ и в многочление, который получается в итоге, есть только $х$ (т.к. при $a = 1$ любая степень $a$ равна еденице). Суть от этого не меняется, но заметить комбинаторную сущность получившийся формулы становится сложнее.

Комментарии (21)


  1. ukhegg
    10.10.2017 18:43
    #10465340
    +8

    Кому-нибудь еще показалось, что первая лекция курса теории вероятности(ну или другого мат. курса, в который входит комбинаторика), пересказанная своими словами, не стоит целой статьи на хабре? Хабр деградирует или у меня завышенные ожидания?


    1. igorm6387 Автор
      10.10.2017 19:10
      #10465402
      -3

      Не знаю, гордиться мне или стыдиться. Хотя курс теории вероятности мне в своё время читали, но в явном виде объяснений изложенного я не слышал (и не встречал в литературе). Так что содержимое статьи — моё собственное «математическое открытие». Надеюсь кому-то ещё оно будет интересно.


      1. ver-sta
        11.10.2017 01:17
        #10465856
        +1

        нет «теории вероятностИ», есть «теория вероятностЕЙ»


      1. saluev
        11.10.2017 01:30
        #10465872
        +2

        Много литературы прошерстили, чтобы написать это высокопарное «не встречал в литературе»? :)


        1. igorm6387 Автор
          11.10.2017 13:58
          #10466540

          Нет, не много. Я вроде бы и не претендую на глубокие математические знания. Лишь хотел подчеркнуть, что содержимое статьи это не пересказ чего бы то ни было.


          1. saluev
            11.10.2017 14:29
            #10466650

            Это называется «изобрести велосипед». Незнание конструкции велосипеда не означает, что вы создаёте что-то новое, переизобретая её. Не надо писать статьи на темы, в которых вы разбираетесь настолько плохо, что не в курсе базовых достижений человечества.


            1. igorm6387 Автор
              11.10.2017 14:56
              #10466704

              Нельзя понять решение задачи, просто прочитав ответ в конце учебника. В лучшем случае у вас просто появиться иллюзия «знаю», «могу». Настоящее понимание приходит когда над задачей вы долго бились самостоятельно и наконец нашли решение. Я взялся написать о биномиальных коэффициентах только потому что «изобрел велосипед».


              1. saluev
                11.10.2017 15:05
                #10466734
                +1

                Я же не предлагаю вам отказаться от решения задач. Просто сообщаю, что не обязательно всех извещать о своих успехах в учёбе :)


  1. neurocore
    10.10.2017 18:51
    #10465356
    +1

    Материал слабоват. Но я с удовольствием почитал бы доказательства множества различных уравнений с биномиальными коэффициентами (но правда соответствует ли эта тематика хабру?)


    1. igorm6387 Автор
      10.10.2017 19:04
      #10465388

      Был бы признателен если бы вы ткнули меня носом на что-то вроде хабра, но математической направленности.


      1. neurocore
        10.10.2017 20:18
        #10465538
        +1

        К сожалению, ничего не припоминаю. Мой основной посыл был в том, что было бы неплохо написать о немного более нетривиальных вещах.


    1. sashagil
      11.10.2017 05:27
      #10465936
      +1

      Если вам любопытны элементарные доказательства (на уровне первых лет занятий школьного маткружка, без утомительной технической / механической работы с алгебраическими преобразованиями), рекомендую полистать книгу «Proofs That Really Count: The Art of Combinatorial Proof» (pdf можно найти в интернетах) — там авторы собрали / придумали довольно длинный ряд доказательств комбинаторных тождеств (уравнений с биномиальными коэффициентами в том числе) «на пальцах» — например, подсчитывая количество способов составить прямоугольник 2xN из N доминошек разными путями.

      Не помню, приводят ли они рядом алгебраические доказательства (суть книги — именно в нахождении способов доказательств «на пальцах»!), но точно помню, что ближе к концу они дают сводку тождеств, к которым они доказательств «на пальцах» пока не нашли :). Перевода на русский вроде нет; я на досуге посмотрю из любопытства, не переводил ли / не пересказывал ли кто фрагментарно.


  1. ver-sta
    10.10.2017 18:52
    #10465364
    -1

    «биномальными коэффициентами»

    всегда они были биномиальными коэффициентами


  1. GeMir
    10.10.2017 20:56
    #10465604
    -2

    Любопытная у вас запись. За годы учёбы встречал лишь «стандартную»:

    image


    1. Hixon10
      10.10.2017 22:01
      #10465680

      Ваша запись — мировой стандарт, а запись автора статьи — стандарт из СССР-овских вузов.


      1. ver-sta
        11.10.2017 01:23
        #10465864

        А причем здесь СССР-овские вузы, Математическая энциклопедия говорит, что обозначение $C_n^k$ появилось в 19 веке.


        1. Hixon10
          11.10.2017 08:01
          #10465994
          +1

          Я, к сожалению, не знаю, когда эта запись появилась. Я лишь вижу, что студенты из российских вузов часто используют $C_n^k$, когда во всех статьях на английском языке используется вышеприведенная запись.


          1. masai
            12.10.2017 13:51
            #10468628

            А ещё студенты российских вузов пишут tg вместо tan и отделяют дробную часть запятой. Вопрос привычки.


      1. WRONGWAY4YOU
        11.10.2017 13:59
        #10466542

        Не только СССР-овские вузы использовали данную нотацию.


        Из Википедии:


        The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by C(n ,k) or by a variation such as $C{k^n}$, {}{n}C{k}, ${}^{n}C{k}$, $C{n,k}$ or even $C{n}^{k}$ (the latter form was standard in French, Romanian, Russian, Chinese and Polish texts).


  1. KvanTTT
    10.10.2017 21:00
    #10465616

    Также есть более обобщенные мультиномиальные коэффициенты. Про них было бы интересней.


  1. crocodile2u
    11.10.2017 13:26
    #10466428
    +1

    Раньше для меня ьыло так:


    abba = Happy New Year


    А теперь тупо


    abba = a2b2


    Мир никогда не будт прежним...