The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

0
votes
2answers
36 views

How many elements in $X$ are of the form $3k + 1$ for some integer $k$?

Consider the set $X={300,301,302,...,29999,30000}$ (the set of all integers from $300$ to $30,000$ inclusive.) You do not need to simplify the numeric answers. How many elements in $X$ are of the ...
1
vote
0answers
39 views

How to find the upper bound of a binomial coefficient by using binomial theorem?

I have a task to find a upper bound of the binomial coefficient for all $r \leq \frac{n}{2}$. I've already obtained by using such relation: $$\frac{\sum_{k=0}^{r}\binom{n}{k}}{\binom{n}{r}}$$ Which ...
1
vote
2answers
24 views

Finding the cardinality of a cartesian product of a set and a cartesian product.

$A = \{0, 1, \{2, 3, 4\}\}$ $B = \{1, 5\}$ $C = B \times \mathbb{N}$ What is the cardinality of $A \times C$? I know the enumeration of $A \times C$ is $\{(0,(1,0)), (0,(1,1)), (0,(1,2))\ldots ...
1
vote
0answers
42 views

Permutation as a product of generators of the permutation group

Let $G$ be a permutation group, generated by $g_1,\ldots,g_n$. And let $h$ be in $G$. Example: $G=\langle (12)(34),(123)\rangle$ and $h=(12)(34)(123)=(243)$ (reading the cycles from right to left, ...
1
vote
1answer
40 views

Graph Theory - How many regions of an n-sided polygon with all chords added?

The question: Consider an $m-sided$ polygon with all of its chords added, and assume that no more than two of these chords cross at any one intersection point. Make the figure into a planar graph by ...
4
votes
0answers
49 views

How to determine if these graphs are isomorphic?

I had this question on my last Discrete exam: (the missing vertex on graph G is vertex d) I did prove that the graphs were isomorphic, but my teacher said that I matched up my vertices wrong. ...
0
votes
1answer
58 views

Proper notation for the function $g(x) = x^2+6$.

I'm using this more as a method of verifying if I'm correct on a question I am having difficulty with. Keep in mind, I'm a complete beginner, so.. yeah. Thereom: Assume the function $g$ is ...
0
votes
0answers
12 views

what can you say about this operation using principle of inclusion/ exlusion [duplicate]

Given: A = [ Aaron features ], B = [Bob features], X = [all countries in Europe ] What must be true if: |A ∩ B ∩ X| = 1 Even though I don't see the relation between cardinality of sets, I kind ...
0
votes
1answer
23 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
2
votes
1answer
30 views

Number of pairs of females and males of different groups

There are n females, which can have m different types. There are n males, which can have m different types. Knowing how many females are of which type and how many males are of which type, how many ...
5
votes
0answers
130 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
0
votes
1answer
34 views

What can you say about this set operation using principle of inclusion/exclusion

Given: A = [ Aaron features ], B = [Bob features], X = [all countries in Europe ] What must be true if: |A ∩ B ∩ X| = 1 Even though I don't see the relation between cardinality of sets, I ...
0
votes
2answers
36 views

Why is this an equivalence relation, and what does the equivalence classes contain?

I'm doing some discrete mathematics exercises, but I can't seem to wrap my head around this relation: $$R(x, y) \text{ if } \exists z(\text{LiesInPart}\circ\text{LiesInCountry}(x,z) \wedge ...
1
vote
1answer
24 views

Recursive function calculation.

Suppose $f(n)=3f(\frac{n}{2})+1$ when n is even, and $f(1)=5$, please find $f(2),f(4),f(10),f(14)$ and so on. I did $f(2)$ and $f(4)$ and answer is 16 and 49. But I am not sure if I am right about ...
2
votes
3answers
54 views

When do we use multiplication instead of addition?

In a class of $n$ students, how many ways can we choose a size $k$ committee that contains a size m subcommittee? The committee can be chosen in $\binom nk$ ways and subcommittee can be chosen in ...
1
vote
2answers
51 views

Discrete Math Informal Proofs Using Mathematical Induction

Need to do a proof by mathematical induction using 4 steps to show that the following statement is true for every positive integer n and to help use the weak principle of mathematical induction. $2 + ...
1
vote
3answers
38 views

Are any two elements, of equal length, conjugate in $A_n$ for $n ≥ 3$

I have given the following problem to solve; (i) Prove any two cycles in Sn of the same length are conjugate in $S_n$ for any $n\geq 3$. (ii) Is the same true in $A_n$ for $n\geq 3$? (iii) Prove ...
2
votes
1answer
38 views

Finding a function into a closed form of the generating function

I have the following equation:$$a_n = n((-1)^n(1-n) + 3^{n-1})$$ How do I convert this into a closed form of the generating function?
0
votes
1answer
51 views

Modulus - Too big a number for the calculator

How do I go about doing this? $51^{47}$ mod $1537$? I tried using binary to split it up but in the end, I got $$ 51^{47}=1473\cdot 1051\cdot864\cdot1064\cdot51 \mod 1537 $$ which was still to huge ...
1
vote
1answer
52 views

How to represent a Neither/ Nor set operation

Given: A = { Aaron friends } B = {Bob friends} X = {all members in network} Set of friends in the network that are friends of neither Aaron nor Bob I got as answer: $X-(A \cup B)$ Is this ...
0
votes
1answer
18 views

Graphing Fourier transforms on a frequency versus intensity plot (how to deal with complex numbers)

I am trying to understand how Fourier transforms are used to make HNMR plots. HNMR basically consists of hitting some molecules with some radiation and listening to the radio signal that results. ...
1
vote
2answers
101 views

How many zeroes are there at the end of $36!^{36!}$?

Could you please tell me how many zeroes are there at the end of $36!$ to the power $36!$, i.e., $36!^{36!}$? I have been trying to find out. Read some reviews and answers related this but didn't ...
5
votes
8answers
214 views

Why is $n^2+4$ never divisible by $3$? [duplicate]

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
0
votes
1answer
21 views

Describing equivalence classes over the set of natural numbers

So for this problem we are supposed to describe the equivalence class for the following relation. $x \thicksim y$ iff $x$ mod 2 = $y$ mod 2 and $x$ mod 4 = $y$ mod 4. I am confused on what is meant ...
5
votes
1answer
69 views

Proving $\frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n}$ for $a,b>0, n\in\mathbb{N}$ by induction

prove using induction: $$ \frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n} $$ $$a,b \gt 0 , n \in N$$ my attempt: base $n=1$: $$ \frac {2}{(a+b)} \le \frac {1}{a} + \frac {1}{b}$$ ...
3
votes
3answers
42 views

Proving that $8^n-2^n$ is a multiple of $6$ for all $n\geq 0$ by induction

I have the following induction problem: $8^n-2^n$ is a multiple of $6$ for all integers $n\geq 0$. So far this is what I've done: Base case: $n = 0$ $8^0-2^0 = 6$ $1 - 1 = 6$ $0 = 6$ This ...
5
votes
3answers
112 views

How to quickly compute $2014 ^{2015} \pmod{11}$

Without using Fermat's Little Theorem, how can I quickly solve $2014 ^{2015} \pmod {11}$?
0
votes
2answers
26 views

Set A contains $\{1, 2, 3…, 11\}$ Compute the number of subsets of length $4$ of which at least $2$ numbers are $\leq 6$.

Can someone please explain to me how this works in a little more depth? I have the question and the solution and I'm not sure why it works. Here's the question: Set $A$ contains $\{1, 2, 3..., 11\}$ ...
3
votes
3answers
73 views

How can a binomial coefficient can be approximated by using Stirling's formula?

I've met some difficulties with such question: How can we approximate a binomial coefficient by using a Stirling's factorial approximation. I've evaluate a little bit and got this How can I ...
1
vote
1answer
30 views

verifying properties of relations to test equivalence

We are doing some more with relations and this time we are given a relation and told that it is not equivalent. We need to find out which property it does not fulfill. So we at least know there is ...
0
votes
1answer
50 views

Prove there exists a 2x2 entirely black or white square.

Given a 200x200 board containing black and white squares prove there exists a 2x2 sub square that is entirely black or entirely white. The total # of squares is 40000, there are 199x199 squares of ...
1
vote
1answer
44 views

Steps to solve this recurrence relation?

I have the following question: I am aware that I have to find the characteristic polynomial of this equation but I do not understand how to deal with $64 . 3^{n-4}$ so could anyone explain how to ...
-3
votes
1answer
38 views

How many recursive calls are made when quicksort is size n [closed]

How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? I thought the answer is n times because isnt this the best case?
1
vote
3answers
38 views

Help with discrete math proof

I'm having trouble with the following: $\ a_1=1$ and $a_n=1+\sum_{i=1}^{n-1} a_i$ for $n>1$ How should I go about proving the below? Any hints? $a_n = 2^{n-1}$
4
votes
3answers
88 views

Proving if $x^3$ is even, then $x$ is even.

Theorem: If $x$ is a positive integer and $x^3$ is even, then $x$ is even. My Proof by Contrapositive: I. Assuming that $x$ is odd, then I will show that $x^3$ is odd. II. $x$ is odd, so $x$ ...
0
votes
2answers
38 views

Can someone explain how to find the number of equivalence classes and elements?

I am struggling so much with this topic. Trying to do some practice questions but I don't seem to get it. What I'm working on is Let $A = \{ 1, 2, 3, \dots, 2014 \} = \{ x \mid 1 \le x \le ...
4
votes
1answer
41 views

“congruence modulo 7” is an equivalence relation on Z. Find three elements in the equivalence class [3].

“congruence modulo $7$” is an equivalence relation on $\mathbb Z.$ Find three elements in the equivalence class $[3].$ so $3$ is congruent to $mod\ 7$.. My attempt: a = bq + r = 7(1) + 3 = 10 , ...
2
votes
1answer
25 views

Questions concerning elements in $F = \big\{f: \{1, 2, 3\} \to \{1, 2, 3, 4, 5\}\big\}$.

a) Find and simplify the number of functions $f \in F$ so that $f(1) = 4$. My attempt: there is $1$ choice for $f(1)$, and $5$ choices for $f(2)$ and $5$ choices for $f(3)$, thus $1\cdot 5\cdot 5 = ...
1
vote
4answers
149 views

Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0?

I'm working on the extra credit for my Discrete Structures homework, but so far I have been unable to get a handle on the problem, even with help from 3rd parties, so I've decided to turn to you guys. ...
3
votes
3answers
270 views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
1
vote
1answer
59 views

What are the components of binary strings?

$C_{9}$ is the graph with vertices representing all binary strings of length nine. Two strings are adjacent if and only if they differ in exactly three positions. How can I compute how many components ...
0
votes
1answer
31 views

How to formulate the product of two generating functions without their final terms?

I know that if we have two generating functions like so: $A(z) = \sum_{n=0}^\infty a_nz^n$ and $B(z) = \sum_{n=0}^\infty b_nz^n$ Then we can write $A(z)B(z) = \sum_{n=0}^\infty(a_0b_n + a_1b_{n-1} ...
0
votes
1answer
27 views

Is my solution consider as a proof of inclusion-exclusion for $k=3$

This is my solution but I don't know if I can consider it as proof??? Here let $A$ , $B$ , and $C$ are sets
0
votes
1answer
31 views

Can the function y=5 be injective or surjective for all x ∈ integers?

I have a practice exam and I get kind of confused about: Is the constant function y = 5 , ∀ x ∈ Z [All integers] Is this function Injective or Surjective?
1
vote
2answers
77 views

Proving $n^a-n^b$ is divisible by 10

Let $n$ be positive integer. Prove that there exists positive integers $a$ and $b$, with $a \neq b$, such that $n^a-n^b$ is divisible by $10$. I have tried using mathematical induction and logs but I ...
2
votes
2answers
31 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
1
vote
2answers
38 views

How would you go through this combination/ permutation problem

A market has 30 different pants and 12 different hats. You want to to get 3 different pants and 2 different hats. How many ways can you make this purchase? I assume this is a combination, but stuck ...
0
votes
0answers
25 views

Turning a recurrence relation into a characteristic equation

I have the following recurrence to solve: bn = 13bn-1 - 22bn-2 , n > 1            Subject to b0 = 3 , b1 = 51 I've figured it out until b4: b2 = ...
2
votes
0answers
31 views

computing characteristic polynomial of hyperplane arrangement

The following problem comes from Richard Stanley's $\textit{Enumerative Combinatorics}$ vol. 1, 2nd ed. It is problem 114 (c) in Chapter 3. Let $\mathcal{A}$ be a hyperplane arrangement in ...
0
votes
3answers
54 views

determining which graphs are bitpartite/2-colorable and which are not

I am having trouble understanding bipartite/$2$-colorable graphs. I was hoping someone can guide me through this question. For the graphs given above, either prove that they are bipartite by showing ...