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
0answers
18 views

How do you find the order of a recurrence relation?

I cannot find a straight forward answer in my book or online. A lot of the answers I found are very wordy and I have trouble understanding them. For example take this recurrence relation: Is the ...
0
votes
0answers
11 views

Clarification on a reflexive function

$R_1 = \{(a, b) | a โ‰ค b\}$ is a reflexive function, but I'm confused on why it is. $aโ‰คb$ but doesn't that not necessarily mean that there is an $a$ that will equal $b$? Couldn't all of the $a$ very ...
1
vote
2answers
31 views

Confusion on sets and relations

I'm confused on how the number of subsets equals the number of relations. If set A = {1, 2} then AxA would be {}, {1}, {2}, {1,2}. I'm confused on how there are $2^{n^2}$ subsets of $A$ x $A$ because ...
0
votes
2answers
37 views

A question related to linear recurrence.

I have seen examples such as Towers of Hanoi and Merge Sort, which I understand but when it comes to solving this kind of problems I just don't understand where to start. If given a solution to the ...
0
votes
1answer
31 views

Discrete Mathematics Nonhomogenous linear recurrence relation

Solve the recurrence relation $$a_n=-a_{n-1}+8a_{n-1}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14\text{ for }n\ge3$$ where $a_0=6,a_1=0$ and $a_2=57$. Just want to ask if my $p_n$ is correct because I ...
0
votes
2answers
25 views

Given that the relation that aRb if and only if the smallest element of a is is equal to the smallest element in b?

X is the set of all nonempty subsets of the set {1,2,3,4,5,6,7,8,9,10}. a,b are elements of X. a) Find the number of elements in the equivalence class [{2,6,7}]? ...
0
votes
1answer
17 views

How to find the number of subsets $A\subseteq \{1,2,\ldots,10\}$ so that $A$ is related to $\{1,2,7\}$ or $A$ is related to $\emptyset$?

Let $S = \{1,2,3,4,5,6,7,8,9,10\}~$, and $ARB$ if and only if $A$ union with $B$ has exactly 3 elements a) Find the number of subsets $A \subseteq \{1,2,...,10\}~$ so that $A$ is related to $\{1,2,7\}...
0
votes
1answer
30 views

Determine if $f=\{(x,y)\mid 2x+3y=7\}$ is invertible. From $\mathbb R \rightarrow \mathbb R$. If it is invert it.

I am thinking this is no, because I am not even sure if this counts as a function? I am unsure how this can be a function if there exist only a few $(x,y)$s that fulfill the equation. Or does the $\...
0
votes
1answer
30 views

Worst Case Time Complexity Analysis of an Algorithm

Below I have an algorithm for finding the mode of a list of nondecreasing integers. I'm trying to analyze the time complexity of this algorithm. Procedure find a mode($a_1, a_2, ..., a_n$:...
1
vote
1answer
44 views

How to find b ( the most efficient way) in $ax^2+bxy+ cy^2$?

I know the very basic way to find the b in this quadratic expression: $$P(x,y)=ax^2+bxy+ cy^2$$ I can first evaluate $P(0,1)=c$. Similarly, I can do $P(1,0)=a$ and then I can do $\frac{P(1,1)-P(1,-1)}...
0
votes
1answer
43 views

Expected number of rolls for fair die to get same number appear twice in a row?

We repeatedly roll a fair die until any number appear twice in a row. I want to find the expected number of rolls until we stop. I am thinking this is a geometric distribution, but how would I apply ...
1
vote
0answers
18 views

Difference equation particular solution

On an exam I was asked to find the solution $h$ for the following difference equation: $h(n) - ah(n-1) = a\delta(n) - \delta(n-1)$ Where $\delta(n)$ is the unit impulse. I was able to find the ...
1
vote
1answer
17 views

Finding the number of ordered pairs of integers (Discrete Maths)

Let $k$ and $n$ be positive integers such that $k\le n$ (i) How many ordered sequences of integers ($a_{1}$,$a_{2}$,...$a_{k}$) are there such that $a_{1}$,$a_{2}$,...$a_{k}$$\in $(1,2...n) (ii) How ...
2
votes
0answers
26 views

Proving the number of vertex in a tree. (Graph theory)

Prove that every tree with $n$ vertices, where $n\geq 2$ has at least $2$ vertices of degree $1$. What i tried Suppose that there are less than $2$ vertices of degree $1$. So we can split into two ...
0
votes
2answers
28 views

Finding Large Bases with Large Exponents [duplicate]

I'm given the question to find: $151 678 213 ^{115431217}\pmod{10}$ I know that 10 is not prime, so I can't use fermats theoreom. So I've attempted using eulers totient function I know that: $a^{\...
0
votes
2answers
16 views

How to prove (given $f\colon A\to B$ and $g\colon B \to C$), if $gโˆ˜ f\colon A \to C$ is onto, then $g$ is onto; if $gโˆ˜ f $ is 1to1, then $f$ is 1to1

