Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
1answer
42 views

General Definition of Anticommutative Operations

I have a problem with this definition of anticommutative operators. I found the following: An operation $\circledast$ is called anticommutative if it satisfies the following: (i) There is a right ...
0
votes
2answers
102 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
2answers
57 views

GCD and LCM.. Need help

Im sure this is obvious... but i was absent in class and am having a hard time finding it on google. If someone would be so kind to help explain to me how to find the GCD and LCM of the number: ...
0
votes
1answer
46 views

Proof of Surjective and injective

I run into a problem when I am trying to studying my review question, I am not sure how to prove the following question: Suppose A,B,C are sets and f:A→B, g:C→A, f∘g:C→B. Are they true or flase. if ...
0
votes
2answers
82 views

Calculate product of transpositions

I've searched for this kind of question-answer, but didn't managed to find one because the problem is quite specific. Let me explain: I have permutation: $(13927)(5846)$ which I must write as ...
0
votes
1answer
94 views

Calculating probability of winning Power Ball

Today I tried to calculate the probability of winning a jackpot in Power Ball California Lottery. There are 1-59 numbers from which you have to guess 5 out of 5 and 1-35 numbers from which you have to ...
0
votes
2answers
47 views

Boolean Logic - Why doesn't the Associativity Law work in this scenario?

By the associativity law, shouldn't the statement below be true? I understand that the truth tables are different but where exactly does the associativity law apply then if this is False? ...
0
votes
1answer
158 views

Solving a recurrence involving floor and square root (Concrete Mathematics 3.28)

I'm working through Concrete Mathematics and having trouble understanding an answer to a problem (as well as what I could've done to come up with the answer). Problem 3.28 asks: Solve the recurrence ...
0
votes
1answer
54 views

How to prove statement about $\mathcal{O}, \Theta$ and $\hbox{o}$?

For a given function g, Prove that $\hbox{o}(g) \neq O(g) - Θ(g)$. Thanks for the help in advance
0
votes
2answers
196 views

Find a closed form for the generating function for each of these sequences

ind a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.) a) 0, 0, 3, -3, 3, ...
0
votes
2answers
385 views

How to scale numbers from one range to another range?

I'm stuck in a problem of mapping numbers from one range to another. I want to calculate popularity of a web page based on the number of page hits on a scale of 10. The problem is total number of web ...
0
votes
2answers
160 views

Using proof of equivalence

I just wanted to make sure whether I was on the right track or not with this. Let $r\in\mathbb{R}_{\ne0}$. Use a proof of equivalence to show the following: $$r\in\mathbb{Q} \iff ...
0
votes
4answers
51 views

Discrete Math- four digit odd integers with distinct digitst

a) Find the number of four-digit odd integers that have distinct digits. b) Find the number of four-digit even integers that have distinct digits. I've been working on this problem and I can't figure ...
0
votes
2answers
62 views

Find the sequence, given generating function.

I am obliged to find the sequence which generating function is $\large f(x)=\frac{1}{(x+2)^2}$. I know how to find a sequence for example for $\large f(x)=\frac{1}{x^2-5x+6}$ I show it as two ...
0
votes
2answers
69 views

Discrete Mathematics - Show that a conditional statement is a tautology.

I am trying to show that the conditional statement: $$[\mathord{\sim}p \land(p\lor q)] \to q$$ is a tautology without using truth tables. Could someone help me understand how to do this?
0
votes
3answers
78 views

Suppose $X$ and $Y$ are greater than $0$. Show that $\gcd(X,Y)$ is $1$ iff $\gcd(X^m,Y^m)= 1$

Problem Suppose $X$ and $Y$ are greater than $0$. Show that $\gcd(X,Y)$ is $1$ iff $\gcd(X^m,Y^m)= 1$. Please help with the above. I have no idea what's going on. An explanation would be nice.
0
votes
3answers
54 views

How to show $((k+1)!)^2 2^k \leq (2(k+1))!$

How do you show that $((k+1)!)^2 2^{k+1} \leq (2(k+1))!$ This is part of an induction proof and I have not made any progress.
0
votes
2answers
31 views

Equivalence Relation Proof Help

