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

learn more… | top users | synonyms

3
votes
1answer
723 views

How to prove if log is rational/irrational

I'm an English major, now doubling in computer science. The first course I'm taking is Discrete Mathematics for Computer Science, using the MIT 6.042 textbook. Within the first chapter of the book's ...
1
vote
2answers
71 views

Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
0
votes
1answer
12 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
1
vote
0answers
34 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
1
vote
3answers
61 views

Recurrence solution of simple recurrence

Please help me to find the solution of the recurrence in terms of n(implies $(f(n))$ and also the summation of the recurrence up to infinity ($sum = \sum_{n=0}^\infty f(n)$) . ...
0
votes
0answers
46 views

verify/prove theorem Diophantine/GCD

a,b,c positive integers. Verify Diophantine ax + by = c has integer solution x0, y0 if and only if GCD(a,b)|c. Attempt: Diophantine ax + by = c has integer solution x0, y0 -> GCD(a,b)|c: factoring ...
3
votes
1answer
15 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
0
votes
1answer
29 views

Is the polar of the polar set the original set?

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:z\cdot x \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is ...
12
votes
2answers
639 views

A Weaker Version of the ABC Conjecture

The ABC conjecture states that there are a finite number of integer triples (a,b,c) such that $\frac {\log \left( c \right)}{\log \left( \text{rad} \left( abc \right) \right)}>1+\epsilon $, where ...
0
votes
2answers
56 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
3
votes
2answers
66 views

Graphs with a polynomial number of shortest paths between any pair of vertices

Let $G$ be a simple undirected graph, and let $s$ and $t$ be two arbitrary vertices of $G$. Even for some rather restricted graph classes, the number of shortest paths between $s$ and $t$ can be ...
0
votes
7answers
149 views

Calculating $\displaystyle\sum_{i=1}^{n} \binom{i}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
2
votes
1answer
26 views

Relations examples (reflexivity, symmetry, transitivity)

I've found the two textbooks I'm using to to be particularly unhelpful in explaining these concepts, especially as they relate to English examples (non-existent). The first few following questions ...
1
vote
1answer
28 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
0
votes
2answers
22 views

Which is kernel similar gaussian kernel?

I must find a kernel that statisfies as follows: In the my reference paper, the author suggest gaussian kernel that is The purpose of that kernel is that it will take a weight for each points ...
-1
votes
2answers
179 views

Expressing integers as sums and differences of distinct powers of 3

Let: A = { 1, 3, 9, 27, 81, 243, 729 } B = { 1, 3, 9, 27, 81, 243, 729 } C = some combination of A ($7$ Choose $k$ where $k= 0$ to $7$) D = some combination of B ($7$ choose $k$ where $k= 0$ to ...
1
vote
0answers
16 views

Why is this directed graph strongly connected?

From what I can see, there is no vertex path that goes to 1 so why is it strongly connected? Shouldnt every vertex be reachable from every other vertex? In this picture the 1 is not reachable.
0
votes
1answer
18 views

Let x, y be integers. Show that if x = y (mod n), then x + mZ = y+mZ,and conversely, if x+mZ=y+mZ then x = y (mod n)?

Let $x, y$ be integers. Show that if $x = y\mod n$, then $x + nZ = y+nZ,$ and conversely, if $x+nZ=y+nZ$ then $x = y\mod n$? I have no a clue on how to prove this! Please help.
0
votes
1answer
43 views

Properties of a relation on matrices: $(m_1,m_2)\in R$ iff $m_1\cdot m_2$ is defined

Let $M$ be a set of matrices of integers. Let $R$ be the relation on $M$ defined as follows: For any two $m_1, m_2 \in M, (m_1, m_2) \in R$ iff the matrix multiplication $m_1 \cdot m_2$ is defined. ...
-1
votes
0answers
43 views

Discrete Mathematics Proof about coefficients in a Function [on hold]

I need to prove these using any method. I know that it deals with the distribution of the coefficients of a function. I just don't exactly know about how to go about proving this. Let the function ...
2
votes
2answers
40 views

Find the recurrence relation for the number of bit strings that contain the string $01$.

Question:Find the recurrence relation for the number of bit strings that contain the string $01$. Attempt: Since $01$ can appear in a lot of places, I focused on instances without $01$ first. Bit ...
1
vote
1answer
246 views

Finding the probability that X will be successful if its success is predicted

Consider an electronics company is planning to introduce a new camera phone. The company commissions a marketing report for each newproduct that predicts either the success or the failure of the ...
0
votes
2answers
81 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
2
votes
2answers
44 views

Find the $4$ sq. roots of $100$ in $ U_{209}$. Identify which square root of $100$ is square.

Find the $4$ sq. roots of $100$ in $U_{209}$. Identify which square root of $100$ is square. (Not the $4^{th}$ root, but the $4$ square roots). I honestly don't even know what this question is ...
4
votes
1answer
62 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
1
vote
2answers
30 views

Source coding and Entropy

Hell people, I have a small question I came by , but I am not quite sure about the right approach to it. Suppose that we have a source that transmits 5 symbols. We have two cases. When all ...
1
vote
2answers
55 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
0
votes
0answers
21 views

Proof of series expansion of $f(k) = {r - sk \choose n}$ in Concrete Mathematics book by D. Knuth, et. al.

Please help me prove this equation in page 190 of Concrete Mathematics 2nd Ed. book by D. Knuth: $f(k) = {r - sk \choose n} = ...
0
votes
1answer
28 views

Diagonalization of Skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. and we have the relation $C=UDU^{-1} ...
1
vote
1answer
58 views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute ...
0
votes
1answer
300 views

Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people, 21 bring hot dogs, 35 bring fried chicken, 28 ...
0
votes
1answer
32 views

Least squares method: must each partial derivative be zero?

In gradient equations, does the sum of the partial derivatives have to be equal to zero or each derivatives has to be zero? As I have just started to understand gradient equations, if my question is ...
-1
votes
3answers
40 views

Exactly why coefficient of $x^ky^{n-k}$ is $C(k,n)$ [duplicate]

in combination when we have a binomial lattices like $(x+y)^n$ the coefficient of $x^ky^{n-k}$ is equal with $C(k,n)$ ... for example we have $(x+y)^4$ so we have this $4$ factor ...
0
votes
2answers
53 views

Combinatorial Proof to $\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$

Question: Combinatorial Proof to $$\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$$ I know that by binomial theorem we can derive this, $$0 = ((-1)+1)^n = \sum_{k=0}^n {n\choose k}(-1)^k1^{n-k} = ...
0
votes
0answers
21 views

Stirling number of the second kind and its extension

I have a question regarding Strling's number. For starters we all know that the number of ways in which it is possible to distribute the m distinct objects in to n identical containers with no ...
2
votes
2answers
45 views

What are $10^k \pmod 3$ and $n = \overline{a_ka_{k -1} \ldots a_1a_0}$?

I feel like I should know these concepts, but I don't.
1
vote
0answers
9 views

elementary proof for discrete Kantorovich-Rubinstein theorem?

For the Kantorovich-Rubinstein theorem, please see the wikipedia page http://en.wikipedia.org/wiki/Wasserstein_metric (which does not contain a reference for the proof). I am only interested in the ...
-2
votes
0answers
36 views

mathematics solve [duplicate]

Please can you help me with this question? Out of 120 customers that visited a supermarket in a day. 62 bought clothing materials, 51 bought provisions and 48 bought kitchen utensils. 15 customers ...
4
votes
3answers
51 views

When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$?

Question: When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$? Attempt: $$1XX\\ X1X\\ XX1$$ The count of $1$ for the types above are, $${{3}\choose{1}}*9*9$$ ...
0
votes
1answer
32 views

Question about proving division

Suppose $m = a_k + a_{k -1} + \ldots + a_1 + a_0$. Does $3$ divide $m$? If so, how do we prove that? We know that $3|m \to 3j = a_k + a_{k -1} + \ldots + a_1 + a_0$ for some $j \in \mathbb Z$. ...
0
votes
2answers
36 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
1
vote
2answers
74 views

Must the centralizer of a non-identity element of a group be abelian?

Q1: Must the centralizer of a non-identity element of a group be abelian? I challenge everyone by asking further about this question one step further. The definition of centralizer is: Let a be ...
-1
votes
1answer
64 views

set-venn diagram [on hold]

in a class of 120 students, 62 students offer maths, 51 offer English language and 48 offer chemistry, 15 students offer both maths and English, 20 offers both maths and chemistry while 10 offer both ...
-1
votes
0answers
42 views

set mathematics [duplicate]

Out of 120 customers that visited a supermarket in a day. 62 bought clothing materials, 51 bought provisions and 48 bought kitchen utensils. 15 customers bought both clothing materials and provisions, ...
1
vote
1answer
775 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
2
votes
2answers
73 views

At a party $n$ people toss their hats into a pile in a closet.$\dots$ [duplicate]

Question: At a party $n$ people toss their hats into a pile in a closet. The hats are mixed up, and each person selects one at random. What is the expected number of people who select their own hats? ...
1
vote
3answers
348 views

How to solve for the amount of arrangements of books on a shelf?

Having a little bit of trouble with this question, but I don't necessarily want the answer, I'm looking for an explanation on how to do it, and if my theory is correct. How many ways are there to ...
1
vote
3answers
82 views

Finding recurrence and an algorithm to represent it

You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy algorithm is not guaranteed to find the optimal way to ...
1
vote
1answer
871 views

probability of selecting cards

i'm confused by the following problem could someone walk me through it, so i can understand (a) 10 cards are drawn at random one at a time with replacement from an ordinary deck of cards. ...
0
votes
1answer
63 views

Combination Problem with Sofa [on hold]

Suppose we have 5 sofa on room A. in this room, 4 students seated on these sofa. These Strudents go to another room for eating dinner, and after that come back to room A. how many way the students can ...