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
0answers
45 views

Discrete math equivalence relations [duplicate]

(a) Let A be a non-empty set, and ρ an equivalence relation on A. Let a, b ∈ A. Prove that[a]=[b] ⇐⇒ aρb. (b) If ρ is both an equivalence relation and (simultaneously) a partial order on A, describe ...
0
votes
1answer
8 views

Estimating the $\beta$th moment of a uniform random variable

Let $n$ be a positive integer, $\beta > 1$, and let $X$ be a random variable uniformly distributed over $\{0, \ldots , n -1\}$. Show that $\mathbb{E}[X^\beta] \leq n^\beta / (\beta + 1)$. I don't ...
1
vote
1answer
122 views

Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to apb

the question: a) Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to $apb$ b) If p is both an equivalence relation ...
0
votes
1answer
46 views

If a|b and b|a, find the value of a in terms of b.

If a|b and b|a, where a and b are integers and a≠0, find the value of a in terms of b. Assume that b>0.
1
vote
2answers
227 views

O(n) algorithm for minimizing Manhattan distance between points

Given two sets points with each point either "Black" or "White", design an algorithm to find the pair of points, one that is black and another that is white, such that the Manhattan distance between ...
1
vote
1answer
89 views

Using recursion tree to solve recurrence $T(n) = 3T(n/2)+n$

I am trying to solve the recurrence $T(n) = 3T(n/2)+n$ where $T(1) = 1$ and show its time complexity. $n$ can be assumed to be a power of $2$. So basically, I drew out the tree and found that: ...
1
vote
3answers
67 views

n! v.s. $a^{n}$ How can we know which one is faster without graphing?

n! v.s. $a^{n}$ If we are given an arbitrary number a (a>1). How can we know which one is faster as n->INFINITY without graphing?
1
vote
0answers
52 views

Big O-notation proof: show that $x^{2}+5x+11$ is $O(x^{3})$

Show that $x^{2}+5x+11$ is $O(x^{3})$ by providing the smallest value of the witness $C$ such that $|f(x)|≤C|g(x)|$ whenever $x>11$. What's the value of $C$?
3
votes
2answers
415 views

How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01?

I thought there were n-1 places between the first and last digit. In these places I hypothesized there are switches that change (from 0->1 or 1->0) For ...
0
votes
1answer
34 views

Transitive Relations on a set

I am trying to study binary relations (for myself, it's not an assignment!) I have the set $\{1,2,3,4\}$, and one of the relations in the exercise is $\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)\}$. A ...
1
vote
2answers
65 views

Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n, a_1=1, a_2=11.$

First I solved $a_n=4a_{n-1} -3a_{n-2}$: $$x^2-4x+3=0\Rightarrow (x-3)(x-1)=0\Rightarrow a_n=k_1(1)^n +k_2(3^n)=k_1+k_2(3^n)$$ The problem is, I have no idea how to handle that part which has made ...
0
votes
1answer
37 views

Inductive proof on r

Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for: $$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$ Step 1: We will prove this using induction on n. n = 1 Step 2: n = k, prove for n = ...
0
votes
1answer
44 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
0
votes
1answer
61 views

Induction proof divisible by 5

Prove that for all n ∈ N, prove that $ 3^{3n+1} + 2^{n+1} $ is divisible by 5. So far what I've gotten is: Step 1: We will prove this by using induction on n. Assume the claim is true when n = k. ...
1
vote
3answers
47 views

Discrete Mathematics Symmetric Diffirence Proof [duplicate]

I've been trying to find a proof for the following problem but have been unable to come up with anything myself: Say we have A, B, C part of a universe U show that if $$A \Delta C = B \Delta C ...
1
vote
1answer
40 views

Recursion and Counting

If $2$ numbers $n$ and $m$ are given, how can be found out the number of numbers with zero between and including $m$ and $n$ ($m \leq n$)?. For example, if $m=10$, $n=100$ the numbers with zeroes are ...
2
votes
0answers
11 views

Looking for a generalised or non-iterative maths equation for the process of slicing up a range value

Suppose I have a integer range $[0,n]$ and an integer $x$ within that range. Suppose I can generate an integer $y$ though this iterative process: $x$ is converted to Base 2 For each bit from most ...
1
vote
2answers
163 views

Discrete Mathematics Riddle, square grid problem

I've been trying to solve this problem in my book to no avail: I am even stuck on part a... to find a closed form of this I started with size 2x2 square, counted the number of paths, then used a ...
0
votes
1answer
108 views

Proving $\sum^n(1/i^2)\le2$ by induction

I am having difficulty proving this from a practice problem in my book with no solutions: For part a, I set up the inductive hypothesis then I am stuck with the Riemann sum of 1/k^2 + 1/(k+1)^2 ...
0
votes
1answer
30 views

Calculating number of students who don't study any language

According to a survey of 100 students, there are 40 students studying English, 30 studying French, and 25 studying Spanish. Inaddition, 8 students are studying English and French, 6 are ...
0
votes
1answer
38 views

Distributing Apples and oranges. confused about solution

How many ways are there to distribute 4 identical oranges and 6 distinct apples into 5 distinct boxes I know you find number of ways for apples which is 5^6. The solution tells me that the ways for ...
1
vote
1answer
83 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
0
votes
0answers
48 views

Predicate with Non-Number Domain

I am having difficulties defining a predicate, given the following domain and requirement: Let x and y be two parameters whose domains Dx and Dy, respectively, are the set ...
0
votes
1answer
34 views

Probability - Random viarbles

A notepad manufacturer requires that 90% of the production is of sufficient quality. To check this, 12 computers are chosen at random every day and tested thoroughly. The day's production is deemed ...
-1
votes
1answer
34 views

does an explicit formula for GCD exist?

i was trying to put GCD(a,b) into the form of f(a,b) = a +5b. i know the euclidean algorithm finds the GCD, so I was trying to put that concept into a recursive formula but its getting way too ...
1
vote
3answers
86 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
1
vote
2answers
51 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
1
vote
1answer
29 views

Strange Absorption Behavior in Discrete Math

I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example: ...
1
vote
1answer
48 views

How does one find/list equivalence classes?

Can someone explain how I would find/list the equivalence classes (And number of equivalence classes) of these two examples? Example 1: A is the set of all possible strings of 3 or 4 letters in ...
1
vote
1answer
48 views

Probability involing percentages (Bernoulli?)

Assume that about 56% of population belong to group type of O. A) What is the probability that it will need to take a blood test from exactly three individuals in order to find a person with O-type ...
1
vote
2answers
47 views

