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
votes
0answers
33 views

Difference between two expressions for combinations with repetition.

While attempting to solve problems that compute the number of combinations with repetition (ie, a store has 4 flavors of ice cream and you are picking 3 with repetitions allowed, how many ways can you ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
0
votes
1answer
37 views

S is a finite set show that $|P(S)|$ is $2^{|S|}$. [duplicate]

If $S$ is a finite set, show that $|P(S)| = 2^{|S|}$. So I know that $|P(S)|$ means the number of elements in the power set of $S$, but I don't understand the relation between the power set and ...
1
vote
2answers
37 views

Order of $f(n) = 4n + 6n^3 - 8n^5$

If a function $$f(n) = 4n + 6n^3 - 8n^5$$ then the order of $f$ is: The answer I have is $\log(n)$, but I'm not sure if it's right.
1
vote
1answer
38 views

Proving the upper bound of edges in a convex polyhedron

The question is the following: Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of ...
2
votes
1answer
45 views

Hierarchy of Mathematics Breakdown

Can you provide me with a hierarchical breakdown on Discrete Math as it applies to computer science? By this I mean a breakdown on topics that fall under the study of discrete numbers, specifically ...
1
vote
3answers
33 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
1
vote
0answers
40 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 ...
2
votes
1answer
73 views

Solve the recurrence relation: $2a_n = 7a_{n-1} - 3a_{n-2}; a_0 = a_1 = 1$

$2a_n = 7a_{n-1} - 3a_{n-2}\\ a_0 = a_1 = 1$ My attempt: $2t^2 - 7t + 3 = 0\\ t = -\frac{1}{2}, -3\\ \\ U_n = b(-\frac{1}{2})^n + d(-3)^n\\ b+d = 1 = -\frac{1}{2}b-3d\\ b = \frac{8}{5}, d = ...
0
votes
1answer
16 views

How to determine whether a given relation on a finite set is transitive?

On $R = \left \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,5),(5,5) \right \}$ Not reflexive because (3,3) and (4,4) are missing? Not symmetric because (2,1) ,(3,2), (4,3), (5,4) are missing? Not ...
0
votes
2answers
23 views

Counting bitstrings of length 10 [closed]

a) How many bitstrings of length 10 have exactly 6 zero's? b) How many bitstrings of length 10 have as many 0's as 1's?
1
vote
1answer
16 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 ...
3
votes
1answer
38 views

Ways of getting three of a kind in a 52 card deck

This question has probably been asked before, but just to be clear here, I am NOT asking for the answer, I know the answer. What i want to know is why my solution is not equivalent to the actual ...
1
vote
2answers
22 views

Total $3$-digit odd number combinations from $1,2,3,4,5,6$

How many three digit numbers can be formed from the digits $1,2,3,4,5$ and $6$, if each digit can only be used once? How many of these are odd numbers? How many are greater than $330$? I've ...
4
votes
1answer
36 views

Number of ways to choose 6 books out of 20 books such that no 2 are adjacent books

I was trying to do the following question: Describe a bijection between ways of choosing 6 books out of 20 books so that no two adjacent books are selected and a 15-bit sequence with exactly 6 ...
0
votes
0answers
32 views

AoPS Intermediate Algebra vs. Higher Algebra by Hall and Knight? And some more questions about learning math.

Ok. I'm learning algebra at the level of AoPS algebra 2, and I want to quickly progress through math. Allow me to explain the situation. I am highly interested in artificial intelligence/computer ...
0
votes
1answer
32 views

Discrete math: Need help understanding these problems

Find a function in the list $n^2$, 1, $n^3$, $n \log n$, $\log n$, $n^4$, $2^n$, $n!$, $n$, $\pi^n$, $n^5$ that has the same order as: (a) $f(n) = 3n^4 + 6n^2 - 8n - 5 $ (b) $f(n) = 5$ (c) $f(n) = ...
-2
votes
2answers
45 views

