Комбинаторика. Шестизначное число из трёх цифр.

[Charlz_Klug]

Здравствуйте! От нечего делать изучаю комбинаторику. Читаю книгу Виленкина "Комбинаторика" 2006 год.

Цитата:

Задача № 46: Сколько шестизначных чисел содержат ровно три различные цифры?

Застрял на этой задаче. Никак не получается решить. Что-то я не допонимаю. Есть в этой книге и решение:

Цитата:

Проводим непосредственный подсчёт с учётом трёх моментов появления в числе новой цифры. Этот момент будет на 1-й цифре (9 вариантов первой цифры - любая кроме 0), на 2 - 5-й (9 вариантов - любая кроме первой) и ещё на одном месте (восемь ещё не использованных цифр), другие цифры придётся выбирать из числа уже появившихся. Это приводит к ответу в виде суммы 10 слагаемых:
$9 \cdot 1 \cdot 1 \cdot 1 \cdot 9 \cdot 8 = 648$,
$9 \cdot 1 \cdot 1 \cdot 9 \cdot 2 \cdot 8 = 1296$,
$9 \cdot 1 \cdot 1 \cdot 9 \cdot 8 \cdot 3 = 1944$,
$9 \cdot 1 \cdot 9 \cdot 2 \cdot 2 \cdot 8 = 2592$,
$9 \cdot 1 \cdot 9 \cdot 2 \cdot 8 \cdot 3 = 3888$,
$9 \cdot 1 \cdot 9 \cdot 8 \cdot 3 \cdot 3 = 5832$,
$9 \cdot 9 \cdot 2 \cdot 2 \cdot 2 \cdot 8 = 5184$,
$9 \cdot 9 \cdot 2 \cdot 2 \cdot 8 \cdot 3 = 7776$,
$9 \cdot 9 \cdot 2 \cdot 8 \cdot 3 \cdot 3 = 11664$,
$9 \cdot 9 \cdot 8 \cdot 3 \cdot 3 \cdot 3 = 17496$,
$648 + 1296 + 1944 + 2592 + 3888 + 5832 + 5184 + 7776 + 11664 + 17496 = 58320$

В случае с $9 \cdot 9 \cdot 8 \cdot 3 \cdot 3 \cdot 3 = 17496$ понятно: на месте первой цифры может быть одна из цифр $\{1,2,3,4,5,6,7,8,9\}$, то есть, все цифры из $\{0,1,2,3,4,5,6,7,8,9\}$, за исключением нуля (с нуля число начинаться не может), итого: 9 цифр. На месте второй цифры могут быть $\{0,1,2,3,4,5,6,7,8,9\}$ за исключением цифры, выбранной в качестве первой, итого: $10 - 1 =9$ цифр. В качестве третьей цифры можно выбрать одну из оставшихся после предыдущих выборов цифру, итого: $10 - 2 = 8$ цифр. В качестве четвёртой цифры можно выбрать любую из трёх цифр, выбранных для первой, второй и третьей цифры, итого: 3 цифры. В качестве пятой цифры, можно выбрать любую из трёх цифр, выбранных для первой, второй и третьей цифры, итого: 3 цифры. В качестве шестой цифры, любую из трёх цифр, выбранных для первой, второй и третьей цифры, итого: 3 цифры. И результат: $9 \cdot 9 \cdot 8 \cdot 3 \cdot 3 \cdot 3 = 17496$. А вот как дальше рассуждать - не пойму. Подскажите, пожалуйста, с последующими рассуждениями.

[ИСН]

Это какое-то убийство веником в лесу. Считайте так: (сколько способов выбрать 3 цифры из 10)*(сколько чисел можно записать конкретными тремя цифрами - вот тут надо повозиться)*9/10.

[TOTAL]

Charlz_Klug в сообщении #902875 писал(а):

А вот как дальше рассуждать - не пойму. Подскажите, пожалуйста, с последующими рассуждениями.

Вариантов из-за появления очередной новой цифры всегда $9 \cdot 9 \cdot 8.$ Это надо умножить на сумму всевозможных различных по составу произведений чисел $1$, $2$ и $3$ (чем меньши сомножители в произведении, тем "позже" появилась новая цифра).

[Kornelij]

topic46837-15.html

-- Вт сен 02, 2014 13:39:22 --

ИСН в сообщении #902881 писал(а):

Считайте так: (сколько способов выбрать 3 цифры из 10)*(сколько чисел можно записать конкретными тремя цифрами - вот тут надо повозиться)*9/10.

По всей видимости множитель 9/10 должен "отбросить" ту часть чисел, у котроых 0 на первом месте. Но разве конкретными тремя цифрами (без 0) можно написть не $3^6$ шестизначных чисел? А если так, то по предложенной формуле получим ответ 78732, который не совпадает с ответом в книге. Или я что-то путаю?

[TOTAL]

Kornelij в сообщении #902903 писал(а):

По всей видимости множитель 9/10 должен "отбросить" ту часть чисел, у котроых 0 на первом месте. Но разве конкретными тремя цифрами (без 0) можно написть не $3^6$ шестизначных чисел? А если так, то по предложенной формуле получим ответ 78732, который не совпадает с ответом в книге. Или я что-то путаю?

