# Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

1,718 questions
24answers
33k views

6answers
18k views

3answers
2k views

### Prove $f(S \cup T) = f(S) \cup f(T)$

$f(S \cup T) = f(S) \cup f(T)$ $f(S)$ encompasses all $x$ that is in $S$ $f(T)$ encompasses all $x$ that is in $T$ Thus the domain being the same, both the LHS and RHS map to the same $y$, since the ...
3answers
335 views

6answers
25k views

### Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
3answers
5k views

### Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin

The number of ways to put $n$ unlabeled balls in $k$ distinct bins is $$\binom{n+k-1}{k-1} .$$ Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
3answers
767 views

### Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer

Letting $f_n$ be the Fibonacci numbers, show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer. Just some homework help. Need to prove. Thank you in ...
8answers
14k views

### What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
3answers
6k views

### Gay Speed Dating Problem

Here's an interesting problem that I came up with the other night. With straight speed dating, (assuming the number of men and women are equal) the number of iterations that need to be made before ...
2answers
93k views

5answers
10k views