Задача о произведении чисел [Комбинаторика]

[Whitaker]

Здравствуйте друзья!
Помогите разобраться с такой комбинаторной задачей.
Из натуральных чисел от $1$ до $n$ включительно составлены всевозможные произведения содержащие $k$ различных сомножителей ($k$ фиксировано). Сколько из этих произведения делится на просто число p, такое, что $p\leq n$?
Меня не совсем интересует ход решения задачи, а больше ее формулировка.
Например если $k=3$, то возьмём три числа $3,4$ и $6$. Их произведение равно $72$.
Но результат произведения еще можно написать так: $8 \cdot 9 \cdot 1$, $2 \cdot 4 \cdot 9$. Получается что одно и тоже число может входить более одно раза. Или в задаче имеет только "произведение", а не "результат произведения"?

С уважением, Whitaker.

[Хорхе]

Я думаю, что имеется в виду не результат, а именно произведение, иначе задача очень сложная.

[Whitaker]

Думаю, что Вы правы.
В таком ответ случае ответ будет такой $C_{n-1}^{2}$.
Я прав?

[AKM]

Whitaker в сообщении #490225 писал(а):

В таком ответ случае ответ будет такой $С_{n-1}^{2}$.

Почувствуйте разницу между С^2_{n-1} = $С?^2_{n-1}$, и C^2_{n-1} = $C^2_{n-1}$. Оставляю подробности в качестве дополнительной комбинаторной задачки.
Также советую пользовать кнопку "Предпросмотр"

[Whitaker]

Извините пожалуйста
Случайно вышло щас исправлю

[AKM]

Whitaker в сообщении #490225 писал(а):

В таком ответ случае ответ будет...

AKM в сообщении #490233 писал(а):

Также советую пользовать кнопку "Предпросмотр"

(см. сабж)

[Хорхе]

Увы, ответ неправильный (и вообще не понимаю, как Вы его получили). Намного легче посчитать количество тех произведений, которые не делятся и отнять от общего.

[Whitaker]

Ааа да у меня ошибка. Спасибо за то, что исправили

-- Чт окт 06, 2011 23:03:14 --

Всего произведений $C_{n}^{k}$, а произведений которые не делятся на число p(т.е. не содержат его) всего $C_{n-1}^{k}$.
Получаем, что $C_{n}^{k}-C_{n-1}^{k}=C_{n-1}^{k-1}$
Вроде всё правильно.

[Хорхе]

Все равно неправильно, хоть и гораздо ближе.

[VAL]

Whitaker в сообщении #490246 писал(а):

Всего произведений $C_{n}^{k}$, а произведений которые не делятся на число p(т.е. не содержат его) всего $C_{n-1}^{k}$.
Получаем, что $C_{n}^{k}-C_{n-1}^{k}=C_{n-1}^{k-1}$
Вроде всё правильно.

Подсказка: Ваш ответ будет верен, когда $p$ больше половины $n$.

[Whitaker]

VAL в сообщении #490288 писал(а):

Whitaker в сообщении #490246 писал(а):

Всего произведений $C_{n}^{k}$, а произведений которые не делятся на число p(т.е. не содержат его) всего $C_{n-1}^{k}$.
Получаем, что $C_{n}^{k}-C_{n-1}^{k}=C_{n-1}^{k-1}$
Вроде всё правильно.

Подсказка: Ваш ответ будет верен, когда $p$ больше половины $n$.

А почему должно быть $p>\dfrac{n}{2}$?

-- Пт окт 07, 2011 08:42:51 --

P.S. Я на простых примерах проверяд вроде мой ответ правильный.
А где ошибка-то?

[VAL]

Whitaker в сообщении #490291 писал(а):

VAL в сообщении #490288 писал(а):

Whitaker в сообщении #490246 писал(а):

Всего произведений $C_{n}^{k}$, а произведений которые не делятся на число p(т.е. не содержат его) всего $C_{n-1}^{k}$.
Получаем, что $C_{n}^{k}-C_{n-1}^{k}=C_{n-1}^{k-1}$
Вроде всё правильно.

Подсказка: Ваш ответ будет верен, когда $p$ больше половины $n$.

А почему должно быть $p>\dfrac{n}{2}$?

Я не утверждал, что так должно быть. Я утверждал, что Ваш ответ верен лишь для этого случая.

[Whitaker]

Ну в книге ответ немного другой, т.е. $C_{n-2}^{k-1}$.
Как получить такой ответ я не совсем понимаю

[Хорхе]

Ответ в книге тоже неправильный. Еще подсказка: может быть больше одного числа меньше $n$, кратного $p$.

[Whitaker]

Вы правы уважаемые! Например если мы возьмём множество $\{1, 2, 3, 4, 5, 6\}$ и хотим найти произведения состоящие из $3$ различных сомножителей делящиеся на простое число $3$?
Тогда мой ответ неправилен, а правильный ответ к задаче $14$
Ведь есть произведение $1 \cdot 2 \cdot 6$ среди сомножителей которого нет $3$, но она всё равно делится на $3$.
Нужно рассматривать числа делящиеся еще на $kp$