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
33 views

Show that we can check if $G$ has a circuit in time $O(V)$.

Consider a non-directed graph $G=(V,E)$ at which it is not allowed that we have edges of the form $(v,v)$. Show that we can check if $G$ has a circuit in time $O(V)$. According to my notes, we can ...
1
vote
0answers
89 views

Show that any sequence $(u_{n})$ must tends to infinity as $n→∞$

The motiation to this question can be found in About the solution of a difference equation My question is: Show that any sequence $(u_{n})$ verifying the equation in the above question must tends to ...
1
vote
1answer
38 views

How to display one to one correspondence?

This is a problem from Discrete Mathematics and its Applications Here is the book's definition of countable/not countable For 2a, I came up with the fact that the set is countably infinite. What ...
1
vote
0answers
26 views

How do you calculate Up and Down Penalties on a Branch and Bound algorithm of a MILP?

My notes really don't explain this clearly at all, so I have no idea what to do. If I have the following MILP: In which I've been told to solve it using: (a) Rule 1 (choose the variable with the ...
1
vote
1answer
33 views

Would there be no input or input does not exist?

This problem is from Discrete Mathematics and Its Applications. And the definition of inverse from the book: For part 43 (c), would the inverse not exist? For the floor function, in terms of $f(a) ...
1
vote
4answers
55 views

Would this be an acceptable answer for the inverse of floor function

This problem is from Discrete Mathematics and its Applications And the book's definition on inverse Would an acceptable answer to 43b just be the set itself again? What I like to think of the ...
1
vote
0answers
60 views

Discrete Mathematics, set theory power set question.

Find the power set℘(S) for S={Ø,{Ø},{Ø{Ø}}} Since there are 4 elements would the power be 2^4 which is 16?
1
vote
0answers
43 views

Proving the Divisibility Rule for $3$ [duplicate]

Theorem: If 3 divides the sum of the digits of a number, then 3 divides that number
1
vote
2answers
44 views

How to iterate through all the possibilities in with this quantifier?

This is a problem from Discrete Mathematics and its Applications My question is on 9g. Here is my work so far I am struggling with the exactly one person part. The one person whom everybody loves ...
1
vote
0answers
68 views

Inputs x1, x2, and x3 are all true then output y is true

I'm in online school there's no guidance and I'm just completely unprepared for this. I am to write this as a logical statement using logic symbols for conjunction and implication. Can someone help ...
1
vote
0answers
102 views

What is the counting sequence of a Binary String?

I have a two part question dealing with the binary strings for Discrete Math and I am stuck on the meaning of the very last part. (a) List all binary strings of length 3. Since a binary string is ...
1
vote
2answers
58 views

Converting Decimal to Hexadecimal

MathExchange, I am trying to learn more about computers, and one thing I have opted to teach myself is decimal to binary, and decimal to hex conversion. From the web, I have found tutorials on ...
1
vote
1answer
23 views

Relations - anty symmetric, reflexive and transitive?

So I'm trying to answer this question : Show that if a relation $S= f(x,y)$ that belongs to $N : x$ is the power of $y$ , is a partial order, is it a total relation ? justify. Note: this is a rough ...
1
vote
1answer
36 views
1
vote
1answer
63 views

Check for valid statistics

Alice conducted a voting about N of his opinions. A[i] percent of people voted for opinion number i. This statistics is called valid if sum of all A[i] is equal to 100. Now let us define rounding up ...
1
vote
0answers
36 views

In how many parts an integer N (greater than or equal to 5) should be dissected so that the product of the parts is maximized?

I tried using the AM-GM inequality and all I could arrive at was that the maximum value of product is obtained when all the parts are equal. How do I proceed after that? Any help is appreciated. ...
1
vote
0answers
44 views

partitions of finite set in same-size parts having at most one element in common

Given g ≥ 2, k ≥ 1 and a population of p = kg workers, I'm trying to figure out the longest series of work shifts such that: during each shift, all workers work in k teams of g people; any two ...
1
vote
3answers
73 views

How many strings of length four that have the letter x in them?

We're only considering lowercase letters, repetition is allowed. Number of strings of length $4 = 26^4$ Number of strings of length $4$ other than $x = 25^4$ $26^4-25^4 = 66,351$ strings. This is ...
1
vote
1answer
33 views

number of strings formed of k characters and length n

You have been given a set of characters of size $k$ and you have to make strings of length $n$. How many strings are possible. A constraint is that every character must be used at least once in each ...
1
vote
2answers
38 views

components of a vector

If I have the angle between two vectors and , I have the components (x,y,z) of the first vector ( xi + yj + zk) how can I know the components (x,y,z) of of the second vector ?
1
vote
0answers
24 views

Calculate year for a provided yield

\$146.25 will yeild \$46.25 at 7.5% per annum. How to get the number of years? Answer is 6 but how do you get it? What is the formula?
1
vote
1answer
68 views

Phase trasition of $f(x)$ on random graph $G(n,p(n))$

Random graph $G(n,p(n))$ and graph $H$, which shown below, are given. I'm in need to find $f(x) : f(x) > 0$, such as: if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G ...
1
vote
1answer
19 views

guessing particular solution of a recurrence equation

Please I need help on this recurrence equation .. I have tried googling but couldn't find much on this... The recurrence equation is $a_n - 2a_{n-1} = (n+1) 2^n $ I can find the homogenous ...
1
vote
2answers
25 views

Let $p \in \lbrace2,3,4,…\rbrace$. Suppose that for all $x,y \in \mathbb{Z}$, if $p \mid xy$, then $p \mid x \vee p \mid y$. Show that $p$ is prime.

I'm studying for an upcoming exam and came across this question in my textbook. I'm assuming the easiest way to approach this proof is by contradiction. I don't have much so far, I just suppose that ...
1
vote
1answer
46 views

Divisiblity by prime

Find minimum positive integer pair $(x,y)$ such that $P$ divides $|C^x−D^y|$. Here $P$ is a prime number and $C$ and $D$ are constants which are provided to us. For example, if $P=7$,$C=1$,$D=5$, the ...
1
vote
2answers
58 views

Group action on set

Let $A=\{a,b,c,d\}$ be a set consisting of 4 distinct elements. In this question, a group action $s:\mathbb{Z}_4\to S_A$ is considered. Here $\mathbb{Z} _4=\{0,1,2,3\}$ while the group operation in ...
1
vote
1answer
63 views

Does there exist any other function $xi$ that makes the function $f$ continuous on the set of real number $\mathbb R$?

Let's define $\delta:\mathbb R\to \mathbb R$ as follows: $\forall x\in\mathbb R,$ express $x$ as $x=7k+\delta$ with euclidean algorithm, where $\delta$ is the remainder and $7$ is the divisor. We ...
1
vote
1answer
21 views

Maps and the number of elements in a map

So here's the question: Suppose $f: S \to T$ is a map of sets. a. If T is finite & the map is one-to-one, show that $|S|$ is finite and that $|S| \le |T|$. b. If S is finite & the map is ...
1
vote
0answers
14 views

one to one onto and composition functions [duplicate]

I'm kind of confused about how to prove one to one and onto with functions and composition functions. I am also a visual learner. Could someone tell me step by step how to prove whether or not a ...
1
vote
1answer
70 views

Simplification problem with discrete mathematics

I am trying to achieve this equation: $$x_1x_4 \lor x_1x_2x_3\lor (¬x_1)x_3(¬x_4)$$ I start with: $$(x_1 \lor (¬x_4))(x_3\lor x_4)((¬x_1)\lor x_2\lor x_4)$$ Then I do simplify in the following ...
1
vote
1answer
20 views

Finding the size of an intersection of subsets, given several other sizes

I am having trouble with an old exam question that seems to follow a particular format. Essentially you are given a group of X people, some portion of which fall into one category, another portion of ...
1
vote
1answer
54 views

Discrete Math: Combinatorics and recursion

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
1
vote
1answer
39 views

Sets of irrationals whose square contains a rational

Let $S$ be a subset of the irrationals. Also, lets assume that $S$ has infinitely many elements. My very general question is, under what non-trivial conditions does there exist an element $x\in S$ ...
1
vote
1answer
153 views

Special Binary Relations/ Empty Relation, Universal Relation And identity Relation?

The universal relation U = A × A. (Correct me if I'm Wrong). I believe that the Universal Relation is an Equivalence Relation The empty relation E = ∅. From my understanding, a Empty relation on a non ...
1
vote
1answer
32 views

Power set statement validity

If A is a set and P(A) is the power set of A. Why is the following statement is true: ∃C[(C is a set) ∧ (∀A[A is a set → C ∈ P(A)] )]
1
vote
1answer
43 views

Calculating connected components in an undirected graph

Suppose that we have a graph $G$ with $n$ vertices and $n-k$ edges, such that it does not include any cycles. How many connected components does it have?
1
vote
0answers
33 views

need to know if this is correct [duplicate]

Use strong Principle of induction to prove that the amount of postage greater than or equal to 8cents cents can be made using a combination of 3 cent and 5 cent postage this is what i have so far: ...
1
vote
0answers
20 views

Count the Opposite Technique

Assume repetition is allowed and uppercase, lowercase and 0-9 are allowed, how many 8 char. passwords are possible where at least one 1 char that is uppercase at the beginning OR 1 char is a digit at ...
1
vote
3answers
123 views

Suppose that R and S are reflexive relations on a set A. Show that R-S is irreflexive.

Suppose that R and S are reflexive relations on a set A. Show that R - S is irreflexive, i.e., $$\forall x \in A, (x,x) \notin R\setminus S$$ We have: $$\forall r\in R, (r,r) \in R\\ \forall s\in ...
1
vote
0answers
43 views

Does each element of $D4$ have an inverse in $D4$?

We are just starting the concept of permutations of objects in my class and I'm having trouble to grasp this particular question. I'm assuming it does have an inverse because of all the different ...
1
vote
2answers
38 views

Solve the linear homogeneous recurrence relation with constant coefficients

$$9a_{n} = 6a_{n-1}-a_{n-2}, a_{0}=6, a_{1}=5$$ So $$x^n = (6x^{n-1}-x^{n-2})\div9$$ thus $$[x^2 = (6x-1)\div9] \equiv [x^2 - \frac{2}{3}x + \frac{1}{9} = 0], x=\frac{1}{3}$$ also ...
1
vote
2answers
71 views

Proofs with Relations and functions

I need help with setting up a homework problem. I am having trouble finding where to start. Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation ...
1
vote
1answer
27 views

Solve linear homogeneous recurrence relation?

The relation to solve is this: $$ a_{n} = 7a_{n-1} - 10a_{n-2}, a_{0} = 5, a_{1} = 16$$ So $$ a_{2} = 62, a_{3} = 274, ...$$ So I thought I was supposed to be able to do this to solve: $$ x^n = ...
1
vote
1answer
47 views

No.of faces in Peterson graph

I know that Peterson graph is not planar.But in this graph how can I determine the regions of the faces.How many faces does it include? Two faces can't include a common region right?
1
vote
2answers
26 views

Decide whether the relation is reflexive,symmetric,asymmetric,antisymmetric or transitive

R is the relation on the integers such that a is related to b if a+b is odd. So far I know the relation is transitive because a & c must both be even or odd for the sum of a+b to be odd. How ...
1
vote
0answers
55 views

What is the highest state in the context of finite state automata?

I am doing an assignment for my Theory of Computation course. We are writing a function and I am having a hard time understanding what "highest" state means in the following context: ...
1
vote
1answer
98 views

How many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads?

I am trying to figure out how many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads. I understand how to do the problem with two colors, but I am struggling to ...
1
vote
1answer
56 views

How Many Triangles are Created by n Lines in the Plane?

Suppose we are given n lines in the plane in "general position", which in the present case we define to mean the following: A. no 2 lines are parallel or identical B. no 3 lines have common ...
1
vote
1answer
24 views

How to prove by this type of question by Induction (If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m \geq 1$, then $a_n = 2^n + 3n + 1$)

Please do not tell me how to prove this exact question. I would like to know how to go about proving the following type of question by induction: If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m ...
1
vote
0answers
110 views

Predicate Logic and Negation Assistance

I just want to make sure I'm on the right path with these: Using the predicate symbols shown and appropriate quantifiers, write each English language statement in predicate logic. (The domain is ...