Брой вектори

[Гост]

.

[Knowledge Greedy]

С три единици и една 6-ца са общо четири.
С две единици, една 2-ка и една 5-ца са 12.
С две единици, една 3-ка и една 4 - ка са 12.
С единица, две двойки и една 4-ка са 12.
С единица, двойка и две тройки са също 12.
С три двойки и една тройка са четири.
Изглежда са общо 56.

[Гост]

нещо не го разбирам. Защо например (9,0,0,0) да не върши работа

[ptj]

Виж условието, координатите са естествени.

[Hephaestus]

Множеството е съвкупност от елементи, които не се повтарят. Ако има нужда от повторения на елементите в едно множество, казваме, че това е мултимножество. Например, { [tex]1, 1, 2, 3[/tex] } [tex]=[/tex] { [tex]2, 1, 3, 1[/tex] } [tex]\ne[/tex] { [tex]1, 2, 3[/tex] }. Мултиподмножество наричаме подмножество на мултимножество. Неслучайно уточнявам това, защото ще го използвам в задачата.
[tex]x_{1 } + x_{2 } + x_{3 } + x_{4 } = 9[/tex]
На всяко решение в [tex]N^{4}[/tex] на [tex]x_{1 } + x_{2 } + x_{3 } + x_{4 } = 9[/tex] съпоставяме еднозначно 9-елементно мултиподмножество на
{ [tex]x_{1 }, x_{2 }, x_{3 }, x_{4 }[/tex] } [tex]\Rightarrow[/tex] [tex](a, b, c, d) \rightarrow[/tex] { [tex]x_{1 }, ..., x_{1 }, x_{2 }, ..., x_{2 }, x_{3 }, ..., x_{3 }, x_{4 }, ..., x_{4 }[/tex] }, т.е. [tex]x_{1 }[/tex] се повтаря a-пъти, [tex]x_{2 }[/tex] - b-пъти, [tex]x_{3 }[/tex] - c-пъти и [tex]x_{4 }[/tex] - d-пъти, като е възможно някое от a, b, c или d да е нула, т.е. съответният елемент да не се среща нито веднъж.
[tex](a, b, c, d)[/tex] е решение на [tex]x_{1 } + x_{2 } + x_{3 } + x_{4 } = 9[/tex] (например [tex](3, 3, 2, 1)[/tex] и всички други комбинации с повторение). Броят на различните решения в [tex]N^{4}[/tex] на [tex]x_{1 } + x_{2 } + x_{3 } + x_{4 } = 9[/tex] е колкото този на 9-елементно мултиподмножество на [tex]{x_{1 }, x_{2 }, x_{3 }, x_{4 }}[/tex]. Той е [tex]{9 + 4 - 1 \choose 4 - 1} = {12 \choose 3} = 220.[/tex]

В общ вид броят на различните решения [tex](x_{1 }, x_{2 }, ..., x_{n }) \in[/tex] [tex]N^{n}[/tex] на [tex]x_{1 } + x_{2 } + ... + x_{n } = k[/tex] се дава с [tex]{k + n - 1 \choose n - 1}.[/tex] Формулата може да се използва наготово, тъй като влиза в комбинаториката.

[Гост]

Множеството е съвкупност от елементи, които не се повтарят. Ако има нужда от повторения на елементите в едно множество, казваме, че това е мултимножество. ... [tex]\binom{k + n - 1}{n - 1}[/tex] Формулата може да се използва наготово, тъй като влиза в комбинаториката.

Решението на Hephaestus е с добра идея, но не стига само използването на готовата формула. За да е приложима в дадената задача, трябва да изчислим всички елементи на мултимножеството, които съдържат поне една нула и да ги премахнем.
Цитираните бройки [tex]a, b, c, d[/tex] на елементите [tex]x_1, x_2, x_3, x_4[/tex] може да са нули, но самите [tex]x_1, x_2, x_3, x_4[/tex] не може да са нули. Следователно няма да осъществим взаимно еднозначно съответствие между четворките [tex](x_1, x_2, x_3, x_4)[/tex] и елементите на конструираното мултиподмножество.
Все пак говорим за брой на векторите с координати от [tex]\mathbb{N}[/tex].

[Hephaestus]

Приел съм 0-та за естествено число с причина, разбира се.
В повечето учебници и сборници по дискретна математика нулата я причисляват към множеството на естествените числа. Реших да споделя това решение, защото съм попадал на такъв тип задачи именно в учебници по дискретна математика. Иначе решението на KnowledgeGreedy е достатъчно ясно и разбираемо.