How to formalize proofs

I'm struggling a bit with my discrete maths course and I was wondering if anyone could help me with my assignment. The question I'm working on is, Prove that if a and b are positive integers, then ...
0
votes
1answer
75 views

How would I draw the diagram for this relation?

The question I am trying to solve is below. I have proven it is an order but am unsure how to draw the diagram for it. Can someone point me in the right direction? Let A = {1, 2, 3, 4}, and let R be ...
0
votes
1answer
33 views

How to prove this equivalence relation?

How would one go about proving this is an equivalence relation? I have no idea where to start. $\cal R$ is the relation on $\Bbb Z \times \Bbb Z$, such that $((a, b),(c, d)) \in \cal R$ if and only ...
1
vote
2answers
77 views

Showing that ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

Q(x, y) := “Student x did exercise y in the book” R(x) := “Student x gets an A in the class” So my goal is to show that the following equivalency holds: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S ...
1
vote
1answer
54 views

distributing r distinct objects into n-distinct boxes when repetition is allowed

Suppose there are 5 students and we are trying to create 3 distinct commissions which every student must be in at least one commission and every commission must have at least 2 members. what is the ...
0
votes
2answers
85 views

What is the number of nonnegative solutions of a linear equation?

What is the number of solutions of a linear equation? for example look at this equation: $X_1+X_2+...+X_n=r$ The number of solutions is the following formula, because the way of choosing $r$ objects ...
-2
votes
1answer
133 views

Expected value of $\sin^2(0.01n)$ for discrete $n$

Is it possible to calculate the expected value of $\sin^2(0.01n)$, with $n$ taking non-negative integer values? Normally, when we wish to find the expected value of the sine function, we integrate ...
0
votes
1answer
28 views

What rule of logic is this?

I was reading a proof on proving associative law for XOR operator and came across these steps. = (AB'C'+A'BC')+(A'+B)(A+B')C = (AB'C'+A'BC')+(A'(A+B')+B(A+B'))C = (AB'C'+A'BC')+(A'B' + AB)C I ...
2
votes
1answer
262 views

If $\gcd(\gcd(a, b),\gcd(a, c))=1$, then $\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
-1
votes
2answers
39 views

prove the equivalence of the following statements: 2x-1 is irrational; x/3 is irrational

I am stumped. I really have no idea how to solve this problem. Can someone please help me through this? THE TWO EQUATIONS ARE SEPERATE
2
votes
1answer
189 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
1
vote
1answer
73 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
6
votes
2answers
160 views

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
77 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
2answers
52 views

Getting the cumulative distribution function for Sqrt(X) from the cumulative distribution function for X

I've a data set X which consists of randomly generated numbers. My aim is to plot the cumulative distribution function for square root of X without generating data set for square root of X. I'm using ...
0
votes
1answer
9 views

Discrete algebra and exponents (See body text)

Let $a,b\in\mathbb{Z}^+$. If $a \equiv b\bmod 49$, and $\gcd(a,49) = 1$. How can I find any positive integer $n > 1$, so that $b^n\equiv a\bmod 49$? I'm completely stumped by this. I've been ...
1
vote
4answers
307 views

Closed Form for Factorial Sum

I came across this question in some extracurricular problem sets my professor gave me: what is the closed form notation for the following sum: $$S_n = 1\cdot1!+2\cdot2!+ ...+n \cdot n!$$ I tried ...
-2
votes
1answer
69 views

Decorate Tables

You have $r$ red, $g$ green and $b$ blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What ...
1
vote
0answers
17 views

Topology of the intersection of toric arrangement

Hope someone will help me in the solution of the following question. I'm working on some topological problem involving the topology of the intersection of some characters of the torus. I want ot find ...
3
votes
0answers
143 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...