комбинаторика

[jtrefd]

Я тоже сначала простым тождеством не воспользовался! 

[Katia]

Ребят,вы просто нереальные гении!!!! Пифагор по сравнению с вами нервно курит в уголке!!! Спасибо вам огромное!!!

[Fylhtq1997]

Для организации математического вечера учащиеся Х класса должны избрать оргкомитет в составе председателя, секретаря и двух членов оргкомитета. Сколькими способами можно избрать оргкомитет, если в классе 30 учащихся?
РЕШЕНИЕ:
С₃₀⁴*4*3?

[jtrefd]

Для организации математического вечера учащиеся Х класса должны избрать оргкомитет в составе председателя, секретаря и двух членов оргкомитета. Сколькими способами можно избрать оргкомитет, если в классе 30 учащихся?
РЕШЕНИЕ:
С₃₀⁴*4*3?

или

[devnull]

Капитан очевидность замечает, что все три ответа равны

[Fylhtq1997]

Капитан очевидность замечает, что все три ответа равны

Спасибо. Да! 

[Fylhtq1997]

Задача: Сколько различных пятизначных чисел ,больших 20000, можно составить из цифр 1,2,3,4
если каждая цифра может повторяться не более 2х раз?

Мои рассуждения: мы можем составить 5-значное число из 4 различных цифр двумя способами:

1 цифра (любая) встречается дважды, а остальные 3 – по одному разу;
2 цифры (любых) встречаются дважды, а 1 из двух оставшихся – один раз

теперь надо учесть условие > 20000, для этого нужно подсчитать, сколько найденных 5-значных чисел имеющих   единицу в старшем разряде... т.е.  сколько различных 4-значных чисел можно составить из цифр 1, 2, 3, 4, если цифры 2, 3, 4 могут встречаться не более двух раз, а цифра 1 – не более одного раза..
вычтем из первого результата второй.
Но как эти рассуждения воплотить через формулы не предвижу!

[devnull]

Например:

1 цифра (любая) встречается дважды, а остальные 3 – по одному разу;

Выбираем цифру, которая будет повторяться дважды. Это можно сделать четырьмя различными способами. Выбираем два места, которые мы заполним этой цифрой, это можно сделать C²₅ способами. Оставшиеся три места заполняем оставшимися тремя цифрами, т.е. это просто число перестановок из трех цифр P₃. Итого, 4*C²₅*P₃ = 4*(5!/2!3!)*3! = 240.

[Fylhtq1997]

Например:

1 цифра (любая) встречается дважды, а остальные 3 – по одному разу;

Выбираем цифру, которая будет повторяться дважды. Это можно сделать четырьмя различными способами. Выбираем два места, которые мы заполним этой цифрой, это можно сделать C²₅ способами. Оставшиеся три места заполняем оставшимися тремя цифрами, т.е. это просто число перестановок из трех цифр P₃. Итого, 4*C²₅*P₃ = 4*(5!/2!3!)*3! = 240.

Спасибо. Но ведь на первое место по условию нельзя поставить цыфру "1" или 4-а как раз это место исключает, да?
Перестановка  P₃ исключает например такой вариант, число 22114 или 21214
И ещё каждая цифра может повторяться (0, 1, 2) раза 

[devnull]

Я привел пример вычисления только для указанного вами случая "1 цифра (любая) встречается дважды, а остальные 3 – по одному разу". Разумеется, среди этих вариантов будут и недопустимые, как 11234. В своем первом посте вы сами указали метод, я лишь привел пример как вычислять каждую из требуемых величин.

[Fylhtq1997]

Я привел пример вычисления только для указанного вами случая "1 цифра (любая) встречается дважды, а остальные 3 – по одному разу". Разумеется, среди этих вариантов будут и недопустимые, как 11234. В своем первом посте вы сами указали метод, я лишь привел пример как вычислять каждую из требуемых величин.

1)С первым слагаемым, которое Вы мне сформулировали, я разобрался (классно разъяснили). Его, правда? можно представить и в таком виде C14*(5!/2!) = 240
4*C25*P3 = C14*(5!/2!) = 240
2) Второе слагаемое я сообразил только так:
C24* C12*(5!/2! 2!) = 360
Через размещения с повторениями.
А как можно представить второе слагаемое по Вашему методу (логике)?
Таким образом мы получаем сколько таких пятизначных чисел больше 10000.
4*C25*P3 + C24* C12*(5!/2! 2!)=240+360=600
3) Ещё надо исключить числа от 10000 до 19999.
Это ещё труднее сообразить!!!
Спасибо.
 

[ira-sm]

Можно попробовать следующий прием
Если каждая цифра может быть использована не более 2-х раз, то представим ее в виде двух цифр-близнецов, например, цифра 1 "раздвоится" на 1₁ и 1₂
В итоге наш набор цифр для построения числа будет содержать уже восемь элементов, каждый из которых может быть использован только один раз. С₈⁵
К сожалению, не знаю, как "отфильтровать" получившиеся повторы. А было бы красиво.



Есть еще другой подход, менее красивый, на мой взгляд.
Предлагаю рассмотреть все цифры числа, кроме первой (это из-за ограничения >20000). Получаем четырехзначное число.
1) если цифры этого числа не повторяются, то
    количество вариантов четырехзначного числа равно количеству перестановок четырех цифр = 4!
    способов выбрать первую цифру для пятизначного числа только 3 (любая, кроме 1)
    ИТОГО количество различных пятизначных чисел 3*4!=72