Determine if the following relation on $\mathbb R$ is an equivalence relation: $a\sim{b}$ iff $|a-b|≤ 1$ Proof: Reflexive: Suppose $a\in\mathbb R$. Then $|a-a| = 0$ which is real and ...
0
votes
1answer
26 views

Discrete Mathematics One-to-One Proof Help

Is α: A x B --> A defined by α(a,b) = a one-to-one? (Assume A and B are ∅) This is what I have so far. Proof: Let (x1,yn) is in A x B where n is a positive integer. Suppose α(x1,y1) = x1 and ...
0
votes
3answers
122 views

Greatest common divisor. Help [closed]

Let $n \in \mathbb{N}$. Prove that $$\gcd(2^n+7^n;2^n-7^n)=1$$ $$\gcd(2^n+5^{n+1};2^{n+1}+5^n)=3\text{ or }9$$
0
votes
2answers
73 views

Determining elements of a set

So I have a couple questions on how to determine the elements in a set. I was hoping I could get an explanation on how to do these and if my answers were correct. Not really looking for answers just ...
0
votes
1answer
34 views

Reccurence relation

Closed form of $\ nT_n = 3(n-1)T_{n-1} + 1, n \ge 1$ I've tried calculating some terms, and looking it up on wolframalpha, it sais the generating function is $\frac{exp(x)}{1-3x}$. Where do i start? ...
0
votes
1answer
123 views

Understanding basic sets/subsets in discrete math by determining if statements are true or false

Hi I'm working on some basic set/subset comparison statements in the form of True/False. There are 4 statements that I have to determine whether they're true or false. I think I understand the first ...
0
votes
1answer
49 views

Discrete fourier transform problem

We have taken $1000$ observations from signal $s(t),t \in\Bbb{R}$ $$h(k)=s(k\Delta t+t_0),k=0,1,\dots,999,$$ where $\Delta t=1/200 $ and $t_0=-2$ (in seconds). When we calculate discrete fourier ...
0
votes
1answer
94 views

Stuck on writing a proof.

I am taking a discrete math class, and am still really new to writing proofs. I was wondering if anyone could help me with a problem. I am pretty confused on what it is even asking. Here is the ...
0
votes
1answer
12 views

A consequence of edge-criticality

