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
2answers
47 views

Combinatorics (discrete math course help)

2 questions: How many odd $14$ digit numbers can you compose of ten $1$'s and four $2$'s such that in between every pair of $2$'s there are at least two $1$'s? Here I could have $4$ or $5$ spaces ...
8
votes
3answers
274 views

Prime numbers divide an element from a set

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.
2
votes
2answers
122 views

Proving $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$ for prime $p$ [closed]

I am having trouble proving that any prime number $p$ and integers $a$ and $b$, $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$
0
votes
1answer
28 views

Existence of infinite subsequence of trees assuming two tree operations

Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ grow a leaf: choose any vertex and connect it to a new leaf Starting with any rooted ...
1
vote
1answer
64 views

How many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads?

I am trying to figure out how many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads. I understand how to do the problem with two colors, but I am struggling to ...
0
votes
0answers
29 views

Determine the truth values

Let P(x) : x^2 ≤ 4. Determine the truth values of the following propositions. Assume the domain for the variable is all positive integers: 1, 2, 3, 4, 5, and so on. ...
0
votes
1answer
18 views

Use quantifier to express each of the following statements symbolically

Let F(x,y) be the statement x can fool y, where the domain of discourse for both x and y is all people. Use quantifier to express each of the following statements symbolically. Then write the negation ...
-1
votes
1answer
21 views

equivalence relations

Let $S$ be the collection of everywhere defined differentiable functions. Define a relation $R$ on $S$ as follows: *$f$ is related to $g$ if there exist a nonzero $k$ such that $f'(x) =kg'(x)$ for ...
1
vote
1answer
29 views

How Many Triangles are Created by n Lines in the Plane?

Suppose we are given n lines in the plane in "general position", which in the present case we define to mean the following: A. no 2 lines are parallel or identical B. no 3 lines have common ...
0
votes
1answer
24 views

Identify this relation to be an injection, surjection, bijection or non-function

