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

Is the relation A = {(a,a), (c,c), (d,d), (b,a)} transitive?

I'm working on a discrete math problem to solve for reflexive, symmetric and transitive and I'm stuck on the transitive one. How do I solve for the transitive of the following? A = {(a,a), (c,c), ...
1
vote
1answer
39 views

Prove a function $g: \mathbb{ Z}^{+} \times \mathbb{ Z}^{+} \to \mathbb {Z}^{+}$ is one-to-one

I'm given $g: (m,n) = 3^m 9^n, where (m,n)\in \mathbb{Z}^{+} \times \mathbb{Z}^{+}$ how do I prove this function is one-to-one? All I've figured out so far is that $g((m_1,n_1)) = g((m_2,n_2))$ ...
3
votes
3answers
55 views

Proving $n! > n^3$ for all $n > a$

Prove by induction: Find a, and prove the postulate by mathematical induction. For all $n > a, n! > n^3$ Where ! refers to factorial. So far I've done a bit of it, I'll skip right to the ...
0
votes
2answers
44 views

Help with Relations and Functions?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
2answers
32 views

Prove a function $f: \mathbb{R}^{2} \to \mathbb{R}^{2}$ is surjective

I'm given the map $f: (x,y) \mapsto (x+3,4-y): \mathbb{R}^{2} \to \mathbb{R}^{2}$; how do I prove this function is onto (surjective)? So far I said that let $x=z$ and $y=k$, therefore ...
2
votes
2answers
37 views

Getting two answers to: How many monoalphabetic substitution ciphers of $\{A,B,C,D\}$ are possible in which no letter is fixed?

From Combinatorics by Mazur: I am trying this with $\{A,B,C,D\}$ but I am getting two answers. If I enumerate then I get $9$. $ABCD,\ ABDC,\ ACBD,\ ACDB,\ ADBC,\ ADCB$ $BACD,\ BADC(1),\ BCAD,\ ...
0
votes
1answer
72 views

How many balls must a woman select from $10$ red balls and $10$ blue balls to be sure of having at least three balls of the same color?

A bowl contains $10$ red balls and $10$ blue balls. A woman selects balls at random without looking at them. How many balls must she select to be sure of having at least three balls of the same ...
0
votes
1answer
79 views

Proof writing involving functions: Injective and Surjective [closed]

Given two sets that have the same cardinal number Example: \begin{align*} A & = \{1, 4\}\\ B & = \{1, 2\} \end{align*} How would you prove that the function from $A$ to $B$ is always ...
1
vote
1answer
43 views

How many sets with such conditions?

We have S sets. $$M = \{M_1, M_2, ..., M_S\}$$ Overall there are n elements, and $$|M_i| = 6, \forall i$$ $$|M_i\cap M_j| \neq 2, \forall i,j$$ So, the question is: what is the maximum number of ...
0
votes
1answer
30 views

Help with Relations and Functions in Discrete Mathematics.

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
1
vote
1answer
71 views

Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? [duplicate]

Question: Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? I have no idea where to start.
0
votes
1answer
199 views

Formal proof of transitivity of a transitive closure

I am currently struggling with this question. It is obvious that the relation is transitive however I'm not sure how to prove it. ...
-2
votes
1answer
23 views

Solving basic arithmetic modulo

I have no idea to solve these 3 questions because i only seen the question include with equal sign. ex) $a\equiv r \mod n$ $(-2)^5+ 7\mod 6$ $15-11\cdot12\mod12$ $4\cdot13+23\cdot2\mod15$
0
votes
2answers
50 views

Solving $x^3 = x^ 2 − 2 \pmod 7$. [closed]

How one can solve the equation $x^3 = x^ 2 − 2\pmod 7$?
0
votes
1answer
88 views

How many strings of length $7$ contain the substring bcd?

