Нетрадиционна Комбинаторика

Нека имаме обектите - a,b,c,d,e,f,g. По колко уникални начина можем да изберем четири от тях.

Това е задача с която всеки който е чувал за комбинаторика може да се справи.

Обаче в процес на работа ми се наложи да реша една подобна задача и никакво ровене из офлайн и онлайн литература не помогна. Та задачата е следната (в общия случай).

Имаме n1 на брой обекта а1, n2 на брой обекта a2, ... , nR на брой обекта aR, като n1+n2+...+nR = n. По колко уникални начина могат да се изберат m обекта (m <= n)?

Въпроса ми е има ли формула за общия случай и ако има каква е тя.

В процеса на изследване на проблема се натъкнках на следната интересна подробност. Нека фиксираме n и разпишем всички възможни разпределения на n1, n2, ..., nR. Предполагам за никого не е учудващо, че разпределенията са точно p(n) на брой, където p(n) е n-тото partition number (не зная как е на български).

Ще съм благодарен някой ако помогне.

При а1,а2,.., аR = 1 отговорът е коефициентът пред x^m след развиване на (1+х)^n и привеждане в нормален вид. Това е така, защото мислим за всеки израз в скоби като отговарящ на уникален елемент, а степента на х в скобите указва кратността, с която е взет елементът (в случая може 0 или 1). Отговорът е равен на комбинациите без повторение, т.е., n!/m!/(n-m)!.

По същата логика, в общия случай отговорът е коефициентът пред x^m след развиване на ПРОИЗЕДЕНИЕ "I=1 до R" на (1+х+..+x^aI).

В частност, когато m <= min (a1,...,аR), отговорът е равен на комбинациите с повторение, т.е., (n+m-1)!/m!/(n-1)!

Ами аз така като я гледам тая задачка, трудно ще я докараш до някаква формула, дето се пише на един ред с разни факториели. По-скоро това ще се окаже невъзможно.

Мога да предложа рекурентна формула за пресмятането на комбинациите. Да кажем, можем да оценим, колко обекта от вид a1 е допустимо да изберем в общите m. Тези обекти от вида a1 трябва да са най-малко
max(0, m+n1-n)
и най-много
min(n1, m)
Сега за всяко число x в този интервал задачата се свежда до избор на останалите m-x елемента от останалите r-1 групи.

Може да се направи някаква програмка, която на С++ би могла да изглежда примерно така:

/* Пресмятането се извършва от функцията int count(const int *n, int r, int m).

   n[] е масив с r елемента, съдържащ броя на обектите от всеки вид (n1, n2,..., nr)

   m е броят на избраните обекти */



int count_r(const int *n, int r, int m, int total)

{

  if (r == 1) return 1;

  int result = 0;

  int select_min = max(0, m + n[r - 1] - total);

  int select_max = min(m, n[r - 1]);

  for (int selected = select_min; selected <= select_max; selected++)

    result += count_r(n, r - 1, m - selected, total - n[r - 1]);

  return result;

}



int count(const int *n, int r, int m)

{

  int ntotal = 0;

  for (int i = 0; i < r; i++) ntotal += n[ i];

  if (m > ntotal || m < 1) return 0;

  else return count_r(n, r, m, ntotal);

}

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

Първо благодаря за мненията, довечера след ще ги обмисля, проверя и ще взема отношение по тях.

Между другото ето една задачка която поражда този проблем:

Дадено е каноничното разлагане на естественото число N.

N=P1^a1*P2^a2*...*Pk^aк

Където Pi е i-тото просто число.

Да се намерят всички възможни разлагания на числото N с два множителя.

Ето моите разсъждения. Въвеждаме помощна функция F която е равна на броя на групите имащи елементи повече или равни на k:
F(x) = count( nj >= x) for j in [1,R]

F(x) приема стойности [ 0, R] където R е броя на групите


И така започваме с индукция:

1 element = R = F(1)

2 elements = F(1)*F(2) / 2!

3 elements = F(1)*F(2)*F(3) / 3!

И така стигаме до общата формула:

За m elements = (П F(i) ) /m!  for i in [1,m]

Има някои неща за доуточняване в граничните случаи, като например колко трябва да връща F когато x e по-голямо от R.

Хм... Притеснява ме това, че ако кой да е член F(i) от твоята формула е 0, резултатът също ще е нула.

Дали разбрах правилно условието? Давам пример:

Нека r=3, n1=3, n2=1, n3=4, m=5.

Начините за избор на 5 елемента са общо 7:

1) 3 от вид а1, 1 от вид а2, 1 от вид а3 = (3, 1, 1)
2) (3, 0, 2)
3) (2, 1, 2)
4) (2, 0, 3)
5) (1, 1, 3)
6) (1, 0, 4)
7) (0, 1, 4)

Уви, формулата ми е грешна, защото дава неверни резултати дори още преди F да започне да връща 0. В примера за m =2 изчислявам 3, докато броят на комбинациите е 5.

Явно формулата е по-сложна.

При новата задача имаме различие, защото ако мислим за единия делител като урна, в която теглим прости числа, толкова пъти, колкото са техните кратности, то сумарният брой изтегляния, m, няма да бъде точно фиксиран.

Ето едно решение. Броят делители на N е Q = (a1+1)*..*(aK+1).

Понеже тези делители два по два дават произведение N, то техният брой следва да бъде разделен на 2. Единственото, което остава да забележим, е, че при N точен квадрат, делителят sqrt(N) от двойката sqrt(N)*sqrt(N) е броен един, вместо два пъти. Ще компенсираме това като прибавим 1.

При N точен квадрат отговорът е (Q+1)/2.
При останалаите случаи отговорът е Q/2.

Oбобщено, отговорът е ceil(Q/2).