Please help prove this summation problem for me [closed]

Prove that for all integers n greater than or equal to 1, $\sum_{k=1}^{3n} (4k+3)=3n(6n+5)$.
1
vote
1answer
35 views

Prove or disprove this lemma for Catalan Numbers

Prove or disprove that for all non-negative integers $n$ and $r$ with $r+1$ is less than or equal to $n$, $C(n,r+1)=C(n,r)\times\frac{n-r}{r+1}$.
1
vote
2answers
27 views

How many ways are there to place 7 distinct balls into 3 distinct boxes?

How many ways are there to place $7$ distinct balls into $3$ distinct boxes? is the question I'm confused about. The solution shows that the correct answer is $3^7$. I'm just confused why this is. ...
1
vote
1answer
26 views

Cantor's Diagonalization & Cantor Pairing Function

I don't fully understand the concept behind... (1) The Cantor Pairing Function and (2) Cantor's Diagonalization Method. I understand that (1) and (2) involve proving if a set is countable or not. ...
3
votes
3answers
80 views

How do the answers to combinatorial problems change if instead of 4 different objects we have 4 identical ones?

I think I did the first parts of these correctly, but I really don't know about the last part? Could I just divide all my previous answers by $4!$ If you have $4$ children, $8$ unique fruit, and $8$ ...
2
votes
1answer
68 views

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+…+|x_{n}| \leq t$ have?

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+...+|x_{n}| \leq t$ have? We know that: $x_{i} \in Z,\ \forall i \ 0\leq i \leq n \ and \ t\geq0.\ $ I know that if we ...
-1
votes
0answers
11 views

Counting problem: 4 members of a committee that must elect a prez and secretary, …? Use Addition Principle [closed]

A committee composed of Mo, Ty, Ma, and Le is to select a president and secretary. How many selections are there in which Ty is president or not an officer? Use the Addition Principle.
0
votes
1answer
20 views

How can I tell if the function $f(n)=2n$ on $\mathbb Z$ is one-to-one, onto, or both?

The domain of the function is the set of all integers. The codomain of each function is also the set of all integers. $$f(n) = 2n $$ I was thinking that the function is one-to-one but I don't know ...
0
votes
2answers
18 views

Reflexive closure Proof

I have this problem I can't figure out. Suppose R is a relation on A, and let S be the reflexive closure of R. Prove that if R is symmetric, also is S. Could you suggest me how to do it? Thanks
1
vote
2answers
22 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
24 views

Find number of pairs satisfying given absolute difference and product

If I'm given absolute difference of two numbers and their product, how can I determine the number of ordered pairs possible? What I have thought is - Total number of pairs possible may be 4, 2 or 0. ...
0
votes
1answer
24 views

Box containing coins - Finding sets from the box of coins

A set of 4 coins is selected from a box containing 8 dimes and 6 quarters Find the number of sets of four coins. Find the number of sets in which two are dimes and two are ...
2
votes
2answers
33 views

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$.

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$. Cut vertex $v$ here is a vertex which make the ...
0
votes
1answer
38 views

Arithmetic series $1 + 3 + 5 + \dots + (2n + 1)$

$$1 + 3 + 5 + \dots + (2n + 1) $$ For the above question, the answer is $(n + 1)^2$ and I understand that $n$ is the number of terms. If I let my $n$ is $3$, that means I add $1 + 3 + 5 = 9$ but if I ...
2
votes
2answers
31 views

Is this question a pigeon hole question?

How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15? Explain. It seems like this is similar to the birthday pigeon hole ...
0
votes
2answers
11 views

Solving a single-term recurrence relation with a variable coefficient?

$a_n = 2na_{n-1}\\ a_0 = 1$ How do I solve this? Is there a characteristic equation? I found $a_1 = 2, a_2 = 8, a_3 = 48$ but I don't know what to do with that information to solve. Please help, ...
0
votes
0answers
15 views

