Число из цифер без повторений

@joffstick · Регистрация: 21.04.2010

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

Здравствуйте! Как можно определить количество вариантов (V) N-значных чисел, в которых каждая цифра встречается меньше чем R раз. Количество вариантов также зависит от системы исчисления (D).

Пример

В 2-значных числах (N = 2), при R = 2 и D = 10, V = 90.
Не подходят числа: 00, 11, 22, 33, 44, 55, 66, 77, 88, 99.
Подходят: все остальные

В 2-значных числах (N = 2), при R = 2 и D = 16, V = 240
Не подходят числа: 00, 11, 22, 33, 44, 55, 66, 77, 88, 99, aa, bb, cc, dd, ee, ff
Подходят: все остальные

В 3-значных числах (N = 3) при R = 3 и D = 10, V = 990
Не подходят числа: 000, 111, 222, 333, 444, 555, 666, 777, 888, 999.

Отсюда выходит V = (D^N) - D
Но это только при N = R, а как посчитать для остальных?

Например:
В 3-значных числах (N = 3) при R = 2 и D = 10, V = ?
Не подходят: 000, 001 ... 010, 011, 020, 022, 030, 033 и т.д.
Подходят: 012, 013, 014, 015, 016, 018, 019, 021 и т.д.

valeriikozlov · 28.06.2011, 21:27

joffstick, Вряд ли существует какая-то определенная формула для этой задачи. Но вот алгоритм решения этой задачи придумать можно (применяя ДП и комбинаторику).

@joffstick · 28.06.2011, 23:00 **[ТС]**

Я могу ошибаться, но для 8-значного числа 16-ричной системы исчисления должно быть что-то вроде и числом повторений не более 2 символа:

16 x 16 x 15 x 15 x 14 x 14 x 13 x 13

не более 1 символа:

16 x 15 x 14 x 13 x 12 x 11 x 10 x 9

не более 4 символов:

16 x 16 x 16 x 16 x 15 x 15 x 15 x 15

Это я предположил исходя их того, что кол-во всех вариантов:

16^8 = 16 x 16 x 16 x 16 x 16 x 16 x 16 x 16

Здесь мы для каждой цифры предполагаем все варианты. Если же у нас есть ограничения по кол-ву повторений, то по достижении этого предела мы должны уменьшыть кол-во вариантов на 1 символ. Вроде так...
Подскажите мне кто-нибудь если я ошибаюсь.

Осталось привести это всё к общему виду.

valeriikozlov · 29.06.2011, 06:27

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

Я могу ошибаться

В данном случае Вы ошибаетесь.
Например: В 5-значных числах (N = 5), при R = 2 и D = 10, правильный ответ V = 91953
А судя по Вашим предположениям V = 10*10*9*9*8

@Mysterious Light · 29.06.2011, 07:00

Рассуждения вслух:

Пусть "сигнатура" — это D-мерный кортеж, выражающий число вхождений каждой цифры в число.
Сигнатуре (a0,a1,a2,...,aD-1) соотв. $https://www.cyberforum.ru/cgi-bin/latex.cgi?C^{(a_0,a_1,\dots,a_{D-1})}_n = \frac { n! } { a_0! \times a_1! \times \dots \times a_{D-1}! }$ , если я правильно помню, где n=a0+a1+...+aD-1

Теперь определимся, какие тебе нужны сигнатуры:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?1)\;\;\forall i:\; a_i \le R \; \leftrightarrow \; \vec a \in [0..R]^{\tiny{D}} \\ 2)\;\;\sum_{i=0}^{{\tiny{D}}-1}a_i=N$

