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
1answer
52 views

Help with discrete mathematics proof

I am to prove $A_0\cap(\bigcup_{i=1}^n A_i) = \bigcup_{i=1}^n (A_0\cap A_i), n\ge 2$ by induction. I started out like this: Step 1: Prove that $A_0\cap(\bigcup_{i=1}^n A_i) = \bigcup_{i=1}^n ...
1
vote
1answer
47 views

Explain this proof by induction? [duplicate]

$P(n)$ is the statement $n! < n^n$, where $n$ is an integer greater than $1$. I found a solution online here (https://people.cs.umass.edu/~barring/cs2... But I don't understand how they got from ...
3
votes
1answer
115 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
3answers
96 views

Find the sum $\sum_{k=1}^n k(k+1)2^k$

On a discrete mathematics past paper, I must find the sum $\sum_{k=1}^n k(k+1)2^k$. Could I have a hint/hints for approaching this problem, please? NB: the preceding problem was as follows. Let ...
1
vote
1answer
51 views

Are $G_1$ and $G_2$ isomorphic?

If $G_1$ and $G_2$ are two regular graphs on same no. of vertices,with same regularity and have identical Laplacian spectrum, are $G_1$ and $G_2$ isomorphic?
0
votes
1answer
35 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
36 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
1
vote
1answer
73 views

What is the difference between structural induction and ordinary induction?

I know two basic differences: 1.In structural induction you can use both numeric and string datatype,while in ordinary only numeric is allowed. 2.In structural there is base case and constructor ...
1
vote
1answer
53 views

Trouble Understanding a Combinatorics Problem

This question appeared on my combinatorics exam. I did not even understand the question. Determine the number of functions, $f:\{1,2,3\} \to \{1,2,3\}$, that satisfy $$f(1)+f(3)\equiv0\ (\text{mod ...
1
vote
1answer
36 views

$(n,m,d)-$code Hamming bound

I have the $(n,m,d)-$ code $(6,4,4)$ which can clearly be constructed $$\begin{pmatrix} 000000 \\111100 \\ 001111 \\ 110011 \end{pmatrix}$$ However, if i try using the hamming bound on $m$ i have, ...
3
votes
0answers
35 views

Understanding $\sum^n_{k=0}\binom nk x^k y^{n - k}$ combinatorially

In a class of $n$ students, each student is given the choice of solving either one of $x$ different algebra problems or one of $y$ different geometry problems. How many different outcomes are ...
0
votes
2answers
28 views

Counting (arrangement in a line)

So I'm having a tough time figuring this problem out : How many ways may 10 students be arranged in a line so that student 6 always comes before student 2 I've tried to do it by cases: case 1: ...
1
vote
2answers
46 views

Writing basic proofs about cycles?

These are extremely straightforward statements, but I'm getting flustered by how someone would go about constructing proofs to solve these... (a) Every cycle is connected (b) Every cycle is ...
0
votes
1answer
31 views

Binary Search 2Log(n)+1 steps?

So this is probably a basic and slightly stupid question. So.....for a binary search to find a number it takes at most 2Log(n)+1 steps (or Log(2N) questions. Im not a math major or anything, but ...
2
votes
2answers
200 views

Ackermann's function is $\mu$-recursive

In my book there is the following proof that Ackermann's function is $\mu$-recursive: We propose to show that Ackermann's funcition is $\mu$-recursive. The first part of the job is to devise a ...
2
votes
1answer
106 views

Find the union of of the following family or indexed collection

this question was posted but I did not understand the solution. For each natural number n, let An = {5n, 5n+1, 5n+2,...,6n}. And let A = {An: n is an element of the natural numbers}. Here is where I ...
1
vote
1answer
48 views

How do you understand renaming of summation variables?

As a part of a Knuth example, I struggle to understand how you flip the index so easily: $$\sum_{0 < j < k}(k-j) = \sum_{0 < k-j < k} j.$$ Why doesn't Knuth exchange the summand with the ...
0
votes
0answers
60 views

Linearize discretized nonlinear system model

For the following nonlinear system I want to find the linearization after a discretization: $$ \begin{pmatrix} \dot{x_{1}} \\ \dot{x_{1}} \\ \dot{x_{1}} \end{pmatrix} = 1/A \begin{pmatrix} ...
2
votes
1answer
44 views

RSA, cipher, Cryptosystem

I genuinely have no idea how to go about solving this, any hints would be helpful
0
votes
1answer
42 views

Quick formula rearranging

I'm having problems rearranging this formula to solve for c, could someone lend a hand please. It's a physics formula for projectile motion. ...
0
votes
1answer
19 views

Logic gate diagram and $K$-map.

$F(x,y,z) = \bar y \overline{(\bar x z)} + yx + y \bar z$ I needed to draw a logic gate diagram, which I already did. But my instructor also told me that if I want I can use the $K$-map to simplify ...
-2
votes
2answers
86 views

Probability of each person writing code--in a certain language

I am little lost with this problem. Not sure which formulas to use A project was implemented by three developers: Pat, Jon, and Maria. They used four languages: C, C++, Python, and JavaScript. The ...
2
votes
1answer
607 views

Determining matrix for relationship: reflexive, symmetric, transitive.

I have two matrices below and need to determine if R is (a) reflexive, (b) symmetric, and (c) transitive. $M_R = \begin{pmatrix} 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 \\ 1 & 1 ...
4
votes
1answer
45 views

Discrete-time derivative of the sign function

How does one calculate the time derivative of $$ x_{k+1} = C_1\, \text{sign}(x_k-y_k)\sqrt{2\vert x_k-y_k\vert}, $$ with respect to $x_k$ ? I know that the right part of the equation should yield ...
2
votes
1answer
66 views

weak compositions of $n$ with $2m$ parts and extra conditions

A weak composition of $n$ into $k$ parts is a sum $$\displaystyle \sum_{i=0}^k x_i=n$$ such that $x_i\in \mathbb{Z}$ and $x_i\geq 0$ for each $i$. I am trying to figure out the number of weak ...
0
votes
3answers
45 views

Showing that $\mathbb{Z}_N$ is a field if $N$ is prime

I know that $N$ being prime is a necessary and sufficient condition for $\mathbb{Z}_N$ to be a field. I know how to prove that it's necessary but I'm not sure how to prove that this is a sufficient ...
1
vote
1answer
35 views

Are these graphs homeomorphic?

Are these graphs isomorphic, and why? In advance, thanks!
4
votes
2answers
141 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
2
votes
1answer
108 views

What is the next prime number?

Given an integer \begin{equation*} N~\text{such that}~N\leq 10^{18}, \end{equation*} what is the next prime number after this number? What approach should I use to solve this problem? (Problem ...
0
votes
1answer
51 views

Probability of choosing two cards--event probability

Given six cards: $A♠, J♠, 2♠, A♥, 2♥, 2♦$, you pick one card at random. Consider two events: ...
0
votes
1answer
42 views

Finding a truth value from a given statement.

If $Q(x,y)$ be the statement $"x+2=3y"$, what are the truth values of $\forall x\exists yQ(x,y)$, $ \exists x \forall y(x,y)$, and $ \forall x \forall yQ(x,y) $? I know how to do it if $Q(x)$ be ...
0
votes
1answer
52 views

Show that if $a, b$ and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod{m}$, then $\gcd(a, m) = \gcd(b, m)$

Problem 1 (#3.5.32). Show that if $a, b$, and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod {m}$, then $\gcd(a, m) = gcd(b, m)$. Proof. Let $d = \gcd(a, m)$ Then $d \mid a$ and $d ...
2
votes
1answer
57 views

Bayes' theorem to find $P(A\cap B), \,P(B\mid A),\,P(A\cup B)$

Given, $P(A)=0.4, P(B)=0.5,P(A\mid B)=0.3 $. Need to find $$P(A\cap B), \,P(B\mid A),\,P(A\cup B).$$ So far I did $$P(A\cap B) = P(A\mid B) P(B) = ...
2
votes
1answer
167 views

Perfect matching problem

We have a random graph G = (V,E). Two players are playing a game in which they are alternately selecting edges of graph so that in every moment all the selected edges are forming a simple path (path ...
1
vote
1answer
90 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
2
votes
3answers
521 views

What is the maximal path of a tree?

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?
0
votes
0answers
14 views

Order of the Big-O's?

My order by their Big-O order would be: 8,5,3,1,2,7,6,4. Would this be the correct order? $f(n) = C$ where $C$ is some constant $f(n) = \log (n) $ $f(n) = n^6 $ $f(n) = n! $ $f(n) = 6^n $ $f(n) = ...
3
votes
6answers
106 views

Using induction prove $(n^3)-n$ is divisible by 3 whenever n is a positive number.

I am not sure if I am doing this right, but I have this: There exists an integer $k$. $2k =$ positive number $(2k)^3 - 2k$ [*And this is where I get lost. How does one prove this?]
0
votes
1answer
25 views

Prove that the circuit rank $= |e|-|v|+c$ , where $c$ is the number of connected components?

How to prove that for any given graph $G=(V,E)$, the circuit rank is $$|E|- |V| + C,$$ Where $C$ is the number of connected components.
1
vote
3answers
35 views

Representing a Decimal as a Fraction - 2 Methods

So I am trying to represent the number 0.71717171 · · · as a fraction and have managed to do it using algebra. I was told I was supposed to solve it using a geometric sum. Could someone guide me ...
1
vote
3answers
112 views

Determine whether the relations are symmetric, antisymmetric, or reflexive.

This exercise is given in my textbook and I am trying to solve it. Determine whether they are symmetric, antisymmetric or reflexive. $R_1=\{(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)\}$ ...
3
votes
2answers
60 views

Showing that a function is surjective (onto)?

For example : $F:\Bbb R\rightarrow\Bbb R$ defined by $F(x) = \frac{2x+1}{3}$ I let $F(x)=Y$ which gives $Y=\frac{2x+1}{3}$ then simplify and solve for $x$ , what I have at the end is ...
3
votes
2answers
212 views

How high a priority does discrete math have for people who want to become machine learning practitioners?

Machine learning seems to depend on such math fields as probability, statistics, calculus, and linear algebra. @pranav suggested discrete math would be an important prerequisite. However, someone ...
7
votes
5answers
179 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
0
votes
1answer
72 views

Consider the recursively defined language, L2

Consider the recursively defined language, $L_2$ i) $x \cap L_2$ and $y \in L_2$ ii) if $w \in L_2$, then so is $wxw \in L_2$ Find all strings in L_2 with length less than $7$ ...
1
vote
0answers
56 views

Polya's Enumeration Theorem applied to the 'colourings' of a cycle using integers

I am trying to solve a problem about an application to Polya's Enumeration Theorem. The problem concerns the cycle group on 5 vertices, $C_5$. I found its cycle index to be $x_1^5+4x_5^1$. Thus the ...
0
votes
0answers
10 views

Combinatorial proofs with vandermond's identity [duplicate]

I am studying for my final for discrete math and I have come across a proof that I am confused on solving. I was wondering if anyone could help. I understand that it is vandermond's identity but I ...
1
vote
0answers
26 views

Deriving the Particular Solution to a Linear Discrete Dynamical System

In my lecture notes it says that for a linear dynamical system of the form $ f(x) = Ax $ where A is diagonalisable d x d matrix, with $ \left \{ v_1 , v_2, \cdots , v_d \right \} $ a basis for $ ...
3
votes
1answer
66 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
1
vote
0answers
50 views

Set $X$ has $n$ elements, and set $Y$ has $m$ elements. Prove by induction that $X$ into $Y$ has $n^m$ elements.

I found this problem in a discrete mathematics textbook but there is no solutions provided for me to see how it was done. I started by making the inductive hypothesis, assume $n^m$ is true. The base ...