Identify this relation as an injection, surjection, bijection or non-function, where f:A->B, with x an element of A, and the value of f is determined by: f(x)=the number of elements of x, A={subsets ...
0
votes
1answer
33 views

Identify as an injection, surjection, bijection or non-function

Identify as an injection, surjection, bijection, or non-function, where f:A->B with x an element of A, and the value of f is determined byL f(x)=the address number of x A={houses} B={natural numbers} ...
1
vote
1answer
25 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
1
vote
1answer
29 views

Implementation of a a binary search tree.

I am currently working with Binary Search Trees and I am having trouble understanding the question for this homework I am doing. Question: Draw the binary search tree that results from the following ...
1
vote
1answer
22 views

How to prove by this type of question by Induction (If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m \geq 1$, then $a_n = 2^n + 3n + 1$)

Please do not tell me how to prove this exact question. I would like to know how to go about proving the following type of question by induction: If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m ...
2
votes
0answers
23 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
6
votes
1answer
238 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
2
votes
1answer
97 views

Combinatorics question with stars and planets [closed]

Assume that a small universe has 10 distinct stars and 100 distinct planets so that 20 of them are habitable and 80 of them are nonhabitable by humans. How many ways are there to form a galaxy with ...
3
votes
2answers
125 views

Application of Mergesort

We have $8$ players and we want to sort them in $24$ hours. There is one stadium. Each game lasts one hour. In how many hours can we sort them?? I thought that we could it as followed: ...
1
vote
1answer
59 views

Counting regions in a disk that has been cut by lines

Let $n$ be a positive integer, and $n$ lines drawn in a ring such that each one of them intersects with all of them, but no more than two intersect at one point. prove that the lines cut the disk ...
1
vote
2answers
29 views

Explicit formula for recurrence relation

I am given recurrence relation : an = 5an/2 + 3n, for n = 2,4,8,16... and a2 = 1. I found first 4 terms and I don't see a pattern. a4 = 5*1 + 3*4 = 17 a8 = 5*17 + 3*8 = 109 a16 = 5*109 + 3*16 = 593 ...
-2
votes
1answer
68 views

Finding number of regions on the circle that is cutting by chords using mathematical induction [closed]

Let $n$ be a positive integer, and suppose that $n$ chords are drawn in a circle such a way that each chord intersects every other, but no three intersects at one point. Use mathematical induction to ...
1
vote
0answers
45 views

Predicate Logic and Negation Assistance

I just want to make sure I'm on the right path with these: Using the predicate symbols shown and appropriate quantifiers, write each English language statement in predicate logic. (The domain is ...
1
vote
1answer
59 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
0answers
21 views

Application of divide-and-conquer

Good afternoon. Consider a two-position switch with two inputs and two outputs. In one position inputs 1 and 2 are connected to outputs 1 and 2 respectively. Using these switches, design a network ...
1
vote
0answers
26 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
0answers
31 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, ...
1
vote
1answer
26 views

Proof that a bipartite graph cannt exist with this degree sequence

Is there a bipartite graph with degree sequence $3,3,3,3,3,6,6,6,6,6,6,9$? Answer is No.Here's my justification: Suppose there exists such a bipartite graph G with the given degree sequence.And ...
0
votes
0answers
20 views

Fleury’s Algorithm in case of we have odd-degree nodes

I'm studying Fleury’s Algorithm to find Eulerian tour. I'm confused in case of we have two odd-degree nodes. What should we do in this case? Should we duplicate the path between the two add-degree ...
0
votes
2answers
25 views

Show that f is injective if and only if for any $y \in Y$ , the preimage $f^{−1}(y) \subseteq X$ is either empty or a singleton.

Let $ f:X \rightarrow Y$ be a map Show that f is injective if and only if for any $y \in Y$ , the preimage $f^{−1}(y) \subseteq X$ is either empty or a singleton. Since this is an if and only if ...
1
vote
0answers
38 views

Inverse Relation of Irreflexive Property.

We are taking the inverse of relation to check that inverse of R is transitive, reflexive , symmetric and anti-symmetric to as it is on R (not inverse).. My question is that why we are not taking the ...
2
votes
1answer
18 views

Show that for any subset $C\subseteq Y$, one has $f^{-1}(Y\setminus C) = X \setminus f^{-1}(C)$

Let $f: X\rightarrow Y$ be a map Show that for any subset $C\subseteq Y$, one has $f^{-1}(Y\setminus C) = X \setminus f^{-1}(C)$ In this case $f^{-1}$ refers to preimage I started off with trying ...
1
vote
1answer
21 views

Partial ordered set

Consider the set $\{9,3,56,4,2,15,1544,8,112,675,20,336,772,28,405,45,224,135\}$ with the binary relation if x divides y. Show that the relation is a partial order. These are the only directions my ...
2
votes
3answers
40 views

Recursive Sequence solving for $f(200)$

Let $f$ be defined recursively by: $f(0)=5$ and $f(n+1)=3f(n)-2$. Find $f(200)$ I'm really confused how to go about solving this. Can someone help? Thank you!
1
vote
0answers
36 views

Show that the following family of hash functions is $2$-wise but not $3$-wise independent

Consider the following family of hash functions that map $w$-bit numbers to $l$-bit numbers (i.e. the range is $\{0,...,m-1\}$ where $m=2^l$): $\mathcal{H} = \{h_{A,b}|A\in \{0,1\}^{l\times w}, b \in ...
0
votes
1answer
19 views

One-To-One functions

Let A be the set with n elements and B be the set with m elements. How many one-to-one functions are there from A to P(B) (power set of B). There are n! total functions from A to B. and (2m)n from A ...
1
vote
2answers
42 views

Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

I know this question has been posted before, there is a solution in my text-book for this question and also this is posted on so many websites with full solution but I still don't understand. So can ...
0
votes
0answers
18 views

Show that this is the number of moves that have to be done to solve the problem [duplicate]

Prove that $2^n − 1$ moves are necessary and sufficient to solve the Towers of Hanoi problem. Could you give me some hints how I could do that??
2
votes
0answers
44 views

Recursive definition of a language

Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria: All words in L contain the substring aa an odd number of times. All words in L are such ...
2
votes
3answers
81 views

$x+1/x$ an integer implies $x^n+1/x^n$ an integer

Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$. I can't figure out and understand the question. Can you give me ...
1
vote
1answer
126 views

Finding recurrence relation for digits

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation. I can't figure out and understand the question. Can you ...
0
votes
0answers
42 views

Check if $2^{2^n}=O(2^n)$

I want to check if $2^{2^n}=O(2^n)$. That's what I have tried: Let $4^n=O(2^n)$. Then, $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1$: $$4^n \leq c \cdot 2^n$$ $$$$ ...
3
votes
1answer
55 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
2
votes
0answers
35 views

How the second form of following equation is derived form first form (i.e. given first line, what are the steps involved in writing second line

How the second form of following equation is derived form first form (i.e. what are the steps involved in writing second line)
0
votes
1answer
30 views

Properties of Relations and their negations.

There are three properties of relation, 1. Reflexive 2. Symmetric 3. Transitive and if all properties are satisfy by a relation then its known as ...
1
vote
2answers
46 views

permutation;discrete structures review

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Consider a group of n people, let ...
0
votes
2answers
42 views

Why does $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$

I was looking at a solution to the problem and it says that $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$. I am wondering why this is true? Any help would be highly ...
0
votes
1answer
51 views
+50

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
0
votes
1answer
37 views

Approximating a binomial coefficient using Stirling's formula

I am working on a problem of modelling a rubber molecule as a one-dimensional chain consisting of $N=N_{+}+N_{-}$ links, where $N_{+}$ points in the positive $x$-direction a distance $a$ and $N_{-}$ ...
2
votes
1answer
118 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
38 views

Circular permutations problem with putting objects into circle

How many options do I have if I want to put red boxes and black boxes into circle so that no two black boxes are next to each other? I have 12 red boxes and 4 black boxes. Also all two red and black ...