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

learn more… | top users | synonyms

0
votes
1answer
23 views

Graph Theory - Complete graphs

I am having trouble with this question... Find the expected number of copies of $k_k$ in $G(n,1/2)$. Can anyone help!?
4
votes
4answers
65 views

Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$

An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity: $$ {n \choose 2} + {n+1 \choose 2} = n^2 $$ The algebraic solution is ...
0
votes
0answers
27 views

Graph theory proof explanation.

For a homework question, I have found a proof for a problem. However the answer does not seem to make sense to me. Here is the following question: Let G be a k -regular graph with n vertices and k ...
0
votes
1answer
17 views

Combinations of bit strings of length 9

How many bit strings of length $9$ contain exactly three $1s$? $10*10*10*9^6=531441000$ But then those first $1's$ don't necessarily have to be the first 3 digits. They can be elsewhere in the digit ...
0
votes
1answer
31 views

Equivalence relation and equivalence class question

Show that the relation $\sim$ defined on the set $X = \mathbb{N} \times \mathbb{N} = \{(a, b) : a \in \mathbb{N}; b \in \mathbb{N}\}$ as $(a,b) \sim (c,d)$ if and only if $a + d = c + b$ is an ...
0
votes
0answers
8 views

How to proove these properties of compositions of relations?

From wikipedia: If R and S are injective, then S ∘ R is injective, which conversely implies only the injectivity of R. If R and S are surjective, then S ∘ R is surjective, which conversely implies ...
0
votes
1answer
25 views

Prove by induction $T_n$ is odd

Taken from MIT's OpenCourseWare site for Discrete Math: We define the following recurrence for $n ≥ 0$: $$T_{n+2} = T_{n+1} + 2T_{n}$$ where, $T_{0} = T_{1} = 1$ (a) Prove by induction ...
17
votes
1answer
465 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
0
votes
0answers
10 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
1
vote
2answers
32 views

Prove that $|x+y| \leq |x|+|y|$ [duplicate]

How to Prove the triangle inequality which says for all x (no matter how big or small) and for all y (no matter its size) in the set of irrational+rational numbers, this holds: $|x+y| \leq |x|+|y|$
0
votes
0answers
10 views

Set Relations, Partial Orders, and Hasse Diagrams Question.

A question about elements of a set, binary relations, and hasse diagrams. Bear with the set-up as I'm just copying the question from the assignment. Let me know how to improve my answers to be more ...
0
votes
1answer
19 views

Probability Discrete Math

{1,2,3,4,5,6,7,8,9} What is the probability that the sum of any of these three numbers is odd? I know that I should use $ n \choose k $ somehow and I know that my professor used this as his equation: ...
1
vote
1answer
40 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
2
votes
1answer
19 views

In how many ways can letters in mathematics be ordered with restrictions?

I've been stuck on these for a while. Please guide me through all the steps because I actually want to understand this. I've got an exam coming up. Consider the letters in the word "MATHEMATICS". In ...
0
votes
3answers
23 views

Big O question related to nested loop

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?
0
votes
1answer
21 views

Combinations and Permutations

What is the probability that a poker hand has five cards each with a different rank? P(5 cards different rank)= P(No pair)+ P(Straight)+ P(Flush) $.50118+.00197+.00392= .50707 =50.7$ percent This ...
0
votes
1answer
19 views

Determine the languages for the given alphabet

I need some help figuring out this exercise. 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 ...
0
votes
1answer
23 views

Permutations and Combinations

In a group of 30 ball bearings, 5 are defective. If 10 ball bearings are chosen at random, a) what is the probability that none of them are defective? b) what is the probability that two or more ...
2
votes
4answers
57 views

Generating Functions in Discrete Math

a)Find the coefficient of $x^3y^4$ in $(2x + 5y)^7$. b) Find the coefficient of $x^5$ in $(3x -1)(2x +1)^8$. I know this has to do with generating functions , but i'm not sure how to start with this ...
4
votes
3answers
45 views