Если на 9/10 умножите правильное число, то получите правильный ответ.

[Kornelij]

TOTAL в сообщении #902945 писал(а):

Если на 9/10 умножите правильное число, то получите правильный ответ.

Масло масляное. Вопрос был совсем конкретный, а ответ ниочем.

[Sender]

ИСН в сообщении #902881 писал(а):

сколько чисел можно записать конкретными тремя цифрами - вот тут надо повозиться

Подумаешь, бином Ньютона. Принцип включений-исключений ещё никто не отменял.

[ИСН]

Kornelij в сообщении #902903 писал(а):

Но разве конкретными тремя цифрами (без 0) можно написть не $3^6$ шестизначных чисел?

Что-то типа того, но теперь надо вычесть те, которые используют не все из трёх цифр.

[Kornelij]

ИСН в сообщении #902973 писал(а):

Что-то типа того, но теперь надо вычесть те, которые используют не все из трёх цифр.

Ах ну да... вот я балда

[Charlz_Klug]

TOTAL в сообщении #902887 писал(а):

Вариантов из-за появления очередной новой цифры всегда $9 \cdot 9 \cdot 8.$ Это надо умножить на сумму всевозможных различных по составу произведений чисел $1$, $2$ и $3$ (чем меньши сомножители в произведении, тем "позже" появилась новая цифра).

Спасибо, вы несколько туманно описали, но поспособствовали прояснению решения задачи. Я поискал в интернете и наткнулся на такой пост, автор поста предельно ясно описал рассуждения. Я опишу рассуждение решения своими словами: Возьмём множество цифр в таком порядке: $\{1,2,3,4,5,6,7,8,9,0\}$, в целом канонично было бы использовать $\{0,1,2,3,4,5,6,7,8,9\}$, но, для разбора решения более лучше подходит первый вариант $\{1,2,3,4,5,6,7,8,9,0\}$. Составляем первую комбинацию из первого элемента множества (в данном случае $1$):
$111111$ - не удовлетворяет условию задачи.
$111112$ - не удовлетворяет условию задачи.
$111113$ - не удовлетворяет условию задачи.
...
$111119$ - не удовлетворяет условию задачи.
$111110$ - не удовлетворяет условию задачи.
$111121$ - не удовлетворяет условию задачи.
$111122$ - не удовлетворяет условию задачи.
$111123$ - удовлетворяет условию задачи.
$111124$ - удовлетворяет условию задачи.
$111125$ - удовлетворяет условию задачи.
$111126$ - удовлетворяет условию задачи.
$111127$ - удовлетворяет условию задачи.
$111128$ - удовлетворяет условию задачи.
$111129$ - удовлетворяет условию задачи.
$111120$ - удовлетворяет условию задачи.
$111131$ - не удовлетворяет условию задачи.
$111132$ - удовлетворяет условию задачи.

То есть, в этом варианте изменяются 1-ая позиция, 5-ая позиция и 6-ая позиция, остальные цифры будут той цифрой, которая представляет первую позицию. Следовательно, в данном случае количество комбинаций можно подсчитать так:$9 \cdot 1 \cdot 1 \cdot 1 \cdot 9 \cdot 8 = 648$, расшифровка: 1-ая позиция от 1 до 9 (9 вариантов), 5-ая позиция от 1 до 0 минус один элемент выбранный для первой позиции (9 вариантов) и 6-ая позиция от 1 до 0 минус два элемента, выбранные для первой позиции (8 вариантов). Остальные единицы - это цифра, взятая из первой позиции. Так мы переходим к следующему варианту:
$111100$ - не удовлетворяет условию задачи.
$111211$ - не удовлетворяет условию задачи.
$111212$ - не удовлетворяет условию задачи.
$111213$ - удовлетворяет условию задачи.
...
Теперь уже расклад такой 1-ая позиция выбирается от 1 до 9 (9 вариантов), 2-ая позиция - это цифра из первой позиции (1 вариант), 3-ая позиция - это цифра из первой позиции (1 вариант), 4-ая позиция - выбирается от 1 до 0 минус 1 элемент выбранный для первой позиции (9 вариантов), 5-ая позиция - один из двух элементов выбранных для первой и четвёртой позиции (2 варианта), 6-ая позиция - выбор от 1 до 0 минус два элемента для первой и четвёртой позиции (8 вариантов). Итого: $9 \cdot 1 \cdot 1 \cdot 9 \cdot 2 \cdot 8 = 1296$.

Теперь, переключаемся на позиции 1, 4 и 5: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это цифра из первой позиции (1 вариант), 3-ая позиция - это цифра из первой позиции (1 вариант), 4-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 5-ая позиция - это варианты от 1 до 0 минус два элемента из первой и четвёртой позиции (8 вариантов), 6-ая позиция - это один из трёх цифр которые появились ранее на позициях 1, 4 и 5 (3 варианта). Итого: $9 \cdot 1 \cdot 1 \cdot 9 \cdot 8 \cdot 3 = 1944$.

