Задачи на перестановки

@Judi · Регистрация: 24.01.2011

Студворк — интернет-сервис помощи студентам

Сколькими способами из колоды в 36 листов можно выбрать не упорядоченный набор из 5 карт так, чтобы в этом наборе было бы точно:1 король, 1 дама, 1 крестовая карта?

Сколько различных слов можно получить перестановкой букв слова ПЕРЕДЕЛ, если в начале и в конце слова стоит согласная буква?

Сколько натуральных чисел от 1до 10000 не делится ни на 2, ни на 5, ни на 4, ни на 17?

Подсчитать количество различных перестановок цифр данного числа 352366, при которых никакие 2 одинаковых цифр не идут друг за другом.

Сколько существует перестановок 8 различных предметов, при которых на своих первоначальных местах окажутся ровно 3 или ровно 4 предметов?

Комментарий модератора

Перечитайте правила форума, п. 3.15.

Байт · 02.12.2011, 17:11

Сообщение от Judi

Сколько натуральных чисел от 1до 10000 не делится ни на 2, ни на 5, ни на 4, ни на 17?

Четверку со спокойной душой можно выкинуть, ведь если не делится на 2, то уж на 4 и подавно.
На 2 делится 5000, на 5 - 2000, на 17 - 588. Хотелось бы сказать, что ответ 10000 - 5000 - 2000 - 588, но это, конечно, не так. Из 2000, которые делятся на 5 половину (те, которые делятся на 10) мы уже посчитали с двойкой. Тоже самое с 17. Выкинем их 5000 + 2000 + 588 - 1000 - 294 - 117. (117 возникло от того, что числа 85*к мы подсчитали с пятеркой) Но теперь числа кратные 170 (а их 58 штук) мы выкинули 2 раза.
Итого 10000 - 5000 - 2000 - 588 + 1000 + 294 +117 - 58 = ...
ЗЫ. Хотя бы нумеруй задачи

Добавлено через 20 минут

Сообщение от Judi

Сколько существует перестановок 8 различных предметов, при которых на своих первоначальных местах окажутся ровно 3 или ровно 4 предметов?

Это 2 задачи.
Пусть ровно 4 предмета неподвижны. Их можно выбрать C(4,8) способами Остальные 4 предмета надо рассувать по 4 местам, так чтоб их положения изменились. Пусть Xk - количество перестановок из k предметов с изменением их положения. X1 = 0 X2 = 1 X3 = 2 X4 = 11 - результат странный, но вот эти перестановки: 2143 2341 2413 3142 3241 3421 3412 4123 4213 4312 4321 - я просто перебирал, может быть чего-то упустил. Получается C(4,8) * 11 = 11 * 8! / 4! 4!
Хм.. Возможно я и не прав...

Не по теме:

ЗЫ. Красота - великая сила

@kazak · 03.12.2011, 11:57

Сообщение от Judi

Сколько существует перестановок 8 различных предметов, при которых на своих первоначальных местах окажутся ровно 3 или ровно 4 предметов?

1)С(8, 3) * 5!
2)С(8, 4) * 4!
Или общая формула С(m, n)*(m-n)!

Добавлено через 3 минуты

Сообщение от Judi

Сколько различных слов можно получить перестановкой букв слова ПЕРЕДЕЛ, если в начале и в конце слова стоит согласная буква?

А(4, 2)*5!/3!

Добавлено через 4 минуты

Сообщение от Judi

Сколькими способами из колоды в 36 листов можно выбрать не упорядоченный набор из 5 карт так, чтобы в этом наборе было бы точно:1 король, 1 дама, 1 крестовая карта?

https://www.cyberforum.ru/disc... ost2151573

Байт · 03.12.2011, 12:01

Сообщение от kazak

1)С(8, 3) * 5!
2)С(8, 4) * 4!
Или общая формула С(m, n)*(m-n)!

Это верно, если остальные предметы переставляются как угодно. Но они должны все сдвинуться!

@kazak · 03.12.2011, 12:24

