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

learn more… | top users | synonyms

0
votes
1answer
37 views

Path counting discrete

I need help understanding a simple concept. Lets say you're given a problem where you start at (0,0) on a 2D grid and want to count the number of paths to (8,4). Would I be following the combinations ...
0
votes
2answers
64 views

Proving congruent statement for a prime number $p>10$

I have the next statement that has to be proved: Let $p$ be a prime number where $p>10$. Prove that $p-2$ has an inverse module $p$, this is, a number $q$ exists where $(p-2)q \equiv 1\mod(p)$. I ...
0
votes
2answers
264 views

Continuous functions from real numbers to discrete space

One of my homework problems is this: "Let X = $\mathbb{R} \!\,$ with the usual metric and let X′ be a discrete metric space. Describe all continuous functions from X to X′." A function f : X ...
0
votes
1answer
16 views

Number of equivalence relations on a set with fixed class

For A={a,b,c,d,e,f}, how much equivalence relations can we get if a,b and c are in relation? The total is: $\sum_{k=1}^6 S(6,k)$. But since a,b and c are already in the same class, i would say the ...
0
votes
1answer
123 views

recursive formula for bit binary strings

Find a recursive formula for the number of n bit binary strings that contain the substring 10. How many such strings of length 8 exist? Find a closed form for the number of n bit binary strings that ...
0
votes
1answer
28 views

Use induction to prove for all $n \ge 1$, if $f(x) = ax^n$ then$ f '(x) = anx^{n-1}$.

So for the base case: $n=1$ $$F'(1) = a(1)x^0 = a$$ So this checks out. So I can assume: $f(x) = ax^k$ then $f'(x) = a\ k\ x^{k-1}$ For the induction $n = k+1$. $f'(x) = a(k+1)\ x^{(k+1)-1}$ ...
0
votes
1answer
263 views

Find the equivalence class of 0

R is a relation defined on the integers by $(a,b) \in R$ is $a^2-b^2$ and is divisible by 3. I set a or b to zero to get all the negative and positive values in the equivalence class. Although I want ...
0
votes
1answer
41 views

If $A$, $B$, and $C$ are sets, the only way that $A\cup C = B \cup C$ is if $A=B$

If $A$, $B$, and $C$ are three sets, then the only way that $A\cup C$ can equal $B\cup C$ is $A = B$. I believe this statement is false and here is why: Let $A=\{1\}$, $B=\{2\}$, and ...
0
votes
1answer
31 views

counting and probability question

I need help figuring out this exercise. I am stuck on it and am not sure how to get it started. Any help is appreciated. Exercise: An instructor gives an exam with 14 questions. Students are allowed ...
0
votes
1answer
253 views

Number of possible combination of all subsequences of two strings

Suppose, two strings $A$ and $B$ of length $x$ and $y$ are given. Now, I have to find out number of possible combination of sub-sequences of these two strings. For example, let A="abc"; clearly the ...
0
votes
1answer
61 views

Induction and typical pigeonhole principle

Let $n,\,k,\,r,\,s\in\mathbb{N}$ and $0\leq r,s<n$. We have $nk+r$ objects placed in $n$ containers. Show that we can choose $s$ containers such that there is at least $sk+\min{\{r,\,s\}}$ objects ...
0
votes
1answer
26 views

Congruence Inconsistency

I have a question about congruency... I understand that: $$ 12 \equiv 7 \bmod 5 $$ $$ \text {is equivalent to:} $$ $$ 5|12-7 $$ but this doesn't seem to hold for: $$ 2 \equiv 8 \bmod 6 $$ $$ \text ...
0
votes
1answer
47 views

is “N -> N where g(n) = all integers > n” a function?

I know this is probably not the best question, but I'm sitting on the fence about my answer because I'm not 100% sure of "Natural Numbers" definition. Does it include negatives or is it strictly ...
0
votes
1answer
39 views

Discrete Math- Ways to order men and women in a circle

The question is: In how many ways can you order 2 men and 5 women (when two of these women are married to the two men) in a round circle such that every men will sit next to his wife? My calculation ...
0
votes
1answer
55 views

Prove that the set $B = \{0,1\}^8$ forms a group

Prove that the set $B = \{0,1\}^8$ forms a group under the composition operator: $g \circ f$ is defined by $(g \circ f)(x) = g(f(x))$
0
votes
2answers
93 views