Множество всех таких кортежей a можно найти из системы. Для каждого можно определить число вариантов, осталось их просуммировать.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?V = \sum_{\vec a \in \mathscr P(n)} C^{\vec a}_n, \;\; {\mathscr P}(n) = \{ \begin{matrix} { \vec a \in [0..R]^{\tiny{D}} \\ \sum_{i=0}^{{\tiny{D}}-1}a_i=n } \end{matrix}$

Сумму можно перегруппировать, чтоб суммировать только по упорядоченным цепочкам, тогда вылезет коэффициент в сумме.

valeriikozlov, поясните ответ в Вашем примере.
Мне кажется, если R=2, то число должно быть составлено только из уникальных цифр, поэтому число вариантов 10 (первая позиция) * 9 (вторая позиция) * 8 * 7 * 6 = 30240

valeriikozlov · 29.06.2011, 07:13

Mysterious Light, Особо пояснять не буду. Есть такая задача: http://acmp.ru/index.asp?main=task&id_task=403
Я ее раньше сдавал. А сейчас взял и подставил в нее данные из своего примера и получил ответ.

@Mysterious Light · 29.06.2011, 07:20

Зря Вы так грубо, я действительно слабо понимаю, как у Вас получился такой ответ.
Кстати, в задаче R=3, но я по-прежнему не понимаю, как количество вариантов может быть нечетным.

valeriikozlov · 29.06.2011, 07:44

Ксати, только сейчас заметил. Мой пример не подходит для этой задачи (там задаче засчитываются такие числа для моего примера, как 1, 2 .. и тд. А по этому условию, эти числа выглядят как 00001, 00002 и не подходят под условие).
Ладно давайте вручную пересчитаем мой пример:
Просчитаем кол-во вариантов когда 3 цифры совпадают, потом когда совпадают 4 цифры, потом когда 5.
Итак совпадение 3 цифр:
XXX.. <- здесь X это например цифра 0, '.' это любая другая цифра (но не 0). На оставшихся двух местах можно размещать цифры от 1 до 9. Итого для варианта XXX.. (где X равен 0, а '.' любая другая) получается 89 вариантов.
Т.к. X может быть и другими цифрами от 1 до 9, то кол-во вариантов XXX.. (где X не равно '.') 89*10=890.
Всего кол-во вариантов, где только три цифры одинаковые:
XXX..
XX.X.
XX..X
и тд
..XXX
Всего 10.
Итого всего вариантов когда только 3 цифры совпадает - 890*10=8900.

Теперь вариант когда совпадает 4 цифры:
XXXX. По тому же алгоритму 9*10*5=450

Теперь вариант когда совпадает 5 цифр:
XXXXX По тому же алгоритму 10

Итого кол-во вариантов когда совпадает 3, 4 и 5 цифр : 8900+450+10=9360
Всего вариантов 100000 (пятизначных чисел), тогда V = 100000-9360=90640
А это значит что формула в 3-ем посте все равно не правильная.

я не хотел грубить. Если чем-то обидел, извиняйте.

@Mysterious Light · 29.06.2011, 09:44

Ваши рассуждения выглядят правдоподобно, но вот только всё равно я сомниваюсь в ответе

Есть альтернативный ход рассуждения (прямой)
1. Все цифры уникальны => 10*9*8*7*6
2. Есть одна пара, остальные различны => 10*9*8*7
Пара может принимать одну из 15 позиций среди других цифр
3. Две пары => 10(первая)*9(вторая)*8(свободная)
Пусть первая та, у которой левая цифра (из двух) левее. Тогда можно позиционировать 15 способами:
1122.
112.2
11.22
1212.
121.2
1.122
1221.
12.12
1.212
122.1
12.21
1.221
.1122
.1212
.1221

Итого:
10*9*8*7*6
10x 10*9*8*7
15x 10*9*8
------------
91440

P.S. по-быстрому написал программу, которая влоб перебирает все варианты, но усомнился в её работоспособности: http://codepad.org/rIeQSpXy

valeriikozlov · 29.06.2011, 10:44

Mysterious Light, Да нет правильный ответ у Вас выдает. Я тоже проверил перебором в лоб своим кодом.

@joffstick · 29.06.2011, 12:05 **[ТС]**

Сообщение от Mysterious Light

P.S. по-быстрому написал программу, которая влоб перебирает все варианты, но усомнился в её работоспособности: http://codepad.org/rIeQSpXy

Не знаю что это за язык, но я его не понимаю...

Сейчас попытаюсь переварить всю эту информацию...

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@joffstick 15 / 15 / 5 Регистрация: 21.04.2010 Сообщений: 85

	Число из цифер без повторений 28.06.2011, 14:37. Показов 2110. Ответов 10 Метки нет (Все метки) Здравствуйте! Как можно определить количество вариантов (V) N-значных чисел, в которых каждая цифра встречается меньше чем R раз. Количество вариантов также зависит от системы исчисления (D). Пример В 2-значных числах (N = 2), при R = 2 и D = 10, V = 90. Не подходят числа: 00, 11, 22, 33, 44, 55, 66, 77, 88, 99. Подходят: все остальные В 2-значных числах (N = 2), при R = 2 и D = 16, V = 240 Не подходят числа: 00, 11, 22, 33, 44, 55, 66, 77, 88, 99, aa, bb, cc, dd, ee, ff Подходят: все остальные В 3-значных числах (N = 3) при R = 3 и D = 10, V = 990 Не подходят числа: 000, 111, 222, 333, 444, 555, 666, 777, 888, 999. Отсюда выходит V = (D^N) - D Но это только при N = R, а как посчитать для остальных? Например: В 3-значных числах (N = 3) при R = 2 и D = 10, V = ? Не подходят: 000, 001 ... 010, 011, 020, 022, 030, 033 и т.д. Подходят: 012, 013, 014, 015, 016, 018, 019, 021 и т.д. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	28.06.2011, 21:27
	joffstick, Вряд ли существует какая-то определенная формула для этой задачи. Но вот алгоритм решения этой задачи придумать можно (применяя ДП и комбинаторику). 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	29.06.2011, 07:00
	Рассуждения вслух: Пусть "сигнатура" — это D-мерный кортеж, выражающий число вхождений каждой цифры в число. Сигнатуре (a0,a1,a2,...,aD-1) соотв. $https://www.cyberforum.ru/cgi-bin/latex.cgi?C^{(a_0,a_1,\dots,a_{D-1})}_n = \frac { n! } { a_0! \times a_1! \times \dots \times a_{D-1}! }$ , если я правильно помню, где n=a0+a1+...+aD-1 Теперь определимся, какие тебе нужны сигнатуры: $https://www.cyberforum.ru/cgi-bin/latex.cgi?1)\;\;\forall i:\; a_i \le R \; \leftrightarrow \; \vec a \in [0..R]^{\tiny{D}} \\ 2)\;\;\sum_{i=0}^{{\tiny{D}}-1}a_i=N$ Множество всех таких кортежей a можно найти из системы. Для каждого можно определить число вариантов, осталось их просуммировать. $https://www.cyberforum.ru/cgi-bin/latex.cgi?V = \sum_{\vec a \in \mathscr P(n)} C^{\vec a}_n, \;\; {\mathscr P}(n) = \{ \begin{matrix} { \vec a \in [0..R]^{\tiny{D}} \\ \sum_{i=0}^{{\tiny{D}}-1}a_i=n } \end{matrix}$ Сумму можно перегруппировать, чтоб суммировать только по упорядоченным цепочкам, тогда вылезет коэффициент в сумме. valeriikozlov, поясните ответ в Вашем примере. Мне кажется, если R=2, то число должно быть составлено только из уникальных цифр, поэтому число вариантов 10 (первая позиция) * 9 (вторая позиция) * 8 * 7 * 6 = 30240 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	29.06.2011, 07:13
	Mysterious Light, Особо пояснять не буду. Есть такая задача: http://acmp.ru/index.asp?main=task&id_task=403 Я ее раньше сдавал. А сейчас взял и подставил в нее данные из своего примера и получил ответ. 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	29.06.2011, 07:20
	Зря Вы так грубо, я действительно слабо понимаю, как у Вас получился такой ответ. Кстати, в задаче R=3, но я по-прежнему не понимаю, как количество вариантов может быть нечетным. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	29.06.2011, 07:44
	Ксати, только сейчас заметил. Мой пример не подходит для этой задачи (там задаче засчитываются такие числа для моего примера, как 1, 2 .. и тд. А по этому условию, эти числа выглядят как 00001, 00002 и не подходят под условие). Ладно давайте вручную пересчитаем мой пример: Просчитаем кол-во вариантов когда 3 цифры совпадают, потом когда совпадают 4 цифры, потом когда 5. Итак совпадение 3 цифр: XXX.. <- здесь X это например цифра 0, '.' это любая другая цифра (но не 0). На оставшихся двух местах можно размещать цифры от 1 до 9. Итого для варианта XXX.. (где X равен 0, а '.' любая другая) получается 89 вариантов. Т.к. X может быть и другими цифрами от 1 до 9, то кол-во вариантов XXX.. (где X не равно '.') 8910=890. Всего кол-во вариантов, где только три цифры одинаковые: XXX.. XX.X. XX..X и тд ..XXX Всего 10. Итого всего вариантов когда только 3 цифры совпадает - 89010=8900. Теперь вариант когда совпадает 4 цифры: XXXX. По тому же алгоритму 9105=450 Теперь вариант когда совпадает 5 цифр: XXXXX По тому же алгоритму 10 Итого кол-во вариантов когда совпадает 3, 4 и 5 цифр : 8900+450+10=9360 Всего вариантов 100000 (пятизначных чисел), тогда V = 100000-9360=90640 А это значит что формула в 3-ем посте все равно не правильная. я не хотел грубить. Если чем-то обидел, извиняйте. 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	29.06.2011, 09:44
	Ваши рассуждения выглядят правдоподобно, но вот только всё равно я сомниваюсь в ответе Есть альтернативный ход рассуждения (прямой) 1. Все цифры уникальны => 109876 2. Есть одна пара, остальные различны => 10987 Пара может принимать одну из 15 позиций среди других цифр 3. Две пары => 10(первая)9(вторая)8(свободная) Пусть первая та, у которой левая цифра (из двух) левее. Тогда можно позиционировать 15 способами: 1122. 112.2 11.22 1212. 121.2 1.122 1221. 12.12 1.212 122.1 12.21 1.221 .1122 .1212 .1221 Итого: 109876 10x 10987 15x 1098 ------------ 91440 P.S. по-быстрому написал программу, которая влоб перебирает все варианты, но усомнился в её работоспособности: http://codepad.org/rIeQSpXy 1

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	29.06.2011, 10:44
	Mysterious Light, Да нет правильный ответ у Вас выдает. Я тоже проверил перебором в лоб своим кодом. 0