Байт, мда... мне это в голову как-то не пришло

Добавлено через 6 минут

Сообщение от Байт

11 - результат странный, но вот эти перестановки: 2143 2341 2413 3142 3241 3421 3412 4123 4213 4312 4321

2314 пропущен, всего 12 перестановок.

Добавлено через 4 минуты
туплю...

Добавлено через 2 минуты
3241 и 4213 лишние остается 9 комбинаций.

Day · 03.12.2011, 12:44

А не работает ли здесь рекурентная формула Xn = (n-1)^2 * Xn-2 ? (при n>3)

@kazak · 03.12.2011, 12:54

Day, если я правильно понял формулу, то при n = 5, Xn = 48, но при ручном подсчете у меня получилось 44.

@Judi · 03.12.2011, 14:44 **[ТС]**

Спасибо всем за помощь. Вот как я решила эти задания. Не знаю, правильно или нет. Может покритикуете.
На фотках 1 и 2. 3 решила так же, как Байт.

Сколько существует перестановок 8 различных предметов, при которых на своих первоначальных местах окажутся ровно 3 или ровно 4 предметов?
Думала думала и надумала такое:

1) Представим, что 4 предмета на своем месте. Переставляем остальные 4.
4! - 3!*4+2!*4-1!*4= 4
2) 3 стоят на месте, переставляем остальные 5 аналогично.
получается 44.
Находим общее количество перестановок.
С(8,4)*4 + С (8,3)*44=2744

Подсчитать количество различных перестановок цифр данного числа 352366, при которых никакие 2 одинаковых цифр не идут друг за другом.
сначала общее количество перестановок нашла. 6!/2!2!, тк цифры повторяются. получается 180.
а дальше находила при данном условии количество перестановок.
180 - 5!/2! *2 + 4!/2!*2 - 3! =126

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

Байт · 03.12.2011, 20:36

Judi, Что я вам могу сказать на это? У вас очень хорошая голова. Не только красивая, но и умная. В деталях ваших решений я не разбирался (вечер уже), но сам подход чрезвычайно грамотный. Я хочу сказать, что ваш разум светлее моего. Да, у меня есть некоторый опыт, но вы значительно точнее и интереснее справились. Может быть тут дело в том, что это - не мой экзамен?
Как бы то ни было - удачи вам!

@kazak · 04.12.2011, 05:52

Judi, формула сочетаний не учитывает порядок элементов, поэтому, допустим, варианты п*****л и л*****п будут считаться по формуле сочетаний одной и той же перестановкой. Что неверно, здесь следует применять формулу размещений А(4, 2). Аналогично и для букв внутри, здесь нужно использовать перестановку с повторением
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac {m!}{m_1! \, \cdot \, m_2! \, \cdot \, \dots \, \cdot \, m_n!}$
где m - длина слова, m1, m2... mn - количество элементов m1,m2..., если их больше одного. В нашем случае букв 5 из них три одинаковые - 5!/3!.

Добавлено через 10 минут
Про королей и дам:
С(3, 1)*С(3, 1)*С(7, 1)*С(21, 2) + 2*С(3, 1)*С(21, 3)
По первому слагаемому считаются варианты с некрестовой парой король\дама, по второму - варианты король или дама крестовой масти.

Day · 04.12.2011, 09:03

Сделал программку подсчета подстановок, не оставляющих ни одного элемента на месте

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
long Per(int N)  // Генерация перестановок со смещенными элементами
{ char s[100], t; int i, j, r, k; long L;
 if (N>98) return -1L;
 L = 0;
 for(i=0; i<N; i++) s[i] = '1'+i;
 s[N] = '\0';
 while(1) {
   for(i=N-1; i>=0 && s[i] > s[i+1]; i--) ;
   if (i<0) break; // Уже получили самую старшую перестановку
   for(j=N-1; s[i] > s[j]; j--) ;
   t = s[j];
   s[j] = s[i];
   s[i] = t;
   for(k=i+1, r=N-1; r > k; k++, r--) {
     t = s[r];
     s[r] = s[k];
     s[k] = t;
   }
   for(j=0; j<N; j++)
     if (s[j] == '1' + j) break; // Есть элемент стоящий на своем месте
   if (j==N) L++;
 }
 return L;
}
/*****************/
main(int ac, char *av[])
{ int m, N = 10; long K;
   if (ac>=2) N = atoi(av[1]);
   for(m=2; m<=N; m++) {
     K = Per(m);
     printf("%2d %ld\n", m, K);
   }
}
/*****************/