Solving single term recurrence relation?

$a_n = -3a_{n-1}\\ a_0 = 2$ Therefore $a_1 = -3(2) = -6\\ a_2 = -3(-6) = 18\\ a_3 = -3(18) = 54$ So... $x^n = -3^{n-1}$? If so $x^2 = -3^1$, so $x^2 + 3 = 0$, then $x = \pm (i\sqrt3)$. That doesn't ...
1
vote
1answer
45 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
47 views

How many consecutive squares can be subtracted from a number?

Let's say I am given a number N. I want to check how many consecutive squares of integers(starting from 1) can be subtracted from this number. Example- For N=13, I will first subtract 1(=1^2), leaves ...
0
votes
1answer
24 views

How to calculate monthly payment

I have data inside spreadsheet and it is calculationg based on formula to calculate Monthly payemnt. Now I am implementing this functionality in my HTML using ...
0
votes
2answers
44 views

How many elements are there in the set R?

+Let A be a finite set with $n \geq 4$ elements and let R be an equivalence relation on A . Suppose that there are exactly $n-2$ equivalence classes and that no equivalence class can contain exactly ...
0
votes
1answer
30 views

Simple question about recursive sequence format regarding $a(n+2) = -4a(n+1) + 5a(n)$

Suppose there's a recursive sequence $a(n+2) = -4a(n+1) + 5a(n)$ How can i convert it into the form $a(n)$ because I am most comfortable solving questions in this form. I tried to find out but I'm ...
0
votes
1answer
23 views

de morgan's law for greater and less than

Suppose that we let $!$ mean not (negation) and let $a,z,p$ be integer variables. We have the expression. $$! ( (a>7) \& (z<=p) ) $$ and we can solve it by De Morgan's laws to yield: ...
1
vote
2answers
52 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 ...
3
votes
1answer
99 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
1answer
49 views

We roll a standard fair die over and over. What is the expected number of rolls until the first pair of consecutive sixes appears.

During class we split this task into smaller pieces: Let $X$ = r.v. denoting the result of the first roll Let $Y_1$ = r.v. denoting the result of the first roll Let $Y_2$ = r.v. denoting the result ...
1
vote
2answers
37 views

In how many ways can I merge $m$ and $n$ items without disturbing the order in each group?

I have two lists having all distinct elements. One contains $m$ elements and other contains $n$ elements. We need to arrange them such that the order of elements of individual lists is not disturbed. ...
3
votes
2answers
48 views

Objects into two bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1,a_2,⋅⋅⋅,a_n$ into two bags. For each $i=1,2,⋅⋅⋅,n$, the weight of $a_i$ is $w_i$ kilograms. The ...
1
vote
1answer
32 views

How many ways are possible to place k items in n spots such that order of k items is not disturbed

I have k items, need to place them in n spots(n>k). In how many ways can this be done? Example - for k=2 and n=4, these are the possibilities assuming items to be like this [1,2] 12-- 1-2- 1--2 -12- ...
1
vote
2answers
52 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 ...
0
votes
1answer
38 views

two place predicate logic

Im trying to prove following,as lecturer did not have time to go through the proof on the lecture, I wonder how to solve at least the first statement $$(\forall x)(\forall y)L(x, y) ≡ (\forall ...
2
votes
1answer
71 views

An idea on the Collatz problem

I am using the T-version of the function: $$ T(x)=\left\{\begin{array}{cl} \text{down}(x)=x/2,& \mbox{x even}\\ \quad\,\,\,\text{up}(x)=(3x+1)/2,& \mbox{x odd}\end{array}\right. $$ I will ...
0
votes
2answers
27 views

Finding a homomorphism

I'm not sure if I'm solving this problem correctly. Can someone verify? Question: Find a non-trivial homomorphism from $[\mathbb{Z}_6, \oplus_6]$ to $[\mathbb{Z}_9, \oplus_9]$ *My solution ...