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

1
vote
1answer
15 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, ...
2
votes
0answers
28 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
22 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
33 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
17 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
106 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 ...
1
vote
1answer
25 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
40 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
29 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
35 views

RSA, cipher, Cryptosystem

I genuinely have no idea how to go about solving this, any hints would be helpful
0
votes
1answer
34 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
12 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
72 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 ...
1
vote
1answer
50 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 ...
3
votes
1answer
24 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
35 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
44 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
90 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 ...
1
vote
1answer
98 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
48 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
25 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
32 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
37 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
32 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
55 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
201 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
86 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
20 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
25 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
38 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)\}$ ...
2
votes
2answers
45 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
120 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
92 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
38 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
33 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
8 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
15 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
0answers
41 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
42 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 ...
3
votes
1answer
62 views

RSA cryptography?

I understand how RSA cryptosystem works; however, I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be equal to the product of two distinct, ...
0
votes
1answer
43 views

Discrete math, Showing a recursive equation as equivalent to a non recursive equation.

I'm having trouble with this: Show that this recursive function: $L(n) = \{0 : n = 1\ ,\ \lfloor(L(n/2))\rfloor +1 : n \gt 1\}$ is equivalent to this non-recursive equation: $L(n) = ...
0
votes
2answers
54 views

Truth table- what is the value of the statement?

$(p \lor q)\rightarrow (p \land q)$ this is the statement. I know how to build the truth table from this but what does it mean when both p and q are false, what is the value of the statement?
0
votes
1answer
15 views

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=e^{\theta x}$. Show that $E[f(X)]=exp(\lambda (e^\theta -1))$

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=e^{\theta x}$, where $\theta \in \mathbb{R}$ and suppose that $X ~ Po(\lambda)$ for some $\lambda >0$. Show that $E[f(X)]=exp(\lambda ...
2
votes
4answers
45 views

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,…\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,...\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$ Absolutely lost. From my notes, we define $E[X]$ as follows ...
0
votes
1answer
38 views

How can I mathematically model the combinatory problem?

I have the following problem, and I would like to model it using a mathematical formula, for a purpose of optimization problem: let's say that I have two tasks $[T_1, T_2]$, and $3$ resources ...
0
votes
1answer
11 views

variation of domination numbers

I am searching a e-copy of a book T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998. It is out of print. Is it possible to ...
2
votes
1answer
16 views

W/ generating functions, How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$?

The question is: How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$? Solve this by writing down the correct generating function. I have no idea ...
1
vote
1answer
31 views

Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

The question: Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$? I used a modulo calculator to get that the answer for $N$ mod $4$ is $3$, and ...