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
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
20 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
2answers
46 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
28 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
34 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
27 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 ...
1
vote
1answer
47 views

Proof by cases: Prove that if $x$ and $y$ belong to the set of real numbers, then $\max(x, y) + \min(x, y) = x + y$

Question: Let $x$ and $y$ be real numbers. Using a proof by cases, show that $$\max(x, y) + \min(x, y) = x + y.$$ So for this question, I'm not sure how you would apply proof by cases. I think that ...
0
votes
1answer
14 views

A graph that all its vertices are vertices cut [duplicate]

Is there any graph that all its vertices are cut vertices? I couldn't find a graph with this property? and if there is no such graph how can i prove that it does not exist.
2
votes
1answer
93 views

Variation of Tower of Hanoi

I have been reviewing the solution of the following problem for which I have to find a recurrence relation for the number of moves: "In the Tower of Hanoi puzzle, suppose our goal is to transfer all ...
3
votes
3answers
115 views

Prove that $14322\mid n^{31} - n$

Im trying to prove that $ 14322 \mid n^{31} - n $, $ \forall n \in \mathbb{Z}$ My thought was to rewrite $n^{31} - n$ which a got to $$ 2(n-1)\sum_{i=0}^{n} i \sum_{k=0}^{14} n^k \sum_{j=0}^{14} ...
-2
votes
0answers
19 views

Finding maximally weighted subgraph triangles from a complete graph.

In a Complete Graph of say, $|V| = 12$, where the edges are all weighted, how can you select $4$ triangles of $3$ vertices and $3$ edges (disjoint subgraphs), such that the triangles are maximally ...
1
vote
0answers
12 views

Brooks' theorem and greedy algorithm-vertex colouring

For this question in the answer that is attached below, for the last row in the blue table, for v1 in the set of adjacent colours, they have (2,3,4) but v1 is adjacent to v2,v6,v7 and v3 so ...
0
votes
0answers
33 views

how can i find a grammar for this language?

The language is $L = \{a^i b^j c^k | k = (i + j)^2, i > 0, j > 0\}$. To produce a's and b's I have this solution: S -> aS | aB B -> bB | bC but for producing the right number of c's i have no ...
0
votes
0answers
32 views

Making up Quadratic formulas (parabola)

I've to make up 2 quadratic formulas (parabola) and I don't get it how I've to do that. The data of these two quadratic formulas is as followed: I wanna get something like this: $$y=ax^2+bx+c$$ ...
3
votes
3answers
37 views

Find point of passing of two racers. [closed]

Two contestants run a 3-kilometre race along a circular course of length 300 metres. If their speeds are in the ratio 4:3, how often and where would the winner pass the other? (The initial start-off ...
1
vote
4answers
171 views

Is this relation transitive, reflexive, symmetric?

I am having a hard time identifying transitive relations. I think I understand those that are symmetric, but do correct me if I'm wrong. For a set $S = \{0,1,2,3,4\}$ and a relation $Z = ...
0
votes
1answer
44 views

How can I calculate $d$ from this equation?

So how can I calculate $d$ from this equation : $17^d \mod 55 = 8 $ ? I am solving an RSA Encryption question and im confused on how the modula is formulated when transferring to the other side, and ...
0
votes
0answers
19 views

How to solve this linear recursive sequence in a closed form function?

How would I solve this linear recursive sequence and write it as a closed-form function? R0 = 11 R1 = 266 Rn = -5Rn-1 + 6Rn-2 I worked out that R2 = -64 and R3 = 476 but I'm unsure how to use ...
-5
votes
2answers
50 views

How to formally prove: if d|(da+b), then d|b?

How would I formally prove that for the integers a, b, and d If d|(da+b), then d|b. Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty quickly... in fact I ...
-1
votes
1answer
38 views

Confused on the Euclidean formula yet AGAIN

I'm confused on what the formula is to get $s_2$ as well as $t_2$ as well as $s_3$ and $t_3$ ... I can't seem to crack it no matter how hard I try.By the way $s_0 = 1$
0
votes
1answer
33 views

Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$.

Here's the problem: Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$. Where I Am: I assume that I should induct on $n$ and come to the ...
0
votes
2answers
30 views

Let $m,n \in \mathbb N^+$. Define an explicit bijection from the Cartesian product $\lceil m \rceil \times \lceil n \rceil$ to $\lceil mn \rceil$.

Here's the problem: Let $m,n \in \mathbb N^+$. Define an explicit bijection from the Cartesian product $\lceil m \rceil \times \lceil n \rceil$ to $\lceil mn \rceil$. My Progress: Obviously, I'm ...
1
vote
0answers
47 views

Solving the GCD m = 735, n =252

I understand everything except the values in $s_i$ and $t_i$ how do we get those values??? Can anyone please elaborate. I have no idea what the formula is for calculating the values in $s_i$ and ...
2
votes
3answers
38 views

Calculate number of (four-letter) strings that contain exactly two matching characters (s)

The following problem refers to strings in A, B, ..., Z. Question: How many four-letter strings are there that contain exactly two S's? I used the formula in this answer to come up with the ...
0
votes
2answers
33 views

How can we prove by induction the relation $P(x,y)$?

How can we prove by induction the relation $A(x,y)>y, \forall x,y$, where A(x,y) is the Ackermann function? When we have to prove a relation $P(n), n\geq 0$, we do the following steps: we ...
1
vote
1answer
42 views

Prove that S is an equivalence relation on P(X)

Let $X = \{ 1, 2, 3, \ldots , 2015\}$ and $Y = \{ 1, 2, 3,\ldots, 271 \}$. Let S be the relation on power set (X) defined by For all A, B in $\mathcal{P} (X)$, $(A, B) \in S$ if and only if $|A \cap ...
0
votes
0answers
15 views

Proof solutions linear congruence

If $x_0$ is the solution of the system of linear congruence equations: $$ x \equiv c_1 \text{ mod } m_1$$ $$ x \equiv c_2 \text{ mod } m_2$$ $$ \cdots $$ $$ x \equiv c_s \text{ mod } m_s$$ AND the ...
-3
votes
3answers
143 views

$1+1=0$ What am I doing wrong???! [duplicate]

Does someone know what I'm doing wrong? I'm struggling with this for a while now and I don't see what I do wrong! $$1+1=$$ $$1+\sqrt{1}=$$ $$1+\sqrt{-1*-1}=$$ $$1+\sqrt{-1}*\sqrt{-1}=$$ $$1+i*i=$$ ...
0
votes
0answers
42 views

Counting all permutations(repeating) with no adjacent elements equal and m majority elements.

Counting all permutations(repeating) of 1 to n which have size n. 1. with no adjacent elements equal, and 2. m majority elements(A element is majority element when it appears max number of times in ...