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}\)
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
	Zaslat komentář k úloze