Теперь, переключаемся на позиции 1, 3 и 6: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это цифра из первой позиции (1 вариант), 3-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 4-ая позиция - это цифры из первой и третьей позиции (2 варианта), 5-ая позиция - это цифры из первой и третьей позиции (2 варианта), 6-ая позиция - это варианты от 1 до 0 минус два элемента из первой и третьей позиции (8 вариантов). Итого: $9 \cdot 1 \cdot 9 \cdot 2 \cdot 2 \cdot 8 = 2592$.

Теперь, переключаемся на позиции 1, 3 и 5: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это цифра из первой позиции (1 вариант), 3-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 4-ая позиция - это цифры из первой и третьей позиции (2 варианта), 5-ая позиция - это варианты от 1 до 0 минус два элемента из первой и третьей позиции (8 вариантов), 6-ая позиция - это цифры из 1-й, 3-й и 5-й позиций (3 цифры). Итого: $9 \cdot 1 \cdot 9 \cdot 2 \cdot 8 \cdot 3 = 3888$.

Теперь, переключаемся на позиции 1, 3 и 4: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это цифра из первой позиции (1 вариант), 3-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 4-ая позиция - это варианты от 1 до 0 минус два элемента из первой и третьей позиции (8 вариантов), 5-ая позиция - это цифры из первой, третьей и четвёртой позиций (3 варианта), 6-ая позиция - это цифры из первой, третьей и четвёртой позиций (3 варианта). Итого: $9 \cdot 1 \cdot 9 \cdot 8 \cdot 3 \cdot 3 = 5832$.

Теперь, переключаемся на позиции 1, 2 и 6: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 3-ая позиция - цифры из первой и второй позиций (2 варианта), 4-ая позиция - цифры из первой и второй позиций (2 варианта), 5-ая позиция - цифры из первой и второй позиций (2 варианта), 6-ая позиция - это варианты от 1 до 0 минус два элемента из первой и второй позиции (8 вариантов). Итого: $9 \cdot 9 \cdot 2 \cdot 2 \cdot 2 \cdot 8 = 5184$.

Теперь, переключаемся на позиции 1, 2 и 5: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 3-ая позиция - цифры из первой и второй позиций (2 варианта), 4-ая позиция - цифры из первой и второй позиций (2 варианта), 5-ая позиция - это варианты от 1 до 0 минус два элемента из первой и второй позиции (8 вариантов), 6-ая позиция - это цифры из первой, второй и пятой позиций (3 варианта). Итого: $9 \cdot 9 \cdot 2 \cdot 2 \cdot 8 \cdot 3 = 7776$.

Теперь, переключаемся на позиции 1, 2 и 4: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 3-ая позиция - цифры из первой и второй позиций (2 варианта), 4-ая позиция - это варианты от 1 до 0 минус два элемента из первой и второй позиции (8 вариантов), 5-ая позиция - это цифры из первой, второй и четвёртой позиций (3 варианта), 6-ая позиция - это цифры из первой, второй и четвёртой позиций (3 варианта). Итого: $9 \cdot 9 \cdot 2 \cdot 8 \cdot 3 \cdot 3 = 11664$.

Теперь, переключаемся на позиции 1, 2 и 3: 1-ая позиция - от 1 до 9 (9 вариантов), 2-ая позиция - это варианты от 1 до 0 минус один элемент из первой позиции (9 вариантов), 3-ая позиция - это варианты от 1 до 0 минус два элемента из первой и второй позиции (8 вариантов), 4-ая позиция - это цифры из первой, второй и третьей позиций (3 варианта), 5-ая позиция - это цифры из первой, второй и третьей позиций (3 варианта), 6-ая позиция - это цифры из первой, второй и третьей позиций (3 варианта). Итого: $9 \cdot 9 \cdot 8 \cdot 3 \cdot 3 \cdot 3 = 17496$.

Теперь суммируем всё вместе: $648 + 1296 + 1944 + 2592 + 3888 + 5832 + 5184 + 7776 + 11664 + 17496 = 58320$. Вот такое решение. Всем спасибо! Я разобрался в задаче. Сегодняшний день прожит не зря.

[Intercooler]

Интересно узнать правильный ответ, у меня получилось 33130, считал в уме, так что скорее всего ошибся :)

-- 02.09.2014, 15:37 --

Извиняюсь, опоздал.

[Kornelij]

Charlz_Klug, попробуйте все-таки сделать проще. Все, что дя этого нужно, уже по сути написано в двух постах ИСН. Перебор, конечно, рулит, но это действительно

ИСН в сообщении #902881 писал(а):

какое-то убийство веником в лесу

[Charlz_Klug]

Kornelij в сообщении #902991 писал(а):

Charlz_Klug, попробуйте все-таки сделать проще.

Помозгую ещё на досуге. Может быть и есть попроще метод.

[Evgenjy]

Можно решить без нудного перебора:

$9\cdot(3^5-2\cdot2^5+1)\cdot C_9^2=58320$

[Charlz_Klug]

Evgenjy в сообщении #903304 писал(а):

Можно решить без нудного перебора:

$9\cdot(3^5-2\cdot2^5+1)\cdot C_9^2=58320$

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