Подскажите формулу для последовательности чисел

@ronaldo · Регистрация: 16.06.2014

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

Доброго времени суток.
Дана квадратная матрица. Находясь в левом верхнем углу, требуется добраться до правого нижнего угла, двигаясь либо вправо, либо вниз. Сколькими способами это можно сделать?
Например, если размер матрицы 2x2, то существует 2 способа решения задачи (1 способ - сначала двигаемся вправо, потом - вниз; 2 способ - сначала двигаемся вниз, потом - вправо).
Если размер матрицы 3x3, то существует 6 способов решения задачи.
Если размер матрицы 4х4, то существует 20 способов решения задачи.
Итак, мой вопрос: как, зная размерность матрицы, выразить число способов решения задачи?

@_Ivana · 15.01.2015, 10:09

(2*n)!/(n!)^2, где n равно размерность матрицы минус 1

@SlavaSSU · 15.01.2015, 11:03

C(2 * n - 2, n - 1)

@_Ivana · 15.01.2015, 11:10

SlavaSSU, расскажете как вывели?

@SlavaSSU · 15.01.2015, 11:17

_Ivana, ну. у нас всего будет 2 * n - 2 шагов, из них ровно n - 1 вправо и ровно n - 1 вниз. Ну типо представим то шаг вправо -это 0, шаг вниз - это 1. тогда задача такая - сколько существует последовательностей из 0 и 1 длины 2 * n - 2, в которой ровно n - 1 единица и n - 1 ноль.

@_Ivana · 15.01.2015, 11:19

Именно - сколько

А то получается как в известном анекдоте, про то как математик быстро посчитал количество коров на поле, его спросили как он это сделал а он сказал - это просто, надо посчитать число ног и разделить на 4.

@SlavaSSU · 15.01.2015, 11:22

_Ivana, ну. ок тогда так попробую. есть 2 * n - 2 пустых клеток. сколькими способами можно засунуть ровно в n - 1 клетку кроликов.

нам надо из пустых клеток выбрать фиксированное количесвто - ну это и есть Цшка.

@_Ivana · 15.01.2015, 11:24

(2n-2)(2n-3).... и так n-1 раз

@SlavaSSU · 15.01.2015, 11:28

_Ivana,

я кстати понял как ты получил.
опять представим n пустых клеток. будем пихать кроликов всегда в 1 половину. и каждый раз перемешивать. тгода получим (2 * n)! способов.
но у нас 1 половина учлась (n!) ^ 2 раз.

@_Ivana · 15.01.2015, 11:28

SlavaSSU, понятно, спасибо.

ЗЫ типа того

@SlavaSSU · 15.01.2015, 11:30

_Ivana, ну блин. у нас есть 2 * n - 2 элементов, нам надо выбрать ровно n - 1 из них. при чем неважно в каком порядке мы их выбирали, важно только иоговое подмножество. это же по определению Цшка.

@ronaldo · 15.01.2015, 11:40 **[ТС]**

C(2 * n - 2, n - 1)

Что такое C, для непросвещённых?

@SlavaSSU · 15.01.2015, 11:42

ronaldo, число сочетаний.

@_Ivana · 15.01.2015, 12:03

А давайте поиграем для кубической матрицы и для произвольной размерности?

Добавлено через 6 минут
Интересно, как вы там справитесь цэшками

Добавлено через 3 минуты
(kn)!/(n!)^k

@SlavaSSU · 15.01.2015, 12:14

_Ivana, ну размеры n, m, k.
тогда так C(n + m + k - 3, n - 1) * C(m + k - 2, m - 1);

@_Ivana · 15.01.2015, 12:18

Блин, а я выше только для гиперкубов произвольной размерности вывел. Для гиперпараллелепипедов пока нет...

Добавлено через 1 минуту
А тут как назло на работу уже пора

@SlavaSSU · 15.01.2015, 12:20

