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.

learn more… | top users | synonyms

-4
votes
2answers
58 views

Proof By Induction [on hold]

I am trying to prove the Following, However, I dont understand what to do at the Inductive Step: Any Help would be appreciated!
4
votes
2answers
107 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
0
votes
1answer
21 views

Bitstring Probability

I am not understanding how to apply n choose r and permutations to the following problem. Given a bit string of length 8 that has exactly three 0's, what is the probability that the bit string will ...
0
votes
1answer
13 views

How many comparisons are needed for a binary search in a set of 64 elements

Answer: So the recurrence relation for binary search is f(n) = f(n/2) + 2. ...
2
votes
1answer
37 views

calculating characteristic polynomial in $\mathbb{R}^n$

Given some hyperplane arrangement $\mathcal{A}$, we call any subset $\mathcal{B}\subseteq \mathcal{A}$ $\textit{central}$ if $$\displaystyle \bigcap_{H\in \mathcal{B}}H\neq \emptyset.$$ There is a ...
0
votes
1answer
25 views

Summation. Combining different set of indices.

I am reading the second chapter of Concrete Mathematics book and I cant get my head aroud a simple concept: it is stated there that $$ \sum _{k \in K} a_k + \sum _{k \in K'}a_k = \sum _{k \in K \cap ...
1
vote
1answer
48 views

There are 8 balls which appear identical. However, 1 is heavier than the rest. How do you find the ball with 2 weighings?

I understand there are similar problems but I am not sure how to go about constructing this problem with set of balls that are not exponents of 3^n. I know I need at least 2 weighings to find the ...
1
vote
1answer
33 views

Drawing Bijections for one set

I just want to make sure I understand what to do when asked to draw bijections. So when I am asked Draw the diagrams (as we did in class) for all bijections $f : A\to A$ when the set $A$ is $A = \{1, ...
0
votes
1answer
14 views

Suppose that E and F are events in a sample space … [on hold]

Suppose that E and F are events in a sample space and $p(E) = \frac{1}{3}$, $p(F) = \frac{1}{2}$, and $p(E | F) = \frac{2}{5}$. Find $p(F | E)$?
2
votes
1answer
27 views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
0
votes
1answer
29 views

$n$ divides $a_1 - a_2$ as well as $b_1 - b_2$. Show that $n$ divides $a_1b_1 - a_2b_2$.

I keep arriving at $a_1b_1$ and $a_2b_2$ having the same sign if I multiply the equations $a_1 - a_2 = nk$ and $b_1 - b_2= np$ times each other. They must be opposite signs so that I can say that $n$ ...
2
votes
2answers
37 views

Is this proof for 1/4 mod 9 = x, correct?

Find an integer x so (1/4) mod 9 = x Proof: ...
0
votes
0answers
11 views

Need a lower bound for a discrete monotonic distribution

I'm staring at the following expression: $$ \displaystyle \frac{\sum_{i=0}^{n}\sigma_i\left(\sigma_i-\sigma_{i-1}\right) w_i}{\sum_{i=0}^{n} \sigma_i^2}$$ I need to come up with a lower bound to ...
0
votes
1answer
16 views

Still stuck on simplifying terms while doing linear combinations

So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination. For example, a problem is to express the ...
1
vote
0answers
14 views

Verify combination of disjoint subsets $C$ and $D$ is onto

Let $C$ and $D$ be disjoint subsets of set $A$ and $f:C→B$ and $g:D→B$. Define a function $h(x)$ as follows: $$ h(x)=\left\{ \begin{array}{c} f(x) \textrm{ if } x∈C \\ g(x) \textrm{ if } x∈D ...
0
votes
1answer
17 views

Make the set $R$ transitive

Let $R$ be a relation on a set $A=\{w,x,y,z\}$ defined by $R=\{(w,x),(y,x),(x,y),(z,z)\}$. Using the original relation, $R$, make the necessary minimal additions to make $R$ transitive. I thought ...
2
votes
0answers
13 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
3
votes
3answers
228 views

How to prove this argument valid?

I was just wondering if some helpful person wouldnt mind helping me with this discrete maths question that has had be stuck for about a day now. The argument is: ...
-2
votes
2answers
27 views

N Choose K Problem: how many strings of length 8 with exactly five A's are there if characters are chosen from the letters A, B, C, D, E? [closed]

how many strings of length 8 with exactly five A's are there if characters are chosen from the letters A, B, C, D, E?
4
votes
0answers
29 views

Proving $f$ cannot be onto

If $f$ maps finite sets $A$ to $B$ and $n(A) < n(B)$, prove that $f$ cannot be onto. Proof by contradiction: If $f: A→B$ and $n(A) < n(B)$, $f$ is onto. Since, by definition of a ...
1
vote
1answer
18 views

Repeated rules in Chomsky normal form

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times? ¿It's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, ...
0
votes
0answers
42 views

How many strings $s^\infty$ with $s$ a string of length $\le k$ on alphabet $\{1,2,…,m\}$?

As a function of $k$ and $m$, say $f(k,m)$, how many strings are of the form $sss... = s^\infty$, where $s$ is a string of finite length $\le k$ on the finite alphabet $\{1,2,...,m\}$? E.g., ...
3
votes
1answer
42 views

Pigeon Hole Principle : For $n + 1$ numbers

My question is : Take $n + 1$ numbers out of $1, 2,..., 2n$ Show that there will be two consecutive numbers My Approach : Using the Pigeon Hole Principle , the $n$ holes are ...
1
vote
1answer
34 views

Am I right in this discrete mathematics question?

$A = \{0, 1, 2\}$ $B = \{x \in R\mid−1 \le x \lt 3\}$ $C = \{x \in R\mid−1 \lt x \lt 3\}$ $D = \{x \in Z\mid−1 \lt x \lt 3\}$ $E = \{x \in Z+ \mid−1 \lt x \lt 3\}$ I put that $A=D$, $A=C$, and ...
0
votes
1answer
17 views

How does simplification work when solving linear combinations?

So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination. For example, a problem is to express the ...
0
votes
0answers
39 views

Translating English to symbolic logic

(Question prompt) The domain of discourse in this problem is the set of students and teachers at a school. Define the following predicates: • E(x, y): x has sent a letter to y. • P(x): x is a ...
0
votes
0answers
22 views

Baby-step Giant-Step algorithm to calculate value in new base

Using the Baby step–giant step algorithm I am trying to determine $log_{2}(7)$ in base $1$3. Let $p = 7$. Set $n$ to the least integer greater than $\sqrt p$: $n = 3$. So for baby step, I started off ...
2
votes
3answers
44 views

Determining if a relation is reflexive, symmetric, or transitive [closed]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
1
vote
1answer
20 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
1
vote
1answer
25 views

Solving recurrence relations with two variables

whenever I've had to solve recurrence relations, I've kind of just messed around with it until it works. I have a more complicated case, and I was wondering if there are general strategies someone ...
0
votes
3answers
25 views

Finding the equivalence classes of a relation R

Let A = {0,1,2,3,4} and define a relation R on A as follows: R = {{0,0},{0,4},{1,1},{1,3},{2,2},{3,1},{3,3},{4,0},{4,4}}. Find the distinct equivalence classes of R. How do I solve this problem? ...
1
vote
3answers
69 views

Show the closed form of the sum $\sum_{i=0}^{n-1} i x^i$ [duplicate]

Can anybody help me to show that when $x\neq 1$ $$\large \sum_{i=0}^{n-1} i\, x^i = \frac{1-n\, x^{n-1}+(n-1)\,x^n}{(1-x)^2}$$
-1
votes
0answers
16 views

What will be the negation of the following proposition number (iii)? [closed]

I want to know the method for solving part iii of this question.. Someone please help me !
1
vote
1answer
78 views

Interesting Graph Theory “WOMVIES” problem

Here is an interesting problem: A graph is a set of vertices (points), some pairs of which are joined by an edge. For this problem, we will not allow an edge to join a vertex to itself (i.e., no ...
0
votes
1answer
31 views

Proving Equivalence Relations On A Set

Let X be the set of all nonempty subsets of {1,2,3}. Then X = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} Define a relation R on X as follows: for all S and T in X, SRT if, and only if, the least ...
2
votes
2answers
36 views

Counting and solving bijection

Given the problem: Please count how many functions $f : D → \{0, 1 \}$ can be defined if the domain D is a finite set with the cardinality $|D| = n$. Is there a bijection between the set of all such ...
0
votes
0answers
22 views
0
votes
2answers
30 views

binary relations

I am having a hard time understanding some things dealing with these relations. The five relations we are dealing with are reflexive, symmetric, transitive, irreflexive, and antisymmetric. $R$ is ...
-1
votes
1answer
19 views

Determine which of these are strongly connected. Explain why or why not. [closed]

I'm not sure how to determine this.. Is there a certain formula?
1
vote
2answers
28 views

Given a complete graph of n vertices Kn (has all possible edges – one edge between pair of vertices).

Given a complete graph of n vertices $K_n$ (has all possible edges – one edge between pair of vertices). Use counting to find a formula in $n$ for the number of edges in the graph. I know that the ...
2
votes
1answer
51 views

Find closed form formula [on hold]

I need help to find closed form formula for this summation $$\sum_{i=0}^{\infty}(x-y)^i$$
0
votes
0answers
18 views

(a) Given the graph below, for each pair of vertices given in (i) and (ii) gi

so I think I've figured out part a) but I'm not sure.. my solution is: a) part i) $v_1 \rightarrow v_3 \rightarrow v_7 \rightarrow v_5 \rightarrow v_8 \rightarrow v_4 \rightarrow v_2 \rightarrow ...
1
vote
1answer
17 views

One hypothesis concerning Hamming distance matrix

Suppose $a_1, a_2, \ldots, a_m$ are different strings of the same length n. And let $V = [v_1, v_2, \ldots, v_n]$ be a matrix such that $V_{i, j}$ is a Hamming distance between $a_i$ and $a_j$. ...
1
vote
2answers
49 views

Discrete Math: Implication

If $\neg(P) \to \neg(Q) = Q \to P$ works as a Rule, then why doesn't $\neg(P) \to \neg(Q) = P \to Q$ work as a rule.
1
vote
1answer
23 views

Graphing digraphs with the following vertex set

Just want to make sure I did this correctly.. I think I did part a) correctly? Here is my solution for part a) Not sure how to do b) and c) though. Any advice would be great. Thanks in advance
1
vote
1answer
20 views

Proof of cardinalities sets

Prove that the cardinality of set $A^{B+C}$ is equal to the cardinality of $A^{B}\times A^{C}$. I think I need to make functions from $B+C$ to $A$ and one from $B$ to $A$ and one from $A$ to $C$. I ...
0
votes
1answer
53 views

Does the graph exist with these degrees?

$(11,2,2,2,2,2,2,2,1)$ Is it possible that a degree of a vertex can be 11 ? However, there are only 9 vertices. Does the graph exist?
0
votes
2answers
32 views

Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$ We are given this hint: To do ...