Skoro disjunktní podmnožiny
Úloha číslo: 4424
Spočítejte, kolik existuje uspořádaných dvojic množin \((A,B)\) takových, že \(A,B\subseteq\{1,\ldots,n\}\) a \(|A\cap B|=1\).
Řešení
Nejprve vybereme jeden prvek, který leží v průniku \(A\cap B\) – to jde udělat \(n\) způsoby. Pro každý ze zbývajících \(n-1\) prvků si pak můžeme nezávisle vybrat, zda bude jenom v \(A\), jenom v \(B\), nebo v ani jedné z množin.Odpověď
\(n\cdot 3^{n-1}\)