Suppose there is a string of length $7$ that contain letters from $\{a, b, c, d, e, f, g\}$ without repetition. How many combinations can be made so that there is a substring "bcd" (b,c,d are ...
0
votes
1answer
30 views

How many versions of a shirt can be made if it comes in $12$ colors, male or female fit, and $3$ sizes for each sex?

Suppose there is a shirt of some brand. It comes in 12 colors, in Male or Female fit, and there are 3 sizes for both Male and Female. How many possible versions of the shirt can be made? I've gotten ...
3
votes
2answers
54 views

Mathematical induction and Stirling numbers

I want to find a formula for the following series $$ \sum_{i=1}^m {m \choose i} i! S(n,i)$$ Where $S(n,m)$ is the Stirling numbers of the second kind. Now I evaluated this series at $m=1,2,3$ for ...
1
vote
2answers
241 views

Show that f(x)=e^x from set of reals to set of reals is not invertible…

Yes, this is my question... How can you prove this? That $f(x)=e^x$ from the set of reals to the set of reals is not invertible, but if the codomain is restricted to the set of positive real numbers, ...
0
votes
1answer
38 views

generating function from recurrence relation

I am referring to another question of mine: recurrence relation of a language However, in this question, I am considering the language X of bitstrings with no more than 3 consecutive zeros. (original ...
3
votes
1answer
54 views

How many ways are there to add toppings to ice cream?

At an ice cream shop, in addition to chocolate chips, there are 8 different toppings. If a customer wants to add two more toppings in addition to the chocolate chips in how many ways can he do ...
1
vote
1answer
68 views
3
votes
4answers
2k views

Why b%2==1 implies that rightmost digit of b in binary form is 1

How one can deduce that if b is any number and if b%2==1 then rightmost digit of b in binary form will be 1 without checking it manualy
0
votes
1answer
26 views

If I have a 45 bit ternary number, where x bits must be 0, y bits must be 1, and z bits must be 2…

... How, knowing a specific x, y, and z, can I find how many different combinations of 0,1,and 2 can I have? I have a specific problem. 15 bits must be zero, 20 must be one, and 10 must be 2. But I ...
2
votes
2answers
50 views

Solve the recurrence relation: $a_n = 6a_{n-1} - 9a_{n-2}$

Recurrence relation:$$a_n = 6a_{n-1} - 9a_{n-2}$$ Initial conditions:$$a_1 = 1, a_2 = 9$$ I am having a bit of trouble finishing off this problem. So far I have: Assume:$$a_n = r^n$$ $$r^n = ...
2
votes
2answers
110 views

Is the empty set in every language?

I know that in set theory, $\forall A:\emptyset \subseteq A$ My question is, does this apply to formal languages? In my mind, formal languages are just a set of strings that are over some set of ...
0
votes
1answer
56 views

Select $7$ switches among $60$ of which one has failed

Given a computer network with $60$ switching nodes. If one node has failed, in how many ways can seven nodes be selected without encountering the failed node? I set this problem up as $\binom {59} ...
2
votes
2answers
76 views

Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2. In my attempt. I try $n=2$, and ...
3
votes
1answer
96 views

Trouble understanding why Disjunctive Normal Form is polynomial time solvable but not CNF.

So from my understanding when looking at a Boolean formula in Disjunctive Normal Form, its satisfiability is decidable in polynomial time, yet this isn't the case for CNF. Is this because with DNF you ...
-2
votes
2answers
101 views
1
vote
1answer
58 views

Does the empty set satisfy this statement?

Let K be the subset of |R (real numbers: Statement: John likes K if and only if ∃a∈K such that ∀x∈K, a < x Question: Does John like any subset of the real numbers? My answer: John will not ...
1
vote
1answer
41 views

Find Discrete Time Fourier coefficients of $(-1)^n x[n]$

Given that $x[n]$ is an N-periodic sequence with Fourier coefficients $a_k$, I want to find the Fourier coefficients of $$(-1)^n x[n]$$ for the situation in which $N$ is odd. I'm also interested in ...
0
votes
1answer
39 views

Proving a Recursive Definition using Induction

I have the following recursive definition of a set $S \subseteq \mathbb N \times \mathbb N$ : ...
0
votes
2answers
33 views

Proving $\prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$ by induction

So I have to prove the following using induction. ${\displaystyle \prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right)} = \frac{n+1}{2n}$ I showed the basis step that if $n=i=2$, then the two functions ...
0
votes
2answers
52 views

what is the difference between well ordered set and totally ordered set?

I am unable to get the difference between a well ordered set and a totally ordered set ,I have gone through book , it says that if some non-empty subset of a poset has a least element then it is a ...
3
votes
1answer
47 views

[Ask]prove that for all integers 'n', if n is bigger than 2. then there is a prime number 'p' between n and n!

I think using contradiction will be useful. Suppose $p$ exists which divide $n!-1$ and suppose that $p \leq n$ leads to a contradiction. But I have no idea how to show contradiction I believe ...
0
votes
2answers
115 views

Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology. [closed]

Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology. How to prove this without using truth table? I think it need some existing tautologies like $p\to q\iff \neg p\lor q, \:\: p\land ...
1
vote
0answers
76 views

My mom is driving me crazy. :-) [Probability distributions]

Please I need serius help, with this prob. I do several problem from the book but I'm not be able to solve this: 1) My mom, mix 5000 of chocolate chips in a dove. 2) She cooked the dove and make ...
1
vote
1answer
89 views

Expressing propositional function without quantifiers

I have been following "Discrete Mathematics and its Applications" textbook by Rosen, 7th edition. I have come across an exercise question (1.4, #20) that I am not sure how to answer. The book gives ...
0
votes
2answers
20 views

Expressing statements in Discrete math

Given that $A$ is the set of all Alpha's $M$ is the set of all Men how do I express this statement: Not all Alpha's are Men ............. My attempt: $A \subset S = 0$ in other words saying ...
3
votes
1answer
21 views

Question about subset and elements.

Let $A = \{3,4\}$ be a subset of $S = \{1,2,\ldots,6\}$. Or $A \subseteq S$ and $n \in A$, what is $n \notin A$? Would $n \notin A$ be $\{1,2,5,6\}$? Does that question even makes sense? Help! ...
0
votes
2answers
73 views

Solve the recurrence relations

Recurrence Relation: $$a_n = 6a_{n-1} - 9a_{n-2}$$ Initial Conditions: $$a_1 = -1, a_2 = 1$$ The answer in the back of the book is $$(2n-1)3^{n-1}$$ But I don't see how they got there. When using ...
1
vote
3answers
58 views

How would you prove this statement?

Let $K$ be a subset of $\Bbb R$ (The real numbers) Statement: John likes $K$ if and only if $\exists a\in\Bbb R$ such that $\forall x\in K, a \le x$ Question: Does John like all subsets of the real ...
0
votes
2answers
89 views

The number of bits in N!

I'm struggling with this homework problem: If N is an n-bit number, how many bits long is N! approximately (in Θ(·) form)? I know that the number of bits in N is equivalent to log base 2 of N, but ...
1
vote
1answer
159 views

Composition of relations: A ∘ B

Solve: Composition of relations: A ∘ B A = {(1, 1), (1, 2), (4, 1), (4, 2)} B = {(1, 1), (2, 1), (1, 4), (2, 4)} When i solve mentally i get A ∘ B = {(1, 1), (2,2)} But when I draw an ...
1
vote
2answers
77 views

Prove $\frac{1\cdot 3\cdot 5\cdots (2n - 1)}{ 2^n(n + 1)!}\cdot 4^n= \frac{1}{n+1} {2n\choose n}$

Prove: $$ \frac{1\times 3\times 5\times \cdots \times (2n - 1)}{2^n (n + 1)!} \times 4^n = \frac{1}{n+1} \binom{2n}{n} $$ -Sorry I don't know how to do choose notation in stack exchange. I'm ...
0
votes
0answers
23 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
2
votes
1answer
127 views

Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

$n$ is also given to be an even number. So I want to prove this by using the pigeon-hole principle. I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as ...
1
vote
2answers
72 views

How to apply Pigeonhole principle in this question

There are 10 people at a party and each person knows an even number of people at the party. Prove that there are 3 people who know the same number of people. Here we assume that knowing someone ...
4
votes
1answer
57 views

Find integer a,b > 1 such that $2^a + 3^b = 2^{a+b} +1$

I would like to know if it is possible to find an integer solution to $2^a + 3^b = 2^{a+b} +1$ with $a,b > 1$
0
votes
1answer
75 views

Describe each of the following sets by listing its elements

Slightly confused here: $X = \{Na, \{b\}, \emptyset\}, Y = \{Na, b\}, Z = \{\emptyset\}$ How would I list the elements of: 1) $Y ∩ Z$ (the answer to this is "nothing" but how do I write that ?) ...