Let $G$ be $\Delta$-edge-critical (that is, $G$ is $\Delta + 1$-edge-chromatic and removing any edge of $G$ gives a subgraph which is at most $\Delta$-edge-chromatic, where $\Delta$ is the max degree ...
0
votes
1answer
43 views

How does this theorem of Robertson, Seymour, and Thomas imply Hadwiger's conjecture for $k$ = 6?

The result in question is Theorem Every 6-contraction-critical graph $G \neq K_6$ has a vertex $x$ such that $G-x$ is planar. The article I'm reading ("A Survey of Hadwiger's Conjecture" by Bjarne ...
0
votes
1answer
45 views

On Hadwiger's conjecture for k=4.

I'm reading the article "A Survey of Hadwiger's Conjecture" by Bjarne Toft. Toft states that the following result implies Hadwiger's conjecture for the case $k=4$: Theorem. Let $G$ be edge-maximal ...
0
votes
1answer
92 views

Zhegalkin polynomial Boolean algebra

I have to find the Zhegalkin polynomial of $ (x\rightarrow y)\rightarrow z $. Please tell me if this is right: my polynomial is of this kind $ a_{0} + a_{1}x + a_{2}y + a_{3}z + a_{4}xy + a_{5}yz + ...
0
votes
1answer
32 views

Combinations with repetitions, equality among to solutions

The textbook I'm reading says the number of integer solutions for $$x1+x3+x5+x7=5 \text{ where } x1,x3,x5,x7>0$$ is equal to $$y1+y3+y5+y7=1, \text{ where } y1,y3,y5,y7>= 0$$ This connection is ...
0
votes
1answer
85 views

Random walk with weighted probabilities

Taking a walk on $\mathbb{N}$, starting at 1, I need to find out how many steps I expect to take before returning to the origin, as a fraction. For each step, I either walk forward, backward, or stay ...
0
votes
2answers
32 views

Show that if a prime number $p|a^n$ then $p|a$ [duplicate]

The title says it all, how can I prove the following: Show that if a prime number $p|a^n$ then $p|a$
0
votes
2answers
68 views

Showthat $\mathrm p \leftrightarrow \mathrm q$ and $(\mathrm p\wedge \mathrm q) \vee (\neg \mathrm p \wedge \neg \mathrm q)$ are logically equivalent

Given there are 3 logical variables p, q . Show that $(\mathrm p \wedge \mathrm q) \vee (\neg\mathrm p \wedge \neg\mathrm q)$ and $\mathrm p \leftrightarrow \mathrm q$ are logically equivalent without ...
0
votes
1answer
85 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
2answers
35 views

Random number x probability in interval [0,10]

So lets say $x=10*rand()$, so x will be equal to a random number on the interval [0,10]. So what is the probability of $2x+1$ rounding to $5$. So one can come up with $4.5<=2x+1<5.5$. Is that ...
0
votes
1answer
33 views

What is the relationship between the final concentrations of alcohol in the alcohol jug and water in the water jug?

If the mixture is being poured back into the jug with water, then how can the jug with water also contain ${\frac {V}{V+Q}}$. I would assume that when the diluted alcohol is poured into the jug ...
0
votes
1answer
36 views

Easy set partition problem

So I have this problem : Let A be a non empty set an P1 and P2 be two random partitions of the set A. Prove that the set is also a partition of A. I know that this is probably very easy to most of ...
0
votes
1answer
45 views

Simplifying a geometric series

I seem to be completely misunderstanding something about the simplification of a geometric series. $$\sum_{j=1}^{n+1} ar^j = \sum_{j=0}^n ar^j + (ar^{n+1}-a)$$ Why does this work? From what I tested, ...
0
votes
2answers
148 views

Probability Of Rolling A Strictly Increasing Sequence On A Six-Sided Die

By rolling a six-sided die 6 times, a strictly increasing sequence of numbers was obtained, what is the probability of such an event? I have no ideas on how to attack this. It says, an ...
0
votes
1answer
48 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
0
votes
2answers
48 views

Probability of a plant dying when it is dependent on the probability of it being watered.

You ask a neighbor to water a sickly plant while you are on vacation. Without water the plant will die with probability 0.85. With water it will die with probability 0.5. You are 81 % certain the ...
0
votes
1answer
73 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
0
votes
1answer
73 views

Non-binary 1-error correcting code

I'm stuck with this question: Find an 1-error-correcting code in $\mathbf{Z}_{5}^{6} = \mathbf{Z_5}\, \times \, \mathbf{Z_5}\, \times \, \mathbf{Z_5}\, \times \, \mathbf{Z_5}\, \times \, ...
0
votes
3answers
55 views

How do you find the probability of P(a and b)?

The probability model has a sample space of {A,B,C} with P(A) = 0.1, P(B) = 0.8, P(C) = 0.1. I found that P(B or C) = 0.9 because the probabilities add, but I cannot figure out P(A and B).
0
votes
1answer
36 views

What is the number of inclusive relations?

A binary relation on a set T is inclusive if every element in T relates to at least one element. As an example we can say that {(2, 3), (3, 4)} is not inclusive since 4 does not relate to any ...
0
votes
1answer
38 views

Clarification on a question

I have been reading this problem, Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. That says, Prove that of any 52 integers, ...
0
votes
1answer
40 views

Proving true or false based on discrete math

Discrete math practice problems prove whether true or false If $a^2$ divides $b^2$, then $a^3$ divides $b^4$ I think it is false because it is true that if $a^2$ divides $b^2$ then $a$ divides $b$ ...
0
votes
4answers
75 views

$5$ movies up for $10$ awards, how many ways to distribute

There are $5$ movies up for $10$ awards, how many ways can we distribute these awards? My guess is $\left(\!\!{5\choose 10}\!\!\right)$. Is this correct?
0
votes
5answers
164 views

Prove that if $B-C$ $\subseteq$ $A^c$then $A \cap B \subseteq C$

Let A, B and C three sets. Prove that if $B-C$ $\subseteq$ $A^c$then $A \cap B \subseteq C$ Im trying to prove this with sheer logic and not making use of De Morgans laws etc. Let $y \in ...
0
votes
1answer
60 views

Ergodicity of this Markov Chain

I was recently involved in a debate with a friend over the following graph, and whether it is ergodic or not. In the following diagram, each edge has a strictly positive probability of being travelled ...