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

1
vote
1answer
24 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 ...
2
votes
3answers
40 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}$$
0
votes
1answer
15 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 ...
1
vote
1answer
12 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)$ ...
0
votes
0answers
14 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 ...
1
vote
1answer
18 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 ...
2
votes
3answers
34 views

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

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
0
votes
0answers
25 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
3answers
18 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
0answers
22 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
2answers
26 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 ...
0
votes
1answer
19 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 ...
-1
votes
0answers
15 views

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

I want to know the method for solving part iii of this question.. Someone please help me !
2
votes
2answers
20 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 ...
2
votes
0answers
93 views
+50

basic concept about edge graphs (line graphs)

I was learning about the edge graphs or line graphs $L(G)$ of a graph $G$. I read about the relation between degree of any two vertices $u$ and $v$ in $G$ and that of edge $uv$ in $L(G)$. I am just ...
1
vote
0answers
35 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
1
vote
2answers
46 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
votes
1answer
12 views
1
vote
2answers
8 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
33 views

Find closed form formula

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

difference between “minimal” and “minimum” edge cuts.

I was going through the topic about connectivity of graphs. There it was mentioned about the terms "minimum edge cut" and "minimal edge cut". I know both are the sets of edges if removed from the ...
0
votes
0answers
11 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
14 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
12 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$. ...
0
votes
1answer
19 views

Converting a regular language to a deterministic machine.

How does on go about converting a regular language to a deterministic machine? What are the steps involved. The language I'm working with is as follows: $$(00000 + 0111 + 100)^* (0 + 1)$$ I'd rather ...
0
votes
0answers
34 views

Recurrence in two variables

Anyone know how to solve the following recurrence relation in two variables: $$ f(x,y) = b f(x-1,y) + c f(y,x-1), \qquad \begin{cases}f(x,0) = b^{(x-1)} \\ f(0,y) = 0 \end{cases} $$ (Note: repost of ...
0
votes
0answers
49 views

How does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?

I'm having some serious problems with Dilworth's Theorem. My question is 'how does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?'. Any help is appreciated.
3
votes
1answer
410 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
1answer
17 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
0answers
26 views

Is the algebra of these circuits valid?

I drew these circuits when I was studying Boolean Algebra. Is the algebra of these circuits valid?
0
votes
1answer
23 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
0
votes
0answers
39 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
1answer
303 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
0
votes
2answers
18 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 ...
0
votes
1answer
14 views

General solution to discrete dynamical system.

I am trying to find the general solution to the following discrete dynamical system: $$H(n+1) = 0.89H(n) + 30$$ $$E(n+1) = 0.64E(n) + 0.11H(n)$$ $$o(n+1) = 0.88o(n) + 0.36E(n) + 30$$ $H(0) = 3500$ ...
0
votes
0answers
11 views

Fast Fourier Transform Splitting Algorithm

I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect $ ...
1
vote
0answers
53 views

Deduction method with a quantified statement

In this expression I am trying to prove is a valid argument using the deduction method that is using equivalences and rules of inference in a proof sequence. ...
0
votes
1answer
44 views

Closed form for the summation [on hold]

Can anyone help me to find what is closed form formula for this summation formula $$\sum\limits_{n=0}^mx^n\sum\limits_{i=0}^ny^i$$
0
votes
0answers
27 views

How to solve this discrete question? [on hold]

Newbie to discrete math. Ask for how to start up. Thanks a lot.
-2
votes
1answer
22 views

Discrete Math Lattice Points [on hold]

I'm not sure how to start this problem but I think this has to do with the Inclusion-Exclusion Principle. Please help. Thank you
-1
votes
2answers
70 views

Simplifying on logic Operations

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
1
vote
1answer
20 views

Possible configurations on the subset problem

Let $A=\left\{ a_{i}\right\} $ be a sequence of $n$ positive numbers such that $\sum a_{i}=1$. We define $C\left(A\right)=\left\{ \left\{ b_{i}\right\} \subset\left\{ 1,2..,n\right\} :\sum ...
-3
votes
1answer
20 views

Discrete Mathematics linear recurrence [on hold]

Prove the summation formula using induction: $$\sum_{k=1}^{n} \frac{1}{k(k+1)}=1-\frac{1}{n+1}$$
0
votes
1answer
36 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
0
votes
3answers
49 views

Proof By Induction $2^n \ge n^2$ for $n\ge4$

I am trying to prove the following, and here is what I have done: Can somebody help to complete this? $2^n \ge n^2$ for $n\ge 4$ $n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE Assume ...
0
votes
1answer
30 views

What is the walk of this graph?

A walk that is not a trail from vertex 1 to vertex 3; A trail that is not a path from vertex 1 to vertex 3; A path from vertex 1 to vertex 3. How can I describe these walks?
0
votes
1answer
39 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
5
votes
1answer
110 views

Evaluate complicated sum

Evaluate following sum: $$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$ Hint: use combinatorial ...
0
votes
1answer
48 views

solving a recurrence without initial conditions

I have been working on this problem for two days... I can only get as the characteristic part of the recurrence, I just can't figure out a proper guess for the particular solution. ...