Stars and bars (combinatorics) with multiple bounds

Count the number of solutions to the following: $$x_1+x_2+\cdots+x_5=45$$ when: $1$. $x_1+x_2>0$, $x_2+x_3>0$, $x_3+x_4>0$ $2$. $x_1+x_2>0$, $x_2+x_3>0$, $x_4+x_5>1$ ...
1
vote
2answers
26 views

Permutations and Combinations

Show that $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ...+(-1)^k * \binom{n}{k} = (-1)^k * \binom{n-1}{k}$. I know this has to do with permutations and combination problems, but I'm not sure how ...
7
votes
1answer
68 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
0
votes
2answers
112 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
0
votes
1answer
18 views

Permutations and Combinations

What is the probability that a 3-element subset selected at random from the set {1,2,3, … , 10} a) contains the integer 7? b) has 7 as its largest element? I know this deals with permutation and ...
0
votes
0answers
12 views

Variation of Nim: Player who takes last match loses

Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone! ...
0
votes
1answer
25 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
1answer
23 views

Symmetric relation , why are these symmetric?

$R_1 = \{(a,b)$ such that $a \leq b \}$ $R_2 = \{(a,b)$ such that $a>b \}$ $R_3 = \{(a,b)$ such that $a=b$ or $a=-b \}$ $R_4 = \{(a,b)$ such that $a=b \}$ $R_5 = \{(a,b)$ such that $a=1+b \}$ ...
1
vote
1answer
17 views

With how many ways can there be $n$ couplings between $n$ men and $n$ women?

Could you help me with the following exercise? Could you give me a hint? With how many ways can there be $n$ couplings between $n$ men and $n$ women?
1
vote
2answers
36 views

Combinations and Permutations

How many arrangements of the letters in DIGITAL have two consecutive I’s? I know this is a type combination, permutation problem but i'm a little unclear how to start with this problem.
2
votes
1answer
18 views

How does a cropping of a 2D matrix/image affect its DCT transform?

I apologize in advance: since I am not a mathematician, maybe my question is not well defined, but I hope that some of you will still understand my meaning. Given a 2D matrix, or an image of ...
2
votes
1answer
57 views

Which non-Abelian finite groups contain the two specific centralizers? - part II

