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

0
votes
1answer
19 views

How to find the order of G using the size of G and its complement

If the size of graph G is 19 and the size of its complement G-bar is 17 then find the order of G?
0
votes
1answer
51 views

Proving these are logically equivalent?

How to prove that these are logically equivalent using laws? a. $p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)$ I used the Conditional law and DeMorgan's Law and eventually arrived at $-(p ∨ q) ∧ -(p ∨ q)$ but ...
0
votes
0answers
38 views

Edge and vertex connectivity of bipartite graph

Let graph $G=(V,E)$ be bipartite graph with partite sets $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$. Vertices $x_i$ and $y_j$ are connected with edge if and only if $i \neq j$. What ...
3
votes
2answers
31 views

How to simplify expression with Fibonacci numbers

I have to simplify the expression $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n}$. I only noticed that $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n} = \sum_{n=0}^\infty ...
0
votes
1answer
39 views

Proof by Contradiction to show that if $f^{-1}$ exists, $f$ must be onto

Use proof by contradiction to prove that if $f^{-1}$ exists, then $f$ must be onto where $f:A→B$. Proof: I think the contradiction of the theorem would be: if $f$ exists then $f^{-1}$ must be ...
1
vote
2answers
63 views

Showing $(f^{-1}∘g^{-1})=(g∘f)^{-1}$

If the functions $f$ and $g$ are both bijections then the in inverse of the composition function $(f∘g)$ will exist. Show that it will be $(f^{-1}∘g^{-1})=(g∘f)^{-1}$ For the proof assume ...
0
votes
1answer
17 views

Does a statement have to be true for all conditions to be transitive,symetric,reflexive?

I'm trying to determine if the following are symmetric, reflexive, transitive, equivalence for all-natural numbers but am struggling because they aren't in set notation. Examples of confusing ...
0
votes
2answers
36 views

How to find the actual doubling time with the rule of 72.

I have a programming assignment in C# from my professor that involves the Rule of 72. He clearly says that in order to find the amount of time in years it will take for an amount to double, you have ...
4
votes
1answer
100 views

In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
0
votes
1answer
25 views

What separates an axiom from a proposition?

I have read that an axiom is defined as "an obvious truth." I have also heard that an axiom is a truth so obvious that no proof could make it more clear. My question is: why is one thing considered an ...
1
vote
3answers
236 views

Solving this recursive relation

I want to solve this recursive relation: $$i_{n+1}=4i_{n}+9$$ where the $i_1=t$ that $t \in \mathbb{N}$ I tried to make like relation about Tower of Hanoi, but no good thing happened. How can I do ...
1
vote
0answers
21 views

Does bitwise-XORing substrings results in a uniform distribution?

Let's say I have an integer $k$ whose bit string representation can be exactly divided into $l$ substrings of length $\log_2(m)$. Let's call each one of these substrings $B_i(k)$, for ...
0
votes
1answer
22 views

Summation simplification explanation

I'm trying to understand summation for my algorithm course and it has been a while since I took discrete math. Could any body please explain how does summation simplification work from the problem ...
1
vote
2answers
34 views

Equivelence classes, how many there are, and how many elements they have.

I've been struggling to understand equivalence classes. Say I have a set T, the set of all binary strings, and the relation S on T = {(a,b) | length(a) = length(b)}. How would I write down the ...
0
votes
1answer
24 views

What is the Largest Input Size? [closed]

Suppose a machine on average takes $10^8$ seconds to execute a single algorithm step. What is the largest input size for which the machine will execute the algorithm in two seconds assuming the number ...
1
vote
2answers
46 views

Generating function for a sequence

Please provide a clue on how to solve the following problem: Find a closed form for the generating function for the sequence $\{a_n\}$, where $a_n = 1/(n+1)!$ for $n=0,1,2...$ I know this looks like ...
0
votes
4answers
118 views

If a function maps A to its PowerSet, is it Surjective?

Given an arbitrary set A, let F : A → 2^A be the function defined for all a ∈ A by f(a) = {a} If A maps to its power set, does this make F surjective? If somebody could help to prove this that ...
1
vote
0answers
23 views

The relationship between an equivalence relation, equivalence classes, and partitions?

So I'm struggling right now to understand the concepts behind equivalence relations, equivalence classes, and partitions. This is what I understand about all these topics right now: Equivalence ...
1
vote
2answers
21 views

