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

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
1
vote
0answers
29 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
4
votes
1answer
318 views

Is there a way to find expected value of equation?

If the random variable $X$ is binomially distributed with parameters $n=6$ and $p=0.3$, what is $$E(4+3X^2)$$ I know $E(X) = np = 1.8$. I solved this problem by finding $P(X)$ of all $X$ using ...
0
votes
1answer
34 views

Is the relation $xRy$ iff $|x - y| \leq 2$ transitive?

Question: $xRy$ iff $|x-y| \leq 2$ I think I've found this to be reflexive and symmetric, but I'm stuck on transitivity. Can someone assist me with testing transitivity?
1
vote
2answers
37 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
-2
votes
0answers
17 views

probablitly using bayes theroem

Three numbered urns contain colored balls as described in the table below. One of the urns is picked at random and a ball is drawn from the urn; the ball is red. What is the probability the ball can ...
0
votes
1answer
14 views

Prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$

I'm asked to prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$ I know that for Big O, I need to show: $f(n) <= c*g(n)$ But I'm not sure how to show this, since it involves theta. Any help would ...
-1
votes
0answers
43 views

Closed form for $\left(\sum_{k=0}^n\frac{x^k}{k!}\right)^p$

The expression for the p-th power of the sum of the first $n+1$ powers of x is given analytically by ...
0
votes
2answers
53 views

Prove for all integers n such that n ≥ 3, $ 4^3 + 4^4 + 4^5 … 4^n = \frac{4(4^n - 16)}{3}$

I am trying to prove this using mathematical induction, but I'm lost once I get to comparing the two sides of the equation. Proposition: For all integers n such that n ≥ 3, $ 4^3 + 4^4 + 4^5 … ...
2
votes
1answer
49 views

Converting programming logic to mathematical notation

How do I go about converting programming logic to mathematic notation? For example, I read a question that asks: ...
2
votes
2answers
36 views

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be ...
0
votes
2answers
27 views

How to make this inclusion-exclusion argument

I'm asked to count the number of functions $f:\{1,2,3,4\} \rightarrow\{1,2,3,4,5\}$ such that $f(1)∉\{f(2),f(3),f(4)\}, f(2)\neq f(3), f(3) \neq f(4)$. How do I make the inclusion-exclusion argument ...
0
votes
1answer
12 views

Simplifying DNF conversion?

Context: I have a huge circuit with lots of input bits (around 300). Among these, only about 40 are free, the others are fixed by the current state. I have to find all satisfying assignments knowing ...
0
votes
1answer
53 views

Null Bilinear Forms $x^T A y = 0$, where $A$ is square and full rank.

Let A be a full rank square matrix (A has no null space). When does $y^T A x = 0$ occur ? It could be that this problem is case-specific, so please find attached a document where x,y, and A take ...
0
votes
3answers
47 views

How did $-(2^{k-1})-(2^{k-2}) -\dotsb-(2^0)$ become $-2^k+1$?

I have a question, how was the geometric series collapsed to be in the form of $2^{k+1}$?
0
votes
2answers
21 views

Can I do universal instantiation on this predicate?