This is a question requiring the good knowledge of group theory: (Q1) Which finite groups $G$ contains some specific centralizers isomorphic to both of these two groups (but may contain other ...
1
vote
1answer
30 views

Tanh function representation for conditional function

I have a condtion as $$T(x)= \begin{cases} -1 & \text{if }x <a \\ 0 & \text{if }a\le x \le b \\ 1 & \text{if }x >b \end{cases} $$ I want to approximate the above condition as ...
1
vote
2answers
78 views

How to prove a function from $\mathbb N\times \mathbb N$ to $\mathbb N$ is bijective. [duplicate]

I am having trouble with this problem: $f\colon \mathbb N\times \mathbb N \rightarrow \mathbb N$ is defined by $f(i,j)=\dfrac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection from ...
1
vote
1answer
36 views

How to represent the condition by mathematical

I have a condtion as $$T(x)= \begin{cases} -1 & \text{if }x <a \\ 0 & \text{if }a\le x \le b \\ 1 & \text{if }x >b \end{cases} $$ I want to represent the above condition as one ...
0
votes
1answer
24 views

How do I use Graph theory to determine the minimum amount of moves needed to swap chess pieces?

On 3x4 chessboard (see below) there are 3 Black knights (B B B) and 3 white knights (WWW), exchange knights in the min # of turns (hint: use graph representation) B B B -> WWW 0 0 0 -> 0 0 0 0 0 0 ...
0
votes
0answers
3 views

some past paper questions in Discrete Time Systems i couldnt solve.

I am working on past papers of my exam which is in two days, there was one particular year , 2009, which I could not solve quite a lot of its questions... i only could solve 5 out of 10, can anyone ...
-3
votes
0answers
21 views

how to solve the current problem of evaluating limits approching zero [on hold]

$\sum{(\dfrac{1}{pi}\cdot \tau\cdot \alpha)X}, $$ \ \ \sum(\sqrt{(1-(\mho/2\alpha\tau) {k_a}^2)})$ first summation limit is $\tau=0$ second summation limit is $\mho=-2\alpha\tau$ to $+2 \alpha \tau$ ...
-2
votes
0answers
42 views

Boole's functions' domain is D = {1, 2, 3, 4}. Find ∃xF(x, 2), when F(x, y) = 1100 1111 0011 0101. [on hold]

The problem is, I actually do not understand this problem very well. When the logical function is given, making truth table is not a problem for me at all. I wonder, if this exercise requires to make ...
1
vote
2answers
35 views

Counting problem involving sets

Let $S$ be a set of size $37$, and let $x$,$y$, and $z$ be three distinct elements of $S$. How many subsets of $S$ are there that contain x and $y$, but do not contain $z$? How many subsets of $S$ ...
0
votes
1answer
25 views

When proving a partial order relation is a total order do we have assume both elements are distinct?

Consider the "divides" relation on the set $A=\lbrace 1,2,2^2,.\;.\;.,2^n\rbrace$, where $n$ is a non-negative integer. Prove that this relation is a total order on $A$. First we prove $A$ is a ...
0
votes
2answers
30 views

Different ways of arranging a group of 10 people

In how many ways can a photographer arrange $8$ people in a row from a family of $10$ people, if (a) the bride and groom are in the photo. This would be $9*8*7*6*5*4*3*2*1=362880$, correct? (b) the ...
0
votes
0answers
13 views

How do I draw a Hasse Diagram for the given PO-set?

Copied from my homework: Draw a Hasse Diagram for the PO-set: ({$p, r, p \lor r, p \land r, p \to r$}, $\Rightarrow$) where {$p, r, p \lor r, p \land r, p \to r$} is a set of propositions and ...
0
votes
2answers
26 views

Proving that a set is denumerable without using a particular theorem

this question may seem like a duplicate of another one that I asked, but it is not. In this question, I am not allowed to use the Theorem which states: Every infinite subset of a denumerable set is ...
0
votes
1answer
24 views

Equivalence Relations and distinct equivalence classes

$A=\lbrace(1,3),(2,4),(-4,-8),(3,9),(1,5),(3,6)\rbrace$. $R$ is defined on $A$ as follows: For all $(a, b)\;(c, d) \in A$, $(a, b) R (c, d) \iff ad=bc$ I know what they are asking but I cannot see ...
1
vote
2answers
44 views

Proving that a function from $N\times N$ to $N$ is bijective.

I am stuck on this problem: Define $f: N\times N \rightarrow N$ by $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically ...
0
votes
1answer
16 views

How many way can 7 friends line up if there are certain conditions?

How many ways can 7 friends line up if Ann, Beth, and Chris have to stand next to each other where Ann is ahead of Beth and Beth is ahead of Chris? Would it simply be $5*4*3*2*1=120$ ways? Expanding ...
0
votes
0answers
36 views

Proving that the set of irrational numbers is uncountable [duplicate]

Work: Assume that the set of irrational numbers is countable. Since $Q$ is infinite, it is therefore denumerable. Therefore, there exists a bijective function $f: N \rightarrow Q$. From here I am ...
0
votes
2answers
27 views

How many strings of 8 digits end with an even digit?

So there are $10$ combinations for each digit except the last which has 5 possibilities ($0,2,4,6,8$). Thus $10*10*10*10*10*10*10*5=50000000$ combinations right? As a follow up, how many strings of 8 ...
1
vote
1answer
49 views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
-1
votes
0answers
18 views