Solve discrete Math Problem using abstract algebra, postage problem?

The question I am looking at is not very hard: Determine which amounts of postage can be written with $5$ and $6$ cent stamps. To determine the amount, use a brute force way to solve it. Counting ...
0
votes
2answers
42 views

Probability of seven coins

Flip seven fair coins. Describe the state space for this situation. define a random variable corresponding to the number of heads that show when the coins land. What is the probability that this ...
0
votes
1answer
34 views

Discrete Math need some help!

I'm taking discrete math course now and need some help on this question. THX!! T/F or unknown? There is a function that is both $O(n^2)$ and $\Omega(n^3)$. Given two functions $f(n)$ and $g(n)$, ...
0
votes
1answer
143 views

Compute discrete logarithm

I am stuck in a problem, where i have to compute discrete logarithm without use of brute force. Here is the problem: Given is a prime number $p=21495809$. Find $x$, if $7^{x}=14750571\, mod\, p$. ...
0
votes
1answer
32 views

Proving a complex summation identity

Suppose $b$s are ordered like $b_{i}\geq b_{i-1}$. Then in a research article it says $ ...
0
votes
1answer
84 views

Discrete Math: Recursive Functions

You are given the following recursive definition defining a set of strings. 1∈S; x∈S → x11∈S. What are the 4 shortest members of the set? What does x11∈S mean?
0
votes
1answer
46 views

Dependent Probability Question with Cards

Here's my question: Tom and Harry are dealt fi ve cards each from the same 52-card deck. Calculate the probability that Tom gets a flush (fi ve cards of the same suit) and Harry gets four of a ...
0
votes
1answer
179 views

Consider all colorings of the edges of K6 such that every edge is either colored red or blue…

Consider all colorings of the edges of K6 such that every edge is either colored red or blue. Prove or disprove: there always exist at least two monochromatic triangles in any 2-coloring of the edges ...
0
votes
1answer
87 views

Modular arithmetic and one-to-one functions

Let $S = \{0, 1, 2, 3, · · · , 99\}$ . For each of the following functions $f : S \rightarrow S$ , determine whether it is one-to-one and onto, by computing its values for all $k ∈ S$: Function 1: ...
0
votes
2answers
43 views

Find a sequence which has an even number of odd terms, and yet the sequence is not a graph score.

Construct an example of a sequence of length n in which each term is some of the numbers 1, 2, . . . , n − 1 and which has an even number of odd terms, and yet the sequence is not a graph score. ...
0
votes
3answers
25 views

Discrete math sets help?

How would I do this question? suppose U = {1,2...,9}, A= all multiples of 2, B = all multiples of 3, and C = {3,4,5,6,7}. Find C-(B - A). I really don't know how I would approach this question so ...
0
votes
1answer
57 views

$5^a - 5^b$ is divisible by $n$ (prove)

Prove that for every n natural number exist natural numbers $a,b \leq 4n, a\not= b $, which accomplish, that number $ 5^a - 5^b $ is divisible by n. How many of these pairs exist? Help please, I'm ...
0
votes
1answer
58 views

Help with Cartesian products

I'm given the cartesian products $(A \times B) \times (C \times D)$ and $A \times (B \times C) \times D$ Explain why they are not the same. Then explain why they essentially are the same, by giving ...
0
votes
1answer
249 views

Bijective function proof

I'm having trouble with doing two bijective proofs. I understand bijection and how it works, but I'm just unsure how to word the proof using formulas to find specific values were function are/aren't ...
0
votes
1answer
35 views

How to find matrix $\left(\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{matrix}\right)$.

I need to find all $a_{11}$ to $a_{22}$ can anyone help me pls. $2a_{11}+3a_{21}= 3$ $2a_{12}+3a_{22}= 0$ $1a_{11}+4a_{21}= 1$ $1a_{12}+4a_{22}= 2$ I am stuck here don't know how to calculate ...
0
votes
1answer
85 views

Intersection of a Infinite Collection of Sets - null set or infinity?

Let's say we have a collection of sets $\bigcap_{i=1}^\infty A_i$ where $A_i=[i,\infty]$. In other words: $$ \bigcap_{i=1}^\infty A_i = [1,\infty] \cap [2,\infty] \cap [3,\infty] \cap ... ...
0
votes
2answers
61 views

