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

learn more… | top users | synonyms

1
vote
0answers
84 views

Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
3
votes
2answers
118 views

Symmetric Groups and Commutativity

I just finished my homework which involved, among many things, the following question: Let $S_{3}$ be the symmetric group $\{1,2,3\}$. Determine the number of elements that commute with (23). Now, ...
2
votes
2answers
124 views

Let $A$ be a set, $R$ an empty relation on $A$, what is $A/R$?

Let $A=\{0,1,2\}$ be a set and $R=\{\}$. I know that $R$ is not an equivalence relation, but does it have to be? What is $A/R$ if $R$ is empty? Examples: $R_1=\{(0,0),(1,1),(2,2)\}$, $A/R_1=\{[0], ...
2
votes
0answers
137 views

Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
0
votes
1answer
938 views

Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in ...
1
vote
1answer
29 views

Convergence of Discrete Poisson equation

Are there any sources that show the convergence of the discrete poisson equation? To be clear, by convergence I mean: given the poisson equation in a domain $ M \subset R^2 $, $\Delta \psi = f $, one ...
1
vote
2answers
171 views

Map-Coloring Problem

When we are faced with map-coloring problem, why do we allow countries that meet at only one point to receive the same color? Is it because they do not share the same boundaries or common boundaries? ...
2
votes
2answers
1k views

How do I prove the arithmetic-geometric mean inequality?

I am following along with this bare-bones proof of the arithmetic-geometric mean inequality with two real numbers. I'm having difficulty understanding the logic behind this step: $$ ...
4
votes
1answer
96 views

Finding maximum score in a “bubble pop” game

Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
0
votes
1answer
37 views

Do these two expressions mean the same?

So for a given database we have the sets Persons, Married, Women, Men and Children. I want to express all Women who are not Children and not Married: $$Women\setminus \left ( married \cup children ...
1
vote
1answer
29 views

Prove the existence of a row and a column in the Boolean matrix which satisfy the conditions

"Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove that there is a row and a column such that when the total entries of the row and column are added, the sum is greater than 13." I have ...
2
votes
5answers
183 views

Solving the recurrence relation [closed]

I'm interested in learning how can we solve this linear non-homogeneous recurrence relation? $$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
0
votes
1answer
67 views

Finding a reccurence relation for the following problem

A circular disk is cut into n distint sectors, each shaped liek a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
-2
votes
1answer
137 views

Given the following recurrence relation, prove using mathematical induction

How can we prove this using mathematical induction? $m_1 = 0$ $m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$ Prove using mathematical induction that ...
0
votes
6answers
2k views

Finding the number of subsets of S

How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6? Thanks!
1
vote
2answers
119 views

Use the binomial theorem to expand

How can we expand this using the binomial theorem? $(x^2 + 1/x)^7$
3
votes
3answers
520 views

Why all odd numbers not ending with 5 divide exactly into a number comprising only 9's?

Help me!!It's really frustrating I can't understand this simple thing.The maths instructor in my video,the renowned Arthur Benjamin,states (clip linked below) the following: ...
4
votes
0answers
51 views

Nimber of selective compound games

Background/Definitions. Let $\alpha,\beta$ ordinal numbers. The Hessenberg sum $\alpha \# \beta$ is defined recursively as the smallest ordinal which is $>\alpha' \# \beta$ and $> \alpha \# ...
1
vote
1answer
93 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
1answer
55 views

Proof involving functions.

Consider two functions $f\colon A \to B$ and $g\colon B \to C$. How can I prove the following? If $f$ and $g$ are one-to-one, then the composition function $g \circ f$ is one-to-one. If $f$ and ...
1
vote
1answer
383 views

Relations. Check whether symmetric,reflexive or transitive .?

Q6. Let R and S be relations on a set A. Assuming A has at least three elements, state whether each of the following statements is true or false. If it is false, give a counterexample on the set A = ...
0
votes
3answers
98 views

Set Theory: General Intersection

How to properly prove the following: For all integers positive integers n, if A1, A2,... and B are sets, then
12
votes
2answers
674 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
1
vote
1answer
79 views

Discrete math problem confusion.

: But I'm still confused how we are are going to write the final answer. Your help will be appreciated. thanks.
0
votes
2answers
117 views

Prove that if $A\triangle B = C\triangle B$, then $A = C$

I am working with proofs in discrete math. Help to prove: For the sets $A$ and $B$, we define the symmetric difference of $A$ and $B$ to be $A \triangle B = (A-B)\cup(B-A).$ Prove that if $A ...
1
vote
5answers
354 views

Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square.

Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square. What I have done: This has to either be done with contradiction or contraposition, I was thinking ...
-4
votes
2answers
1k views

Proving the number of edges in the complete graph Kn

I am trying to find the number of edges in the complete graph: $$K_n=\sum_{i=0}^{n-1} i$$
2
votes
3answers
68 views

Proofs and Number theory

I am needing help proving the following: For any integer $n$, $n^2$ + 5 is not divisible by $4$ I am aware that an integer $x$ is divisible by integer $y$ if there exists integer $k$ such that ...
1
vote
0answers
36 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
3answers
106 views

The number of bijections $f$ of $\{1, 2,…, n\}$ such that $f(i) \ne i$ for any $i$

Show that the number of bijections $f$ of $\{1, 2,..., n\}$ such that $f(i) \ne i$ for any $i$ is equal to $$\sum_{j=0}^{n}(-1)^j\frac{n!}{j!}.$$ Can I get some help for the above problem? I am ...
5
votes
1answer
50 views

A graph of order $2n$ for which all vertices have degree $\geq n$ may be partitioned into adjacent pairs.

Suppose that $G$ is a graph with $2n$ vertices for which every vertex has degree at least $n$. Prove that we can partition $V(G)$ into pairs such that the two vertices in each pair are adjacent.
1
vote
2answers
53 views

Show that one person must have x amount of dollars

A group of six friends discover they have a total of \$21.61 with them on a trip to the movies. Show that one or more of them must have at least \$3.61. How should I approach this problem? I can see ...
8
votes
4answers
770 views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
2
votes
1answer
244 views

How many graphs are possible on 5 vertices w/ no multiple edges or loops?

I think the answer may be $5! / (5-2)! 2!$ but I'm not sure.
1
vote
1answer
94 views

How many times can a student skip class in a 14 weeks semester?

In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
3
votes
1answer
144 views

A combinatorial identity with Pochhammer's symbol

Let $m,k$ be an positive integers with $k\le m$. I am trying to prove $$\sum_{j=0}^k{\frac{1}{2}\choose k-j}\frac{2^{2j}(m+j)!}{(m-j)!(2j)!}=\frac{P(n,k)}{(2k)!}$$ where $n=2m+1$ and ...
2
votes
1answer
76 views

A combinatorial identity related to Chebyshev differential equation

Let $m,k$ be an positive integers with $k\le m$. Does anyone have a proof that $$\sum_{j=k}^m {2m+1\choose 2j+1}{j\choose k}=\frac{2^{2(m-k)}(2m-k)!}{(2m-2k)!k!}?$$ This is related to Chebyshev ...
1
vote
0answers
29 views

Two-dimensional Topology and Ordering

This question came up for me when thinking about an answer to this: http://stackoverflow.com/questions/16326318/finding-blocks-in-arrays. I had the idea of listing the 1's, for example: ...
1
vote
1answer
266 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
2
votes
1answer
188 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
0
votes
1answer
55 views

Conditional Probability, weather related

If it is raining, I take my car to work 90% of the time, I take my bike 9%, and I walk 1%. If it is not raining, I take my car 10%, bike 60%, and walk 30%. What is the probability it is raining if I ...
0
votes
1answer
29 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
8
votes
1answer
200 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is ...
1
vote
0answers
57 views

Non-independent two consecutive draws from two urns

Suppose there are two urns: in urn A, there are r red balls and w white balls. In urn B, there are b black balls. Suppose we do the following experiment: draw k balls from urn A. Among those k balls, ...
7
votes
2answers
215 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
2
votes
1answer
82 views

Proving this realtion is not a transitive relation

I have trouble proving how the following statement is false: The relation $g = \{\,(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\,\}$ is transitive. I know you have to use $yRx$, $zRy$, and $xRz$, but I'm ...
0
votes
0answers
138 views

Replace a continuous probability distribution with a discrete one

Say one wants to fit a curve $f(x)$ to a set of noisy data points $(x_i, y_i)$. If the error for each point $y_i$ is assumed to be normally distributed with variance $\sigma_i^2$, one wants to find ...
1
vote
2answers
79 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
-1
votes
1answer
1k views

Proof of divisibility by 2 and 3 if and only if divisible by 6

I can't find a way of proving that: For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6. I’m not sure where to go from here. Any help would be great!
3
votes
1answer
231 views

diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...