Вот результат

Code
1
2
3
4
5
6
7
8
9
10
11
 2 1
 3 2
 4 9
 5 44
 6 265
 7 1854
 8 14833
 9 133496
10 1334961
11 14684570
12 176214841

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	03.12.2011, 12:44
	А не работает ли здесь рекурентная формула Xn = (n-1)^2 * Xn-2 ? (при n>3) 1

@kazak 3604 / 2744 / 356 Регистрация: 11.03.2009 Сообщений: 6,306
	03.12.2011, 12:54
	Day, если я правильно понял формулу, то при n = 5, Xn = 48, но при ручном подсчете у меня получилось 44. 2

@Judi 1 / 1 / 0 Регистрация: 24.01.2011 Сообщений: 16
	03.12.2011, 14:44 [ТС]
	Спасибо всем за помощь. Вот как я решила эти задания. Не знаю, правильно или нет. Может покритикуете. На фотках 1 и 2. 3 решила так же, как Байт. Сколько существует перестановок 8 различных предметов, при которых на своих первоначальных местах окажутся ровно 3 или ровно 4 предметов? Думала думала и надумала такое: 1) Представим, что 4 предмета на своем месте. Переставляем остальные 4. 4! - 3!4+2!4-1!4= 4 2) 3 стоят на месте, переставляем остальные 5 аналогично. получается 44. Находим общее количество перестановок. С(8,4)4 + С (8,3)44=2744 Подсчитать количество различных перестановок цифр данного числа 352366, при которых никакие 2 одинаковых цифр не идут друг за другом. сначала общее количество перестановок нашла. 6!/2!2!, тк цифры повторяются. получается 180. а дальше находила при данном условии количество перестановок. 180 - 5!/2! 2 + 4!/2!*2 - 3! =126 Но я что-то запуталась и не до конца все поняла... Последний,я думаю, не верно решила Миниатюры 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	03.12.2011, 20:36
	Judi, Что я вам могу сказать на это? У вас очень хорошая голова. Не только красивая, но и умная. В деталях ваших решений я не разбирался (вечер уже), но сам подход чрезвычайно грамотный. Я хочу сказать, что ваш разум светлее моего. Да, у меня есть некоторый опыт, но вы значительно точнее и интереснее справились. Может быть тут дело в том, что это - не мой экзамен? Как бы то ни было - удачи вам! 1

@kazak 3604 / 2744 / 356 Регистрация: 11.03.2009 Сообщений: 6,306
	04.12.2011, 05:52
	Judi, формула сочетаний не учитывает порядок элементов, поэтому, допустим, варианты п***л и л**п будут считаться по формуле сочетаний одной и той же перестановкой. Что неверно, здесь следует применять формулу размещений А(4, 2). Аналогично и для букв внутри, здесь нужно использовать перестановку с повторением $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac {m!}{m_1! \, \cdot \, m_2! \, \cdot \, \dots \, \cdot \, m_n!}$ где m - длина слова, m1, m2... mn - количество элементов m1,m2..., если их больше одного. В нашем случае букв 5 из них три одинаковые - 5!/3!. Добавлено через 10 минут* Про королей и дам: С(3, 1)С(3, 1)С(7, 1)С(21, 2) + 2С(3, 1)*С(21, 3) По первому слагаемому считаются варианты с некрестовой парой король\дама, по второму - варианты король или дама крестовой масти. 0

Задачи на перестановки

Решение