Задача по комбинаторике

Понимаю, что задача не из сложных, но что-то никак не могу въехать как к ней подступиться

Сколько шестизначных чисел содержат ровно три различные цифры?
Я так понял это числа типа 554422, 123122 и т.д.
У меня получается их количество 9*9*8*3*3*3, но их больше.

И в общем случае сколько n значных чисел содержат ровно k различных цифр.

 

Пошел нафик со школьными вопросами(в 5 класс там такое проходят или в 7)!

 

ну задача фактически сводится к вычислению количества способов разложить n на k слагаемых.

 

Asvald
10*9*8 - количество трехзначных чисел с различными цифрами

сколько способов удвоить тройку чисел ??? -
первую цифру можно расставить 2 раза 6*5 способами
вторую 4*3
третью 2*1

итак ответ

10*9*8*6*5*4*3*2*1=10!/7

 

Rockphorr
10!/7=518400, что-то многовато по-моему.

 

KeSqueer
ваш вариант решения ???

 

Rockphorr
а почему именно удваиваются цифры??? туда не попадает вариант "111123", к примеру...

Ox8BFF55
очень бы хотелось посмотреть на любого 7-миклассника, решившего эту задачу...

 

Rockphorr

а на 2 каждый случай разве не нужно разделить?

 

Rockphorr
Мой вариант решения

Код (Text):

1. int is_valid(unsigned val)
2. {
3.     int digits[10] = {0};
4.     unsigned sum = 0;
5.     unsigned i;
6.     for (i = 0; i < 6; ++i)
7.     {
8.         digits[val%10] = 1;
9.         val = val/10;
10.     }
11.     for (i = 0; i < 10; ++i)
12.     {
13.         sum += digits[i];
14.     }
15.     return sum == 3;
16. }
17.  
18. int main(void)
19. {
20.     unsigned count = 0;
21.     unsigned i;
22.     for (i = 100000; i <= 999999; ++i)
23.     {
24.         if (is_valid(i)) count++;
25.     }
26.     printf("%u\n", count);
27. }

дает 58320.

 

да, и еще, к условию задачи:
число 001122 является шестизначным? его нужно считать?

 

Блин, нашелся, все же гений, решающий комбинаторные задачи полным перебором!

 

Все решил, ответ получается перебором возможных вариантов появления в числе новой цифры начиная с первой(старший разряд), которая может быть любой цифрой из 9, кроме 0, т.к. ноль не может быть первой цифрой в числе.
Например если нам уже известна 1-я цифра, то 2-я если она не "новая" может быть только равна 1-ой и так далее до встречи следующей "новой" цифры, после которой мы можем выбирать уже из двух вариантов и так до 3-ей "новой" цифры, после которой есть уже три варианта. Тогда у нас получаются следующие комбинации:
9*1*1*1*9*8
9*1*1*9*2*8
9*1*1*9*8*3
9*1*9*2*2*8
9*1*9*2*8*3
9*1*9*8*3*3
9*9*2*2*2*8
9*9*2*2*8*3
9*9*2*8*3*3
9*9*8*3*3*3

Сумма всех комбинаций дает число 58320, которое мы уже проверили, т.к. сказать заранее.

 

Asvald
Как на счет универсальной формулы?

 

Чуть посложнее. Сначала надо определится с нулем - число 000111222 разрешаем или нет.
Потом определить сколько бывает разных наборов из трех цифр. Это действительно школьная задача, хотя в наше время такое только на факультавтивах решали(давно это было).
Так как ноль надо учитывать, то тут все просто = 10*9*8
Теперь надо посчитать число паттернов, куда будем наши тройки бросать : aabbacbaa
Будет что-то типа три факториала вверху и два внизу. Получим ответ или если с нулями низзя, то придется подсчитать число "запрещенных".

 

valterg

если я нигде не ошибся, этих паттернов 90

 

Ну да. Тогда моя формула(без нулей в начале) меняется = 9(без нуля в начале)*9*8
И паттернов действительно 90 - тут нули роли не играют. И кстати легко посчитать "неверные" числа =
90*10*9*8

 

кстати, чисел без нуля вначале ровно 90% от всех чисел

 

Осталось только написать обоснованную формулу с факториалами для общего случая. Пока это было решение программистов

 

Почитайте про числа Стирлинга второго рода - это и есть число паттернов из #14. Ну а общая формула в терминах этих чисел тут уже фактически приводилась - S(n,k)*10!/(10-k)!, если разрешаются нули в начале числа, или S(n,k)*9*9!/(10-k)!, если нет.