Can I do universal instantiation on the following predicate : $ \forall x\;S(x)\; \lor\; \forall x\;L(x)$ become $S(c)\lor L(c)$ or is it has to be $\forall x\; ((S(x) \lor L(x))$ to be able to do ...
1
vote
1answer
30 views

Sum of Reciprocals

I wonder if someone help me with this: I have $\pi_1+\pi_2+ \pi_3 +\pi_4=A$ and $\pi_1\pi_2\pi_3\pi_4=B$ where $\pi_i \;\forall i=1,2,3,4$ are unknown but $A,B$ are known numbers. Can I find for ...
0
votes
1answer
24 views

Am I showing relations correctly using subsets?

The question is: Let $S = \left\{a,b,c\right\}$. Recall that a relation on $S$ is a subset of $S\times S$. Give an example of a relation $R$ on $S$ that is reflexive and: a. Symmetric but not ...
0
votes
1answer
21 views

finding a DNF with an expression that contains quantifiers

I am supposed to use equivalencies to find the prenex DNF for the wff: $\exists xp(x) \land \exists xq(x) \rightarrow \exists x(p(x) \land q(x))$ It's been awhile since I've done something like this ...
-1
votes
3answers
57 views

Showing $k^2 + m^2$ is odd when $k$ is odd and $m$ is even [on hold]

Prove that if $k$ is any odd integer and $m$ is any even integer, then, $k^2 + m^2$ is odd.
0
votes
1answer
17 views

How do I express these relations using subsets? [on hold]

Let S = {a,b,c}. Recall that a relation on S is a subset of S×S. Give an example of a relation R on S that is reflexive and: a. Symmetric but not anti-symmetric. b. Anti-symmetric but not symmetric. ...
0
votes
1answer
33 views

Am I doing this relations question correctly?

Let S = {a,b,c}. Recall that a relation on S is a subset of S×S. Give an example of a relation R on S that is reflexive and: a. Symmetric but not anti-symmetric. b. Anti-symmetric but not ...
0
votes
2answers
22 views

(P and(not(not P or Q))) or( P and Q) equals P

I've been trying to verify the condition above but I get stuck on the passage : $$(P \land (P \land \lnot Q)) \lor (P \land Q)$$ I don't know how to simplify it since there are two ands and a not Q. ...
0
votes
1answer
22 views

Prove a relation is transitive

I've stumbled upon this question in my discrete math book: Prove $$ R = \{(x,y) \in N \times N \ | \ 2x \mid y^2 \} $$ is transitive. I tried thinking about it having to do something with division ...
0
votes
2answers
43 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
1answer
36 views

Prove that $|A| \geq |B|$ implies $|B| \leq |A|$ [duplicate]

If $|A| \geq |B|$, then there exists an onto function $f: A \rightarrow B$. If $|B| \leq |A|$, then there exists a one-to-one function $f: B \rightarrow A$. My issue is that I don't think that $|A| ...
0
votes
0answers
12 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
1answer
24 views

Proof of equivalence theorem using equational calculus

I have to show the following theorem: $p\vee \neg p \equiv ((p \vee q)\wedge \neg (\neg p \wedge (\neg q \vee \neg r)))\vee (\neg p \wedge \neg q) \vee (\neg p \wedge\neg r)$ I have proved $((p ...
0
votes
0answers
14 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
4answers
55 views

Prove that if $n$ is odd, then $-n$ is odd.

Here is my work so far, I am missing something quite obvious but I can't seem to link it together: Proof. Let $n$ be an integer. Suppose $n$ is odd. This means that there is an integer $k$ such that ...
-3
votes
0answers
38 views

Find all cases in which $A \times A$ contains the same number of elements as a given finite set $A$. [closed]

I am doing this for my discrete math class, could you guys explain to me how to to this? Find all cases in which $A \times A$ contains the same number of elements as a given finite set $A$.
0
votes
0answers
24 views

Decode the text using a 3×3 Hill Cipher [closed]

Decode the text using a 3×3 Hill Cipher NKVCHDGPVZYKHYESCHUWOTRUNKUEXFQDHVJMGIVHNCUYGYKJNXNGWLOKVJRUDYYBGNYCZVHYRFZFDBCSCPFGOTBDLDKOM Given Plaintext - 'theintern' How do I decrypt ?
0
votes
1answer
33 views

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$, ($n ≥ 1$).Prove that if $c$ is any integer such that gcd$(b,c) = 1$ then there is some element of the ...
0
votes
0answers
33 views

Consider the sequence of positive integers An, for n ≥ 1, defined by $A_n = 10^{2^n} + 1$.

Consider the sequence of positive integers $A_n$, for $n \geq1$, defined by $A_n = 10^{2^n} + 1$. 1) Prove that the elements of this sequence are pairwise coprime, i.e. prove that if $m \neq n$ then ...
0
votes
0answers
21 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
2answers
30 views

Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent.

I am new in Discrete Math so that I am still not familiar with Logical Equivalent rules. 1) Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent. My Try: ¬p ∨ (r →¬q) $\equiv$ ¬p ∨ (¬r∨ q) ...
1
vote
2answers
53 views

What is the remainder produced when the integer 2099^(2017^13164589) is divided by $99$? [closed]

I'am looking for the remainder produced when the integer $2099^{2017^{13164589}}$ is divided by $99$ ? The goal reached is to avoid large integers.
2
votes
1answer
12 views

Nested Quantification of exactly one.

Suppose my domain is "All students in the class" and P(x, y):= x has emailed y. So, how do i define: Every student has emailed exactly one student. Exactly one student has emailed every one. A ...
2
votes
3answers
48 views

Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times.

So I was given this question. Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times. First I make $x_1 + x_2 + x_3 = 20$ Then $ 0 \leq x_i ...
0
votes
2answers
54 views

Big-Oh Analysis of For Loop

I have the following for loop: sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++ What is the strategy to determine ...
0
votes
2answers
28 views

Floor and ceiling opposite property

For $x\in \mathbb{R}$ let's define $[x]$ as: $$ [x] = max \{ k\in \mathbb{Z}: k\leq x \} $$ and $[x]^{*}$ as: $$ [x]^{*} = min \{ k\in \mathbb{Z}: k\geq x \}. $$ Show that: $$ [x]^{*} = -[-x]. $$ So ...
1
vote
2answers
29 views

Is the relation $P$, for all real numbers $x$ and $y$ that satisfy $xPy $ iff $x^3 - y \ge y^3 - x$, a reflexive, symmetric and transitive relation?

Image of an exam question I am revising link: [1] For (i) I have stated the relation is reflexive as $\forall x ∈ \Bbb R, xPx$ is reflexive as $x^3 \ge x $ For (ii) I have stated that the relation ...
1
vote
0answers
17 views

What are the different ways of performing Triangular matrix-vector multiplication?

Suppose we have $$\left[\begin{array}{cccc} x_1 & 0 & 0 & 0 \\ x_2 & x_1 & 0 & 0 \\ x_3 & x_2 & x_1 & 0 \\ x_4 & x_3 & x_2 & x_1 \end{array}\right] ...
-4
votes
2answers
30 views

How Should I prove the relation between these sets? [closed]

If $A_1$ and $A_2$ are any two sets, show that there always exists $B_1$ and $B_2$ which can be made by $A_1$ and $A_2$, where $A_1 \cup A_2 = B_1 \cup B_2$ and $B_1 \cap B_2 = \emptyset$.
-2
votes
0answers
27 views

How to calculate distance between two or more vector with Euclidean Distance [closed]

I know how to get distance between 2 vector (1 vector may have several points), however I want to get distance between 2 vectors where each object has several points. (See illustration on link below.) ...
0
votes
1answer
36 views

Discrete math: Simplified the following english sentence?

Simplified the following english sentence? It is not the case that overnight lows are not in the 60s or the furnace is running. What I tried is ignore the exactly meaning in the real life. So I took ...
0
votes
0answers
25 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
0
votes
1answer
33 views

combinatorial Proof

I need to check if the following is true for all $k$. Can anyone help me? $$k{n\choose r} ={kn\choose kr} $$ I know that using the formula, I will obtain: $$ k\left(\frac{n!}{r!(n-k)!}\right) = ...
1
vote
2answers
29 views

Deductive Proof - Justify each step with law or inference rule

My Professor gave me the following: a) If $P \to Q, \neg R \to \neg Q$, and $P$ then prove $R$. b) If $P \to (Q\wedge R)$ and $\neg R\wedge Q$ then prove $\neg P$. I understand how to do ...
0
votes
2answers
19 views

$A = \{{1, … , n\}}$ - How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$?

$A = \{{1, ... , n\}}$ How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$ ? I got to the conclusion that it must be $\sum\limits_{k=0}^{n}2^k$ because for ...