Temporary - Discrete Math
Réviser ces flashcardsGratuit · répétition espacée · iPhone, Android, Mac et web
Toutes les cartes
1
Counting the number of solutions to the following equality:
$x_1 + \cdots + x_n = k$
where all $x_j$ and k belong to $\mathbb{N}$.
$x_1 + \cdots + x_n = k$
where all $x_j$ and k belong to $\mathbb{N}$.
Stars and Bars:
$\binom{k+n-1}{k}$
$\binom{k+n-1}{k}$
2
Counting number of solutions to the following equality:
$x_1 + \cdots + x_n = k$
where all $x_i > 0$.
E.g., $n = 3$ and $k = 5$.
$x_1 + \cdots + x_n = k$
where all $x_i > 0$.
E.g., $n = 3$ and $k = 5$.
Substitute $y_i + 1 = x_i$ in the equality:
$x_1 + x_2 + x_3 = 5$ with $x_i > 0 \equiv x_i \ge 1$
$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) = 5$ with $y_i + 1 \ge 1$
$y_1 + y_2 + y_3 = y_i \ge 0$
Now we can use stars and bars as usual.
$x_1 + x_2 + x_3 = 5$ with $x_i > 0 \equiv x_i \ge 1$
$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) = 5$ with $y_i + 1 \ge 1$
$y_1 + y_2 + y_3 = y_i \ge 0$
Now we can use stars and bars as usual.
3
Definition of a Composition of an Integer
Number of Compositions for an Arbitrary $n \in \mathbb{N}$
Number of Compositions for an Arbitrary $n \in \mathbb{N}$
Sum of strictly positive integers summing to a given n.
The number of compositions is $2^{n-1}$ for any $n \in \mathbb{N}$.
The number of compositions is $2^{n-1}$ for any $n \in \mathbb{N}$.
4
Counting the Number of Unit Paths from $\langle 0,0 \rangle$ to $\langle a , b \rangle$ in $\mathbb{N}^2$.
$\binom{a+b}{a}$
5
Value of $\sum_{a+b=n} \binom{a+b}{a}$
$2^n$
6
Catalan Numbers and Interpretation ITO Unit Paths
The nth Catalan number is computed as:
$\frac{1}{n+1} \binom{2n}{n}$
Its value tells us the number of unit paths from the origin to $\langle n , n \rangle$ which never above the line $y = x$.
$\frac{1}{n+1} \binom{2n}{n}$
Its value tells us the number of unit paths from the origin to $\langle n , n \rangle$ which never above the line $y = x$.
7
Counting the number of bijections between two (finite) sets A and B.
The number of functions $f : A \to B$ is $\lvert B \rvert ^ { \lvert A \rvert }$.
8
Counting the number of injections between two (finite sets A and B).
Let $n = \lvert A \rvert$ and $m = \lvert B \rvert$.
Then, the number of injections $f : A \to B$ is:
$\frac{ m! }{ (m-n)! }$
Then, the number of injections $f : A \to B$ is:
$\frac{ m! }{ (m-n)! }$
Plus de flashcards : Mathématiques
Quant MountainMathématiques · AnglaisNicoleGearsMathématiques · AnglaisJuhnFormulae and Equations - 6Mathématiques · AnglaisHrithik5- How to Calculate Present ValuesMathématiques · AnglaisMercedesCh 13: Vector FunctionsMathématiques · AnglaisJohnLecture 2 DSP DreiMathématiques · AnglaisDiandreiDerivates/Integrals of Trig, Identities, etc.Mathématiques · Latinbenjac05La mole Mathématiques · FrançaisGaétanDM 1.4 Vocabulary Mathématiques · AnglaisarpeggiFlashcards Chapitre 1Mathématiques · FrançaisCarolineStructural Theory FormulasMathématiques · AnglaisMPLEMedical Unit Conversions and FormulasMathématiques · Anglaishikaru
Tous les decks : Mathématiques
Révise ces decks dans l’app
Gratuit sur iPhone, Android, Mac et le web. Ajoute n’importe quel deck à ton compte en un tap.
