Брой на релации между две крайни множества

[Davids]

Едно късичко разяснение относно сметките по следната задача би било високо оценено, че се озорвам малко с ориентацията из релациите.

Нека $A$ и $B$ са крайни множества. Да се определи броя на релациите $R \subseteq A\times B$ в зависимост от $|A|$ и $|B|$, ако $R$ притежават следните свойства:
а) $R$ са дясноеднозначни (не знам как е точно на български понятиет, но описано: $\forall x\in A ~\exists ! y: f(x) = y$ или: на всеки елемент от $А$ съответства най-много един от $B$)
б) $R$ са дясноеднозначни, но не лявототална (лявототална или както следва да се преведе на български ще рече, че не всички елементи от $A$ участват в релацията)
в) $R$ е лявототална или не е дясноеднозначна.

Сега по първата подточка с разсъжденията си съм стигнал единствено до извода, че броя на всички такива $R$ е степен с основа $(2^{|A|} - 1)$, но и за това не съм много сигурен.

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

1.4.png (25.97 KiB) Прегледано 601 пъти

[Добромир Глухаров]

Още не съм сигурен, че нямам грешка, но за а) и б) получих съответно $\sum_{k=0}^{\min(|A|,|B|)}C_{|A|}^k.V_{|B|}^k$ и $\sum_{k=0}^{\min(|A|-1,|B|)}C_{|A|}^k.V_{|B|}^k$, където $V_n^k=n(n-1)(n-2)...(n-k+1)$ са вариации от $n$ елемента $k$-ти клас, а $C_n^k=\frac{n(n-1)(n-2)...(n-k+1)}{k!}$ са комбинации от $n$ елемента $k$-ти клас.

в) по формулата на Де-Морган от логиката го разбирам да не е вярно, че е дясноеднозначна и не е лявототална, т.е. допълнение на полученото от б) $\to|B|^{|A|}-\sum_{k=0}^{\min(|A|-1,|B|)}C_{|A|}^k.V_{|B|}^k$

[Davids]

Още не съм сигурен, че нямам грешка, но за а) и б) получих съответно $\sum_{k=0}^{\min(|A|,|B|)}C_{|A|}^k.V_{|B|}^k$ и $\sum_{k=0}^{\min(|A|-1,|B|)}C_{|A|}^k.V_{|B|}^k$, където $V_n^k=n(n-1)(n-2)...(n-k+1)$ са вариации от $n$ елемента $k$-ти клас, а $C_n^k=\frac{n(n-1)(n-2)...(n-k+1)}{k!}$ са комбинации от $n$ елемента $k$-ти клас.

в) по формулата на Де-Морган от логиката го разбирам да не е вярно, че е дясноеднозначна и не е лявототална, т.е. допълнение на полученото от б) $\to|B|^{|A|}-\sum_{k=0}^{\min(|A|-1,|B|)}C_{|A|}^k.V_{|B|}^k$

Имам няколко въпроса по генералния подход.
1. При отношенията с посоки (ляво -> дясно), не трябва ли да разгледаме два случая - когато първообраз е А, а В е образ, и vice versa. Или иначе как определяме кое множество е първообраз и кое е образ?
2. Взимал ли си предвид случаите, в които подмножествата в дадена релация не са с еднакъв брой елементи... понеже гледам, че с един итератор ги третираш $A$ и $B$. Но примерно дясноеднозначната релация $\{(1, a), (2, a)\}\in R$, където $\{1, 2\} \in A$ и $a \in B$ например? Струва ми се, че не влиза в сумата... или нещо пропускам?

[Добромир Глухаров]

2. Взимал ли си предвид случаите, в които подмножествата в дадена релация не са с еднакъв брой елементи... понеже гледам, че с един итератор ги третираш $A$ и $B$. Но примерно дясноеднозначната релация $\{(1, a), (2, a)\}\in R$, където $\{1, 2\} \in A$ и $a \in B$ например? Струва ми се, че не влиза в сумата... или нещо пропускам?

Ох, да - може би трябва да вземем вариации с повторения - вместо $V_n^k=n(n-1)...(n-k+1)$ да бъдат $V_n^k=n^k$, но вече съвсем не съм сигурен, че в написаното от мен има нещо вярно.

[Davids]

2. Взимал ли си предвид случаите, в които подмножествата в дадена релация не са с еднакъв брой елементи... понеже гледам, че с един итератор ги третираш $A$ и $B$. Но примерно дясноеднозначната релация $\{(1, a), (2, a)\}\in R$, където $\{1, 2\} \in A$ и $a \in B$ например? Струва ми се, че не влиза в сумата... или нещо пропускам?

Ох, да - може би трябва да вземем вариации с повторения - вместо $V_n^k=n(n-1)...(n-k+1)$ да бъдат $V_n^k=n^k$, но вече съвсем не съм сигурен, че в написаното от мен има нещо вярно.

Моето окончателно размишление по първата подточка:
Дефинираме $f(n, m) = \sum_{i = 1}^n(C_n^i \cdot \sum_{k=1}^{min(i, m)}V^k_m)$, където $n$ е броят на елементите от изходното множество, а $m$ на образното множество.
Тогава общия брой на дясноеднозначните релации ще е $S = f(|A|, |B|) + f(|B|, |A|)$
Как стигнах до това:
Разглеждаме само едната страна: релацията $A \to B$. Другото ще е после еквивалентното, но наобратно...

Тъй като говорим за дясна еднозначност, така или иначе ще трябва да обходим всички възможни подмножества от по от 1 до $|A|$ елемента на $A$. За всяко такова подмножество ще трябва да намерим всички възможни подредби на елементи от дясното множество, с които да го map-нем 1:1 напречно (немного математичски израз, но онагледява идеята най-добре ).
Това ни дава вече първата част: $\sum_{i = 1}^n( C\cdot g(i, m))$, където $g(i, m)$ ще е нашата специална функция, която връща всички възможни съответстващи подмножества от $i$ елемента от $B$.

Тук идва специалният момент с дясната еднозначност. Искаме всички възможни подмножества от $B$, за които обаче един и същ елемент от $A$ няма да бъде пратен при повече от един уникален елемент от $B$. Тоест тук ще ползваме вариации, при което трябва да вземем предвид случая, в който $n > m$. Тоест при тази сума ще ограничим броя на итерациите до таван $m$. Така извеждам функцията: $g(i, m) = \sum_{k = 1}^{min(i, m)}V^k_m$

И така си получаваме окончателната магическа функция, която брои тези така специални релации $A \to B$: $f(n, m) = \sum_{i = 1}^n(C_n^i \cdot \sum_{k=1}^{min(i, m)}V^k_m)$.

Съответно остава да завъртим сумата от двете посоки през функцията, за да си получим окончателния брой на реалциите: $S = f(|A|, |B|) + f(|B|, |A|)$.

С моите скромни тестове, сметките излизат верни