Pigeonhole question and generalization

Let H be a regular hexagon with side length 1 unit. (a) Show that if more than 6 points are speci ed inside H then the points of at least one pair of them are at most 1 unit apart. (b) State and ...
0
votes
2answers
45 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
0
votes
3answers
57 views

Help required on strong induction

Given: $a_{1} = a_{2}=1, a_{n} = 2a_{n-1} + a_{n-2}, n>2$ for $n\in N$ Can someone explain how this equation simplifies to this answer? I don't understand this summation. $$6(2a_{k-2}+a_{k-3}) = ...
0
votes
1answer
66 views

Calculate time needed to solve problem

I have this question in an assignment and I was wondering if I could get help verifying whether my approach to this question is correct... The question is as follow: Suppose that an algorithm uses ...
0
votes
1answer
85 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
0
votes
1answer
68 views

Clarification on proof by contradiction in a directed graph

Let's say that I have a finite directed graph. Also assume that every vertex in the graph has only one unique closest neighbor. How can I prove that the maximum length of any cycle in this graph is 2? ...
0
votes
1answer
33 views

Proving antisymmetry for this partial ordered set

I need to prove the anti-symmetric property of the following relation (the set is the cross-product of all positive integers). (x1,x2) R (y1,y2) <=> EITHER (x1 + x2 < y1 + y2) OR (x1 + x2 = y1 ...
0
votes
1answer
37 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...
0
votes
1answer
100 views

What's the probability that nine people were born in the same two months (but not the same month)?

Find the probability that nine people were born in the same two months (but not all in the same month). No clue how to approach this. I was thinking well you have to choose 8 out of the 9 people and ...
0
votes
1answer
28 views

In which the real number system that sum of geometric progression involve? [closed]

I want to know about sum of geometric progression a and r Are they real number it integer .. Etc ?
0
votes
1answer
75 views

Inserting values left to right in a binary search tree

What does it mean to build a binary search tree by inserting values from left to right starting from an empty tree? The "left to right" part confuses me..I know how to build one by normally inserting ...
0
votes
1answer
66 views

Let $P$ be the statement: "For all sets $A$, $B$ and $C$, if $A ⊆ B\cup C$ then $A-B=\emptyset$. Is $P$ true? Prove your answer.

I drew a Venn diagram and know that this statement is false I just don't know how to prove it. I don't need hints I really need to know the full proof. Is the converse true or false? Proof? Thanks a ...
0
votes
1answer
131 views

Evaluating a sum with binomial coefficients

I have come across the following sum evoking the binomial theorem: $$\sum_{k=1}^n {n \choose k} \frac{1}{k^r} a^k b^{n-k},$$ where $r > 0$ is a positive real constant and $a,b \in \mathbb{R}$ are ...
0
votes
2answers
52 views

Interesting question posted earlier by another user need help solving

I've been trying to solve a problem a user posted that I thought was interesting. Considered a lucky number, the Thai government decides to issue coins of 9 baht. Show that, forall suciently large ...
0
votes
1answer
70 views

A few questions relating to counting for midterm practise exam?

I'm doing some questions for my midterm practise exam (multiple choice) for discrete structures and would appreciate some help (My answer is bolded): Using the 26-letter alphabet {a,b,c,...,z}, how ...
0
votes
1answer
169 views

Divisibility Discrete Math

For all integers a, b, c, if a | (b + c), then a | b and a | c True or false? Im assuming it's false because if you make a=2 b=3 and c=4, it won't work
0
votes
2answers
74 views

Definition of permutation

Following is one of the definition of a permutation of a nonempty set: The permutation of a nonempty set A is an ordered list of elements of A. Following is another definition of a permutation of a ...
0
votes
1answer
66 views

Numbers of different ways to distribute $m$ balls into $n$ boxes?

So my question is this: assuming I have $m$ balls how many ways there is to divide them into $n$ boxes (at least one ball for each box)? For example if I have $7$ balls and I want to split them into ...
0
votes
2answers
243 views

Discrete Math - Combinatorics question about number of paths in an m x n lattice from one corner to another

Explain why the number of shortest paths in an $m \times n$ lattice from one corner to another is $${s \choose r}$$ where $$s = \text{total # of steps$\qquad$ and $\qquad r= $ total # of right ...