_Ivana, задача такая же осталась.
сколько существеут последовательностей заданной длины, в которой фиксированное число нулей, единиц и двоек.
и там чем больше размерностей, тем больше различных цифр.

@_Ivana · 15.01.2015, 12:22

SlavaSSU, правильно. Вот мы и немного по-разному думаем про эту задачу.

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:42	13
	ronaldo, число сочетаний. 0

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
		1
	Подскажите формулу для последовательности чисел 15.01.2015, 07:59. Показов 1161. Ответов 17 Метки нет (Все метки) Доброго времени суток. Дана квадратная матрица. Находясь в левом верхнем углу, требуется добраться до правого нижнего угла, двигаясь либо вправо, либо вниз. Сколькими способами это можно сделать? Например, если размер матрицы 2x2, то существует 2 способа решения задачи (1 способ - сначала двигаемся вправо, потом - вниз; 2 способ - сначала двигаемся вниз, потом - вправо). Если размер матрицы 3x3, то существует 6 способов решения задачи. Если размер матрицы 4х4, то существует 20 способов решения задачи. Итак, мой вопрос: как, зная размерность матрицы, выразить число способов решения задачи? 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 10:09	2
	Сообщение было отмечено ronaldo как решение Решение (2*n)!/(n!)^2, где n равно размерность матрицы минус 1 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:03	3
	C(2 * n - 2, n - 1) 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 11:10	4
	SlavaSSU, расскажете как вывели? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:17	5
	_Ivana, ну. у нас всего будет 2 * n - 2 шагов, из них ровно n - 1 вправо и ровно n - 1 вниз. Ну типо представим то шаг вправо -это 0, шаг вниз - это 1. тогда задача такая - сколько существует последовательностей из 0 и 1 длины 2 * n - 2, в которой ровно n - 1 единица и n - 1 ноль. 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 11:19	6
	Именно - сколько А то получается как в известном анекдоте, про то как математик быстро посчитал количество коров на поле, его спросили как он это сделал а он сказал - это просто, надо посчитать число ног и разделить на 4. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:22	7
	_Ivana, ну. ок тогда так попробую. есть 2 * n - 2 пустых клеток. сколькими способами можно засунуть ровно в n - 1 клетку кроликов. нам надо из пустых клеток выбрать фиксированное количесвто - ну это и есть Цшка. 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 11:24	8
	(2n-2)(2n-3).... и так n-1 раз 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:28	9
	_Ivana, я кстати понял как ты получил. опять представим n пустых клеток. будем пихать кроликов всегда в 1 половину. и каждый раз перемешивать. тгода получим (2 * n)! способов. но у нас 1 половина учлась (n!) ^ 2 раз. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 11:30	11
	_Ivana, ну блин. у нас есть 2 * n - 2 элементов, нам надо выбрать ровно n - 1 из них. при чем неважно в каком порядке мы их выбирали, важно только иоговое подмножество. это же по определению Цшка. 0

	15.01.2015, 12:22

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	15.01.2015, 11:40 [ТС]	12
	C(2 * n - 2, n - 1) Что такое C, для непросвещённых? 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 12:03	14
	А давайте поиграем для кубической матрицы и для произвольной размерности? Добавлено через 6 минут Интересно, как вы там справитесь цэшками Добавлено через 3 минуты (kn)!/(n!)^k 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 12:14	15
	_Ivana, ну размеры n, m, k. тогда так C(n + m + k - 3, n - 1) * C(m + k - 2, m - 1); 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	15.01.2015, 12:18	16
	Блин, а я выше только для гиперкубов произвольной размерности вывел. Для гиперпараллелепипедов пока нет... Добавлено через 1 минуту А тут как назло на работу уже пора 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	15.01.2015, 12:20	17
	_Ivana, задача такая же осталась. сколько существеут последовательностей заданной длины, в которой фиксированное число нулей, единиц и двоек. и там чем больше размерностей, тем больше различных цифр. 0

Подскажите формулу для последовательности чисел

Решение