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

learn more… | top users | synonyms

1
vote
2answers
37 views

About Recurrence Relations.

I need help in order to solve the following question, Here RR is for Recurrence Relations.
2
votes
1answer
54 views

To what math branches are these assignments related to

I have two different assignments: 1 Hailey was asked to hang seven paintings in a row on the wall. In how many different ways can she arrange them? The answer would be 7! 2 Calculate the amount of ...
0
votes
1answer
50 views

What does the inverted V represent in math

I know that A V B represents Logical disjunction which means A OR B and the result of it is false only when both A and B are false . But I still didn't understand what an inverted V means as shown in ...
1
vote
0answers
64 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
0
votes
1answer
17 views

Count the number of mixes of the card to get come back to origin

Mix a deck of 52 cards by placing them in two parts and take alternate cards from both stacks. Use the cycle notation to show that it only takes 8 mixes to come back to the origin. Since we want ...
0
votes
1answer
28 views

Discrete Math Recurrence with Binary

find the recurrence relation of binary sequence of a length n with no block of three consecutive 0's. I know binary sequences are 0's and 1's but i'm not sure how would the recurrence relation work ...
1
vote
3answers
72 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
0
votes
1answer
20 views

Equivalence relations proof

I need to prove that if $R_1$ and $R_2$ are equivalence relations on the set $A$, then $R_1\cap R_2$ is an equivalence relation. Problem is I dont know how. Please help!
1
vote
1answer
21 views

Number of Binary Operations On a Set

For a group $[S,*]$ where $S=\{a,b\}$, how come there are $2^4$ binary operations that can be defined on $S$ instead of $2^2$? I can only see $a*a$, $a*b$, $b*a$, and $b*b$, which is $4=2^2$. What ...
0
votes
1answer
35 views

Combinatorics Proof

I am having trouble with a combinatorics proof. I need to prove that if $r$ <= $n$ then the number of $r$ - subsets of {1,...,n} is $n!$/$(n-r)!$*$r!$ I really struggle with writing proofs and ...
0
votes
3answers
52 views

Fibonacci numbers

I do have an answer and description from the professor, but I couldn't understand his solution. Can anyone give me an answer and elaborate on how I'm supposed to prove this.
0
votes
1answer
35 views

Discrete Math Proofs, Partial Orders and Equivalence Relations

I am horribly stuck on $3$ proofs for my discrete math class. Any help would be greatly appreciated. Prove that if $R$ is a partial order, then $R^{-1}$ is a partial order Prove that if $R_1$ and ...
0
votes
1answer
35 views

Prove that function f is injective, if function (g o f) is injective as well

I'm sort of stuck with this type of proof. Not quite sure how to go about it. I was wondering if someone could help me out to get started with it. I guess that the two hypotheses I have are these: ...
0
votes
1answer
36 views

Prove a relation is a equivalence

Let $\sim$ be defined so that $a\sim b$ when $a+b$ is even. Is this an equivalence relation? Equivalence relations confuse me a lot, so any help is appreciated!
0
votes
2answers
34 views

Proving something is primitive recursive

I'm trying to prove $f(n) = 2n$ is primitive recursive. I understand that for something to be primitive recursive it must have the following properties: $0(x)=x$ the zero function $s(x)= x+1$ the ...
0
votes
1answer
27 views

Finding discrete maps with prescribed cycle-structure (functional digraph-structure)

I apologize in advance for the naive nature of the following questions. I am also thankful to suggestions for improving the direction of the questions instead of direct answers. Let $f: \mathbb N \to ...
0
votes
6answers
62 views

Prove that for all positive integers $n, 9|(11^ n − 2 ^n )$

Prove that for all positive integers $n, 9|(11^n − 2^n )$ So the base case would be 9 * k = (11*1 - 2 * 1) 9 * k = 9 k = 1 so yes The inductive hypothesis ...
0
votes
1answer
18 views

Graph Isomorphism with Same Degree Sequece

How do I prove that two tree graphs with the same degree sequence are isomorphic (or non isomorphic)? Thanks for the help!
1
vote
0answers
31 views

To solve $ \dfrac1m+\dfrac1n-\dfrac1{mn^2}=\dfrac34$ on all integers

Refering To solve $ \dfrac1m+\dfrac1n-\dfrac1{mn^2}=\dfrac34$ , I think it is an interesting question, if the possible solution are integers, thus How do we find all integers $(m,n)$ such that $ ...
1
vote
2answers
52 views

Prove a 4-cycle exists in a graph with 100 vertices, each with degree of atleast 50

I hope I wrote the question well since it is my attempt at translating from the book. If it isnt clear enough, The question states that in every graph as described in the title a simple cycle of ...
6
votes
1answer
109 views

A group acting on colourings of a set

Suppose I have a set $L$ with some permutation group $G$ defined upon it, which I think of as a symmetry group. I want to consider the set $F$ of functions $f: L \to C$, for some set $C$. It seems ...
1
vote
1answer
72 views

How to prove not an integer?

The question I am trying to figure out is ...
0
votes
0answers
16 views

Expected value of a function hat check n =3