2) если цифры этого (четырехзначного числа) имеют одно повторение
    2.1 выбираем повторяющуюся цифру (4 способа)
    2.2 из оставшихся трех составляем трехзначное число с неповтор. цифрами  -  3! способов
    2.3 выбираем разряд, куда разместим цифру из п. 2.1  (4 способа). Итого получили 4*3! вариантов четырехзначных чисел.
Способов выбрать первую цифру для пятизначного числа в этом случае:
- если в п. 2.1 была выбрана цифра 1  -  3 способа (любая из оставшихся)
- если любая из оставшихся 3-х    -  2 способа (кроме 1) - 2*3=6 способов
ИТОГО количество различных пятизначных чисел (4*3!)*3+(4*3!)*2*3=9*4*3!=216
3) если цифры этого числа (четырехзначного) имеют два повторения
  3.1 Для начала "отложим в сторону" цифру, которую в пятизначном числе поставим на первое место - 3 способа
   3.2 из оставшихся 3-х выберем 2 цифры, которые у нас будут повторяться в четырехзначном числе:  С₃² способов
   3.3 различных вариантов четырехзначных чисел из двух пар повторяющихся цифр - 4!/4=3! способов (берем первую пару цифр. Определяем разряды четырехзначного числа, куда мы разместим эти цифры. Это С₄²=6, вторую пару просто разместим на оставшиеся разряды.)
ИТОГО количество пятизначных чисел в этом случае 3*С₃²*3!=54

Суммируем 1) и 2) и 3)
72+216+54=342 пятизачных числа.

[Fylhtq1997]

Можно попробовать следующий прием
Если каждая цифра может быть использована не более 2-х раз, то представим ее в виде двух цифр-близнецов, например, цифра 1 "раздвоится" на 1₁ и 1₂
В итоге наш набор цифр для построения числа будет содержать уже восемь элементов, каждый из которых может быть использован только один раз. С₈⁵
К сожалению, не знаю, как "отфильтровать" получившиеся повторы. А было бы красиво.

Такие мысли у меня были изначально, но не выруливаю до завершения:

Размещения с повторениями но с прибамбасами
я думаю так
Это размещение из 8 (4*2) по 5 и деленное на колво повторений каждого елемента (2*2*2*2 = 16)
А(5;8) = 8!/(8-5)! /16= 8*7*6*5*4/4/4=2*7*6*5=420 или
перестановки с повторениями Р(8,5)=8!/16=420
 
а теперь самое сложное, отнять кол-во вариантов где первой бы стояла единичка
От здесь у меня и стопор!!!!!
Спасибо
P.S Надежда на devnull

[devnull]

2 цифры (любых) встречаются дважды, а 1 из двух оставшихся – один раз

Выбираем пару цифр, которые будут встречаться дважды. Всего цифр у нас 4, поэтому пару можно выбрать C²₄ способами. Берем меньшую цифру из этой пары и помещаем ее на произвольные два места пятизначного числа, это можно сделать C²₅ способами. У нас остается три незаполненных места. Выбираем из них два и помещаем на них бOльшую цифру из нашей пары, это можно сделать C²₃ способами. Остается последнее незаполненное место, на него можно поместить любую из двух невыбранных ранее цифр, поэтому полное число вариантов в этом случае равно
C²₄*C²₅*C²₃*2 = 360.
Итого, всего существует 240+360 = 600 пятизначных чисел, которые можно составить из цифр 1,2,3,4 так, что каждая цифра может повторяться не более 2х раз. Осталось исключить из этого числа вариантов такие, которые меньше или равны 20000. Пятизначное число, составленное из цифр 1,2,3 и 4 будет меньше 20000 тогда и только тогда, когда оно начинается на 1. Здесь можно последовать вашему методу решения и найти

сколько различных 4-значных чисел можно составить из цифр 1, 2, 3, 4, если цифры 2, 3, 4 могут встречаться не более двух раз, а цифра 1 – не более одного раза..

Однако есть метод проще. Заметим, что все цифры входят в условие совершенно симметрично. Т.е. число пятизначных чисел, начинающихся на 1, равно числу пятизначных чисел, начинающихся на любую другую из этих цифр, и, тем самым, равно одной четвертой их полного числа, т.е. 600/4 = 150. Поэтому количество чисел, больших 20000, будет равно 600 - 150 = 450.
Этот результат несложно проверить и на компьютере:

$ cat numbers.pl
#!/usr/bin/perl
for(11111..44444) {
        $one = y/1//;
        $two = y/2//;
        $three = y/3//;
        $four = y/4//;
        next if $one + $two + $three + $four != 5;
        next if ($one > 2) || ($two > 2) || ($three > 2) || ($four > 2);
        $c1++;
        $c2++ if $_ > 20000;
}
print "Total: $c1\nLarger than 20000: $c2\n";

$ perl numbers.pl
Total: 600
Larger than 20000: 450

[ira-sm]

Однако есть метод проще. Заметим, что все цифры входят в условие совершенно симметрично. Т.е. число пятизначных чисел, начинающихся на 1, равно числу пятизначных чисел, начинающихся на любую другую из этих цифр, и, тем самым, равно одной четвертой их полного числа, т.е. 600/4 = 150. Поэтому количество чисел, больших 20000, будет равно 600 - 150 = 450.

Красиво.