Antisymmetric Relation: How can I use the formal definition?

So I can determine whether a certain relation is antisymmetric, by using a digraph. My understanding through a digraph is that if there is only 1 way streets and/or loops between edges, it's ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
0answers
44 views

Prove that every connected graph whose vertices are all of even degree has no cut-vertices

I am trying to prove that every connected graph whose vertices are all of even degree has no cut-vertices. Now, I am not very good with proofs but I was thinking about proving it by contradiction, ...
0
votes
1answer
30 views

join-semilattice vs Upper-semilattice ?! definition problem ?!

In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. I ran into some definition challenge. I ...
-1
votes
0answers
20 views

Meaning of Square and cube of matrix of relation

Let a stand for the airport in the city of Manchester, let b stand for the airport in Boston, c stand for the Chicago airport, d for the airport in the city of Denver. $M_R$ =$\matrix{&a & b ...
0
votes
1answer
30 views

Given the following, is there equivalence relation?

Let $n$ be an integer. On the set $F$ of all integer-valued functions of a set $A$, suppose we define $f$ and $g$ to be related if $f(a)\equiv g(a)\pmod{n}$ for every $a\in A$. Is this an equivalence ...
0
votes
1answer
21 views

Complementary Relation Proof

If $R$ is reflexive, prove that $R^c$ is irreflexive. If $R$ is asymmetric, prove that $R^c$ is reflexive. Where $R^c$ = complement of $R$. I just can't figure out anything to say for the first one ...
2
votes
3answers
55 views

Power set of a subset

Proof that if $A \subseteq B$, then ${\mathscr P}(A) \subseteq {\mathscr P}(B)$. I tried using the definition of a subset: $A \subseteq B = \forall x(x \in A \to x \in B)$, but get stuck as to how to ...
1
vote
3answers
74 views

Why is $f(n)=n^2+3$, where $f\colon\mathbb{N}\to\mathbb{Z}$, not an onto function?

Question: $f_2 :\mathbb{N} \to \mathbb{Z}, f_2(n)=n^2 +3$ Using algebra, making $y=f(n)$, isolating for $n$ and plugging in the expression back, I get $n$. However, the answer key says it is not ...
0
votes
0answers
21 views

Help Representing Equivalence Classes

In the set $\mathbb{Z}$, we define two integers $x$ and $y$ to be equivalent ($x ≈ y$) if and only if $x \operatorname{div} 10 = y \operatorname{div}10$. How would one select a representative from ...
0
votes
1answer
31 views

Axiom of Induction Question

I have to use the axiom of induction to prove the summation of k^3 from 0 to n is $(n(n+1)/2)^2$. Here's what I have so far: Let P(n) be the assertion that $0^3+1^3+⋯+n^3=(n(n+1)/2)^2$ Base Case ...
0
votes
1answer
29 views

Quick Recurrences Question [closed]

$$given: T(n)=4T(n/2)+n^2 ;T(1)=1\\=4[4T(n/2^2 )+(n/2)^2 ]+n^2\\=4^2 [4T(n/2^2 )+(n/2)^2 ]+n^2+n^2\\=4^3 [4T(n/2^3 )+(n/2)^2 ]+n^2/4+n^2+n^2\\…\\=4^k T(n/2^k )+$$ Here is where I'm stuck because I'm ...
0
votes
1answer
25 views

Greatest Common Divisor Euclid's Algorithm

Find GCD of $28844$ and $-15712$. Find integers $a$ and $b$ such that $d= 28844a - 15712b$. My attempt $$\begin{align*} 28844&= -15712(-2) + (-2580)\\ -15712 &= -2580 (6) + (-232)\\ -2580 ...
0
votes
0answers
33 views

Question about Recurrences

$$given: T(n)=T(n-1)+n^3 ; ...
1
vote
4answers
41 views

Functions: If $f(g(x))$ is onto, does this mean $g(x)$ is onto

Question: Let $g:A \to B$ and $f:B \to C$ be two functions. If $f$ and $f \circ g$ are onto, is $g$ necessarily onto? I know it's not, but I don't understand why/don't know how to explain it.
0
votes
0answers
7 views

How many valid input output combinations exist.

How many valid input/output combinations exist for a switch with X inputs and Y outputs. Each input can be bound to more than one output. Each output can be bound to only one input.
3
votes
1answer
38 views

How can I calculate Index of Coincidence of Vigenère cipher?

I have computed the letter frequency of the cipher text. However, I don't know how to apply Friedman Test to Vigenère cipher. I couldn't calculate the Index of Coincidence. Does anyone can help to me ...
3
votes
1answer
72 views

The Ackermann's function “grows faster” than any primitive recursive function

I am looking at the proof that the Ackermann's function is not primitive recursive. At the part: "We will prove that Ackermann's function is not primitive recursive by showing that it "grows ...
-4
votes
1answer
52 views

How to figure out how many entries are in a relation

I have the domain $A = \{1, 2, \ldots , 1000\}$. I need to figure out how many non zero entries are in each relation: a. $R_1 = \{\;(a, b) \;|\; a \le b\;\}$ b. $R_2 = \{\;(a, b) \;|\; a + b = ...
4
votes
9answers
200 views

Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is ...
0
votes
0answers
24 views

Recursive formula for the number of $n$-permutations with $k$ cycles

Let $n$ and $k$ be a positive integers satisfying $n\geq k$, then $$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$$ where $c(n,k)$ denotes the number of $n$-permutations with $k$ cycles. The proof of this ...
3
votes
1answer
56 views

Find integer $n$ that satisfies $(\lg n)^{2^{100}} <\sqrt{n}$ with $n > 2$

If $(\lg n)^{2^{100}} < {n^{1/2}}$, where $\lg$ is the binary logarithm, then $$(\lg n)^{2^{101}} < n$$ $$2^{101}\lg \lg n < \lg n$$ $$101 < \lg \lg n - \lg \lg \lg n$$ I don't know that ...
0
votes
4answers
24 views

Defining a relation that is antisymmetric, but not symmetric?

Say I have a set = {1,2,3}. I am trying to think about how I could define a set on X which is antisymmetric but not symmetric. At first I had thought the set would be Z = {(1,1),(2,2),(3,3)} but am ...
0
votes
1answer
21 views

Question on counting functions satisfying a relation

I have been assigned the following problem: Let A = {1, 2, 3, 4} and let F be the set of all functions from A to A. Let R be the relation defined by: For all $f, g \in F$, $(f,g)\in R$ ...
1
vote
2answers
108 views

Number of elements in an equivalence class

Let a set X = {1, 2, 3, 4, ... , 2015} and a set Y = {1, 2, 3, 4, ... , 271}. Let S be the relation on P(X) defined by: For all sets A, B, that are elements of P(X), (A,B) are elements of S if and ...
0
votes
0answers
23 views

Define the concept of square root (mod n)

So i was looking at some of the past papers of my module, the new module has different topics slightly.I was wondering how would you solve this since we didn't cover such topic this year Define the ...
0
votes
0answers
88 views

Find 3 integers x so that 271x ≡ 272 (2015)

Now I found the gcd(2015,271) = 1 when (2015)(-62) + (271)(461) For my first integer, I tried doing this -> x ≡ 272 * 461 (mod 2015), and 2015| x + 125392, then I get x = 127407 And then x ≡ ...
1
vote
2answers
23 views

Probability that 3 randomly selected elements of a set are equal check

I have the following question: Let A = {1, 2, 3, . . . , 100}. Let x, y, and z be elements in A that are chosen independently and uniformly at random. What is the probability that x = y = z? Because ...
1
vote
2answers
28 views

Proving isomorphism between graphs

If I'm asked to prove two graphs are isomorphic by constructing an isomorphism E.g for these two graphs if I start from $u_1$ I have an option to send $u_1$ to any of $v_1$ to $v_6$ and I start by ...
0
votes
2answers
18 views

Simple lemma about permutations

While doing some recalling about permutations I've crossed with the following simple lemma: Let $g:[n]\to [n]$ be a permutation. Let $x\in [n]$, and there exist $1\leq i\leq n$ so that $g^i(x)=x$. ...
1
vote
0answers
39 views

Sum of number of rows with max value

Suppose i have an N by N matrix, each element in the matrix my contains 0 or 1, so there are 2^(N*N) different matrix. Let's define the function F that takes a matrix and calculate the sum for each ...
0
votes
2answers
21 views

Proving the summation of a function as big theta of another function

Show that $\sum^n_i i^4\log^2i$ = $\Theta(n^5\log^2n)$ I am completely lost on how to solve this problem. I understand that $\Theta$ deals with the upper and lower bounds, so do we prove both big-oh ...