I am doing practice problems for my exam, and I can't seem to figure this one out. Let ๐‘“: ๐ด โ†’ ๐ต, ๐‘”:๐ต โ†’ ๐ถ. Prove that: (a) if ๐‘” โˆ˜ ๐‘“: ๐ด โ†’ ๐ถ is onto, then ๐‘” is onto (b) if ๐‘” โˆ˜ ๐‘“: ๐ด โ†’ ๐ถ ...
0
votes
1answer
19 views

Correct notation with composite function & characteristic functions.

I have the functions $p: \mathbb R \to \mathbb R; \quad p(x) = \frac12 x + 1$ $q: \mathbb Z \to \{0, 1\}; \quad q(x) = \begin{cases} 1 & x \geq 1 \\ 0 & x \leq 0 \end{cases} $ I know that ...
1
vote
1answer
31 views

In the function $r :\mathbb{R} โˆ’ \{0\} \to \mathbb{R}$, what effect does the “$-\{0\}$” have on the domain?

The full function is: $r : \mathbb{R} โˆ’ \{0\} \to \mathbb{R}$ defined by $r(x) = 6 / x$.
0
votes
1answer
26 views

Find the value of $k$ in the equation [closed]

Find the value of $k$ for which the equation $$kx^2-2015x+(k-2015)=0$$ has one positive and one negative root.
0
votes
0answers
10 views

How do I find the diagonal of a particular element in a triangular series?

I am trying to solve this problem on spoj. It asks to find the nth term in the Contor Series. It can be solved by observing the pattern and implementing the ad-hoc method. However, I was trying to ...
3
votes
1answer
82 views

How to find number of vertices in a given graph?

I am studying on the graphs where eccentricity of every vertex is same. If $G$ is such graph where eccentricity is $r$ for every vertex and for a vertex $x$ if there exists at least two vertices such ...
0
votes
0answers
25 views

Recommend 2nd logic and discrete math books?

I passed all the required undergraduate math for the computer science program at my university. It didn't include a course in complex analysis and the advanced required courses were about discrete ...
3
votes
1answer
46 views

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100.

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100. How would you approach this problem?
0
votes
0answers
17 views

Discrete math Big O notation

I have a question that states: "Let k be a positive integer. Show that $1^k + 2^k + ... + n^k$ is O($n^{k+1}$)". Below is my answer, I'm a little confused about the equalities, I've seen people use ...
1
vote
1answer
59 views

Are all algebras groups?