Hat check experiment with 3 hats, six outcomes are 1,2,3 and then 2,1,3 and then 3,2,1 1,3,2 and then 2,3,1 and then 3,1,2 Z is income defined by 3 + 4N (N is how many ...
0
votes
1answer
13 views

Stuck on relations…Equivalence classes

Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if ad = bc. What are the equivalence classes of this relation? I am completely stuck ...
0
votes
2answers
57 views

Trying to understand a probability question

I'm trying to understand a probability question regarding a biased coin, not quite sure how to factor in the biased probability in the question, and also I wanted to make sure the answer is correct, ...
1
vote
1answer
34 views

Finding the variance of hat check experiment

This is the hat check experiment with 3 hats except the outcomes ${1,2,3}$ ${1,3,2}$ ${2,1,3}$ ${3,2,1}$ Have probability $1/5$ and the rest are $1/10$ I have to know the variance on N, which ...
0
votes
1answer
19 views

Sum of a recurrence relation

I do know the answer for the $a$ and $b$. The answer for $b$ is $$2^n - 1.$$ But why is that the answer? Isn't the TOTAL price of the nth position $1 + 2 + 2^2 + \ldots + 2^{n-1}$. How does that ...
0
votes
2answers
20 views

Sequence satisfying a recurrence relation

I do understand that recurrence relation is recursion. I understand the idea, but I would just like to know how to prove this. I would really appreciate if you show me how to do this problem and ...
2
votes
2answers
65 views

Purely “discrete” PDEs?

Usually, one formulates a system of continuous PDEs and then discretizes it in order to approximately solve it. Is there a view point that instead formulates a system of "discrete" PDEs, which ...
5
votes
1answer
57 views

Writing in 1993, a researcher noted that it is hard to prove things about a cellular automata model - has this changed?

Leah Edelstein-Keshet in her 1993 article Cellular automata approaches to biological modelling writes: We do not believe that CA should be viewed as a replacement for rigorous mathematical models. ...
0
votes
2answers
56 views

Boolean algebra. For all x, y, and z in B, if x + y = x + z and x × y = x × z, then y = z.

In the statements below, $B$ is a Boolean algebra with $\times$ and $+$ for binary operations and ($\bar{a}$)is the complement of $a$. 4.) For all $x$, $y$, and $z$ in $B$, if $x + y = x + z$ and $x ...
1
vote
1answer
30 views

For all $a$ and $b$ in $B$, $(a \times b) + a = a$.

In the statements below, $B$ is a boolean algebra with $×$ and $+$ for binary operations. 3.) For all $a$ and $b$ in $B$, $(a ×b) + a = a$. This is what I have as an answer. Can someone confirm ...
0
votes
1answer
22 views

Why is this a boolean algebra

Let $A = \{a,b\}$. The $\mathcal P(A) = \{\emptyset,\{a\},\{b\},A\}$. Let $+$ be $\cup$, $\cdot$ be $\cap$, complement be set complement, $1$ be $A$, and $0$ be $\emptyset$. I need to explain why ...
10
votes
1answer
523 views

Interview Question Asked In yahoo

Can you find the smallest positive number such that if you shuffle the digits of the number in a particular order, the shuffled number becomes twice the original number. Source: ...
-1
votes
3answers
60 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
1
vote
1answer
32 views

Number of relations from A to B with specific domain

I have two sets $A = \{1,2,3,4\}$, $B = \{5,6,7,8,9\}$ I need to find the number of relations from $A$ to $B$ which includes $\{1,2,3\}$ in the domain. It says to use the Inclusion–exclusion ...
1
vote
1answer
43 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
0answers
42 views

Random looking Gray Codes or Hamiltonian Cycles on Hypercubes

Cyclic Gray codes come in many flavors and correspond 1-1 to Hamiltonian cycles on hypercubes. I would like to find a type that looks like a random walk on the hypercube. In a sense this is an ...
1
vote
1answer
40 views

What is the number of self dual boolean functions?

The dual of a Boolean function $F(x_1,x_2 \dots x_n,+,\bullet)$, written as $F^D$, is the same expression as that of $F$ with $+$ and $\bullet$ swapped. $F$ is said to be self-dual if $F=F^D$. What is ...
0
votes
1answer
59 views

finding the pattern [closed]

Hi Can Someone help me solve the below Back in the day men always wore hats and when they went to a club they would have a hat-check girl store their hats. If n men checked hats, in how many ...
0
votes
1answer
54 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
2answers
49 views

show that $\det(A)=0$ in this case

(a) Let $x$ and $y$ be $n\times 1$ matrices, $n \ge 1$, and let $A=xy^T$. Show that $\det(A)=0$. (b) Explain why the statment in part (a) is false if $n=1$.
0
votes
1answer
113 views

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer ...
0
votes
0answers
41 views

Describe the language generated by the grammar $G = \{\Sigma, \Delta\ S, I \} $

I need to describe the language generated by the grammar $G = \{\Sigma, \Delta\ S, I \} $, where $$\Sigma=\{0,1\epsilon \}, \Delta = \{S,X,Y,Z\}$$ and $$I = \{S \to0X|1Y, x \to1Y|1Z, Y \to0X|0Z, Z ...
1
vote
1answer
41 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
0
votes
1answer
70 views

G as a graph without self loops and parallel edges with n vertices and m edges

EDITED to include c. Could someone help me understand this problem? I haven't been able to comprehend what I am supposed to do here. 1) Let G be a graph without self loops and parallel edges with n ...
0
votes
3answers
87 views

combination question ASAP required

Hi Can someone help me solve this please? In the clock game Alice and Bob both start at 12 o’ clock. During a move Alice moves 5 hours clockwise on the clock-face and Bob moves 9 hours ...
1
vote
1answer
76 views

Proof using addition and multiplication axioms

I'm working on addition and multiplication axioms of integers for discrete math. I'm trying to prove (k - m) + (m - n) = k - n. The first step I took was this ...
0
votes
1answer
28 views

Find the language of $\sum^*$

For the alphabet $\sum = \{0,1\}$, let $A,B,C \subseteq \sum^*$ be the languages below. $i. A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ $ii. B = \{w \in \sum^*|||w|| \ge 2 \}$ $ii. C = \{w \in ...
1
vote
1answer
46 views

need help with Binary Patterns.

Write 0.1, 0.2, and 0.3 in fixed point notation as repeating binary patterns. Use your ability to sum an infinite geometric series ...