мат задача, комбинаторика

[Mayor]

мат задача, комбинаторика

условия задачки просты: сколькими способами можно разместить n одинаковых элементов, между m лунками?

решается тоже просто методом простой итерации ...

вопрос какой формулой она решается аналитически?

если нет формулы то как ее решить итеративно за n или m шагов?

[Алексей++]

Mayor1, а что означает - "между m лунками"  ?

[Вад]

Mayor1, поиск рулит, вики тоже в меру сил: Размещение

[Mayor]

Mayor1, поиск рулит, вики тоже в меру сил: Размещение

неправильная ссылка - там размещаются не однородные элементы
в этой задаче однородные

[Mayor]

Mayor1, а что означает - "между m лунками"  ?

емкость или что тебе угодно, любая из m лунок может принять от 0 до n элементов ...
но по задаче сумма элементов в лунках равна n

[Алексей++]

если представить в виде функции N(m,n) , то , вроде бы, выходит такое рекурсивное определение

N(m+1,n) == 3 * ( N(m,n)+ N(m-1,n-1)+...+ N(m-1,0))

где N(m,0) ==
  1 при m>0
  0 при m<=0

на рисунке: слева - m==2, n==3  ; справа: m==3, n==3

[Алексей++]

вот, подправил


тогда

N(3,3) == N(2+1,3) == 3* ( N(2,3) + N(1,2) + N(1,1) +1 ) == 3*(4+1+1+1) == 21

не, всё равно фигня вышла (((

[Вад]

Mayor1, ну, превращаем размещение в сочетание, если ничего не путаю.

[Алексей++]

и понятно почему фигня - там повторные комбинации на рисунке, как их учесть - фик знает

[Вад]

Вообще, по-моему, задачу нужно рассматривать не как размещение n позиций m по лункам, а как размещение m-1 лунок по n+1 позициям
Тогда требуется посчитать, каким числом способов можно вставить m-1 лунку на n+1 позицию "между элементами" (включая позицию "до всех" и "после всех"). Задача аналогична задаче нахождения количества возможных чисел из m+n-1 разрядов, содержащих (m-1) нулевых разрядов и n ненулевых разрядов. (Одну "лунку" в расчёт не принимаем, она всегда находится "в конце"). Иллюстрация примерно такая: <0> 1 <0> 1 <0> ... <0> 1 <0> 0, где <0> - возможное место вставки одного и более нулей. Если лунки тоже полагаем одинаковыми (в том смысле, что для двух лунок безразлично, в первой или во второй лежат все элементы) - вот тогда используем сочетание уже. Из твоей задачи одинаковость неочевидна

[Вахмурка]

 Задача сводится к нахождению максимального значения n-разрадного числа + 1, с основанием исчесления m т. е. m^n . Если я правильно задание понял.

[Mayor]

Задача сводится к нахождению максимального значения n-разрадного числа + 1, с основанием исчесления m т. е. m^n . Если я правильно задание понял.

неа не правильно понял

формулу нашли, только я не понял как:
f(n,m) = (n+1)*(n+2)* ... (n+m-1) / m!    - как ее можно было вывести?

вот проверка для m==4:

Код:

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main() {
	int elem,cell;
	int count=0;
	for (int elem=1;elem<10;elem++) {
		count=0;
		for (int q=0;q<=elem;q++) {
			for (int z=0;z<=elem;z++) {
				for (int x=0;x<=elem;x++) {
					for ( int y=0;y<=elem;y++) {
						if (x+y+z+q==elem) {
							cout<<q<<"\t"<<z<<"\t"<<x<<"\t"<<y<<endl;
							count++;
						}
					}
				}
			}
		}
		cout<<elem<<"\t"<<count<<endl<<endl;
	}
}

[Вахмурка]

  Если n - неоднородные элементы, то количество способов равно m^n где m - количество позиций. Если элементы однородные, то из этого выражения нужно вычесть все комбинации чисел которые выводятся друг из друга перестановкой цифр. Например при n =2 97 и 79 дают одну комбинацию, значит одно из них можно удалить. Всё усложняется при увелечении n. Например при n =3 нужно расматривать не только пары чисел, но и тройки. Отсюда рекурсивность формулы. Вот такие вот мысли.

[Вахмурка]

 Есть типа ещё одна идея: сначало написать алгоритм, а потом по нему попробовать вывести формулу. Правдо мне такими вещами заниматься не приходилось.

[Вахмурка]

Рекурсивно задача довольно таки просто решается: прдеставляем что пересыпаем элементы из одной лунки в другую. Если за количество позиций принять m то получается вот такой код:

Код:

class Test {
   static int metod ( int n, int m ) {
      if ( m == 1 )
         return 1 ;
      int k = 0 ;
      for ( ; n > 0 ; n -- ) 
         k += metod ( n, m - 1 ) ;
      return k + 1 ;
    }
}

[Mayor]

  Если n - неоднородные элементы, то количество способов равно m^n где m - количество позиций. Если элементы однородные, то из этого выражения нужно вычесть все комбинации чисел которые выводятся друг из друга перестановкой цифр. Например при n =2 97 и 79 дают одну комбинацию, значит одно из них можно удалить. Всё усложняется при увелечении n. Например при n =3 нужно расматривать не только пары чисел, но и тройки. Отсюда рекурсивность формулы. Вот такие вот мысли.

угу ... есть у кого идеи как можно было вывести эту формулу:
f(n,m)= ((n+m)!-n!)/n!

[Вад]

Mayor1,  f(n,m)= ((n+m)!-n!)/n! = ((n+m)! / n!) - 1? Это точно так будет?

[Sands]

Mayor1, По моему формула немного ошибочна, потому что если взять 2 лунки и 2 элемента, то по цормуле выходит ((2+2)!-2!)/2!=(12-2)/2=5
но(если я правильно пощитал)таких размещений всего 3 - (2,0);(1,1);(0,2)

[Mayor]

Mayor1, По моему формула немного ошибочна, потому что если взять 2 лунки и 2 элемента, то по цормуле выходит ((2+2)!-2!)/2!=(12-2)/2=5
но(если я правильно пощитал)таких размещений всего 3 - (2,0);(1,1);(0,2)

Да точно
F(n,m)=(n+1)*(n+2)*...(n+m-1)/((m-1)!)
это будет более правильный вариант

[Sands]

Mayor1, Судя по формуле F(n,m)=(n+m-1)!/((m-1)!*(n)!) = C(m-1,n+m-1) Что собственно и было предложено Вадом,(ну почти так ) несколькими постами выше(если конечно я его правильно понял)