It seemed to me that boolean algebra is a group because it is closed (You can't use boolean algebra and get a result that is outside the group) under a logical primitive(?) and order of operands and ...
0
votes
1answer
47 views

First order logic equivalence proof

I have this homework problem that I can't figure out. I have to show that the following sentences are equivalent: $\neg \forall c\; A(c)\Rightarrow\exists d\; B(d) \land \neg C(c,d)$ $\exists c\; A(...
0
votes
1answer
23 views

Confusion on in order problem with combinations

In a permutation of the set ${1, 2, . . . , n}$, a pair $i$, $j$ is out of order if $i < j$ but $i$ occurs after $j$ in the permutation. In a random permutation of the set ${1, 2, . . . , n}$ with ...
0
votes
1answer
38 views

Having trouble understanding how to disprove/prove if a formula is a function.

Is $\frac 1{x^2-2} $ a function from $\mathbb{R}\to \mathbb{R}$? Is it a function from $\mathbb{Z}\to \mathbb{R}$? I have been thinking about this but, I can't find any example for which you can have ...
0
votes
2answers
20 views

First Order Logic and equivalence rules

I have a couple of questions about first order logic equivalence rules. How do you distribute the $\neg$ correctly with the $\exists$ and $\forall$ quantifiers? If let's say I have $$\neg[\forall x\;...
0
votes
2answers
77 views

If Mr. X was born on April 16, 1987 what day is 2016 days after he was born?

I have a confusion about the way of solving the following mathematical problem: If Mr. X was born on April 16, 1987 what day is 2016 days after he was born? How will I solve these kind of ...
0
votes
0answers
23 views

Choose a point which minimizes the sum of distances between it and other points in set explanation

I was wondering, suppose I have a set of integers, {1, 70, 97, 98, 99, 101, 102}, what is the integer to choose such that the distance is minimised for a subset ...
0
votes
0answers
22 views

The multi-binomial theorem, prove multiples of 11

Over $\mathbb{Z_{11}}$ $ $, $ \\\\$ $f(x)= x^{11} - x $ has solutions $0, 1, 2, \cdots , 10.$ (by Wilson) $$$$ So, we can rewrite $f(x)=x(x-1)(x-2)(x-3)\cdots(x-10)$ That is $$x^{11} - x = x(x-1)(...
0
votes
1answer
31 views

Double counting proof of binomial problem

The assignment is to prove the following assertion using the method of double counting and explaining which pairs were counted. $$\dbinom{n+1}{k+1} = \sum_{i = k}^{n} \dbinom{i}{k}$$ Left side is ...
1
vote
2answers
30 views

The number with minimum sum of differences

Let $a_1,a_2,...,a_n\in\mathbb{R}$. I wonder how to find the number $x$ with $$|x-a_1|+...+|x-a_n|=\mbox{min}\{|a-a_1|+...+|a-a_n|\mid a\in\mathbb{R}\},$$ namely the sum of the differences with $a_1,.....
2
votes
1answer
24 views

A basic combinatorics problem: number of solutions of form $ \pm 1 $ to and additive equationn

In my combinatorics and discrete mathematics class I was asked this question which I cannot seem to be able to solve: Let us define N variables $ \{ s_k \}_{k=1}^{N} $ each having two possible ...
0
votes
1answer
15 views

Treewidth Of Graphs And Chordal Completion

https://en.wikipedia.org/wiki/Treewidth The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal ...
-1
votes
1answer
44 views

Discrete Mathematics Stamp problem [closed]

I am very confused on how to solve. Use the Principle of Mathematical Induction to prove that every amount of postage of 18 cents or more can be formed using just 4-cent and 7-cent stamps.
8
votes
2answers
165 views

What is the subword complexity function of this infinite word?

Let $w_{0}$ denote the finite word $01$ in the free monoid $\{ 0, 1 \}^{\ast}$, and for $i \in \mathbb{N}$ define $w_{i}$ as the word obtained by adjoining the first $\left\lfloor \frac{\ell(w_{i-1})}{...
0
votes
1answer
30 views

Let $G$ be a graph with $n$ vertices. Prove that $\chi(G) \ge \frac{n}{\alpha(G)}$

$\chi$ is the chromatic number of $G$, and $\alpha$ is the independence number of $G$. I know that if $G$ has a proper coloring, then the set of vertices with a particular color is an independent set....
0
votes
1answer
49 views

Discrete Math Problem Find a formula for (1 / (1 · 2)) + (1 / (2 · 3)) + (1 / (3 · 4)) + . . . + (1 /(n(n + 1) ) [duplicate]

Find a formula for (1 / (1 ยท 2)) + (1 / (2 ยท 3)) + (1 / (3 ยท 4)) + . . . + (1 /(n(n + 1) ) by examining the values of this expression for small values of n, where n is a positive integer. Use ...
0
votes
3answers
23 views

Why is the Relation R4 Reflexive?

Given A = {1,2,3,4} R4 = {(1,1), (1,2), (2,2), (3,3), (4,4)}. My understanding is that in the case where if R4 was {(1,1), (2,2), (3,3), (4,4)}, then R4 would be reflexive because every element is ...
1
vote
2answers
69 views

Solve by Mathematical Induction: $2^n+1 \leq 3^n$

I'm very confused on how to prove this. By using Mathematical Induction prove that, for all positive integers $n$ the following inequality holds: $$2^n + 1 โ‰ค 3^n$$
0
votes
1answer
31 views

Why is the Relation R3 Transitive?

Given $A = \{1,2,3,4\}$ in the Relation $\mathcal{R} = \{(1,1),(2,2),(3,3),(4,4)\}$ I understand why $\mathcal{R}$ is Reflexive, Symmetric but why is it also transitive? In my understanding for a ...
0
votes
1answer
30 views

If $G$ is a graph with exactly one vertex of odd degree, does G have both an Eurelian trail and an Eurelian tour?

I believe the answer must be yes, because I'm having a difficult time finding a counterexample that contains only one vertex of odd degree. So I need to figure out how to prove this. All I've got so ...
0
votes
1answer
28 views

Let $S$ be a set of $k$ elements, where $k$ is a whole number. Suppose $n$ is not an element of $S$. Show that $S$ union s has $k + 1$ elements.

Let $S$ be a set of $k$ elements, where $$k \in \omega$$ Suppose $$n \notin S$$Show that $$S \cup \{n\}$$ has $k + 1$ elements. I'm honestly last as to where I should start. I was thinking of maybe ...
-1
votes
1answer
45 views

How to solve the recurrence $T(n) = 2T(n/3)+n$ [duplicate]

Base case of $T(1)=1$ As a part of your solution establish, a pattern for what the recurrence looks like after the $k$-th iteration Express final answer as $\Theta(n)$ $T(n) = 2T(n/3)+n $ How to ...
1
vote
2answers
44 views

Proving $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = 2\binom{n + 2}{3}$by math induction?

I am working on a problem, but I don't know whether or not to use math induction on it. Here's the problem: Prove that for all integers $n \geq 1$, $$1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = 2\...
3
votes
4answers
46 views

Using a combinatorial argument

I am having some difficulty with this problem: Use a combinatorial argument to show that $$\binom{m + n}{r} = \binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r - 1} + \dots + \binom{m}{r}\binom{n}{0}...
3
votes
2answers
45 views

Proving $\sum_{i=0}^n \binom{n}{i} = 2^n$ by math induction

I am having some trouble using math induction to prove the following problem: $$\sum_{i=0}^n \binom{n}{i} = 2^n$$ Where n $\geq$ 0 I know the first thing with math induction is substitute the base ...
1
vote
1answer
64 views

$10$ people are standing in a queue when three new checkouts open. In how many ways can the three new queues be formed?

Problem: $10$ people are standing in a queue when three new checkouts open. 8 people rush to the new checkouts and the new queues end up with at least two people in each. In how many ways can the ...