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

learn more… | top users | synonyms

1
vote
1answer
25 views

To prove these sets are equal without using modulo arithmetic.

Prove $\{3t : t \in \mathbb Z\} \cup \{3t + 1 : t \in \mathbb Z\} \cup \{3t + 2 : t\in \mathbb Z\} = \mathbb Z.$
1
vote
1answer
37 views

Permutation and combination 4 digits number

I know how to compute the number four-digits strings: $10^4$, but I'm stuck on how to qualify this with the condition that at least two digits are different. Can anyone help?
0
votes
1answer
41 views

Use generating functions to prove Pascal’s identity

How do I prove Pascal's identity using generating functions? $C(n,r) = C(n−1,r) + C(n−1,r−1)$ when $n$ and $r$ are positive integers with $r < n$. I am given the hint to use the identity ...
3
votes
6answers
129 views

How many $3$ digit numbers with digits $a$,$b$ and $c$ have $a=b+c$

My question is simple to state but (seemingly) hard to answer. How many $3$ digit numbers exist such that $1$ digit is the sum of the other $2$. I have no idea how to calculate this number, but I hope ...
2
votes
1answer
68 views

Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
0
votes
1answer
46 views

Proper Set Theory Transformation

I was wondering if i am using the Inverse Laws Correctly in this transformation: 1. $\mathrm{A}\cup(\mathrm{B}\cap(\mathrm{A}\cup\mathrm{C})\cap(\mathrm{A}\cup\neg\mathrm{C}))$ 2. ...
0
votes
4answers
30 views

In how many ways can we arrange $n$ A's and $n-1$ B's into $2n-1$ slots?

There are $2n-1$ slots/boxes in all and two objects say A and B; total number of A's are $n$ and total number of B's are $n-1$. (All A's are identical and all B's are identical.) In how many ways ...
1
vote
1answer
64 views

Set Theory Laws

I have been working on the Inclusion Exclusion Principal and came across a problem where I am having difficulty identifying the transformation. Given Information: $\mid\mathrm{U}\mid = \mathrm{50}$ ...
3
votes
1answer
81 views

How to prove a duality about partitions of numbers?

I found the following theorem, which I think should be correct but I do not know how to prove it: Consider the set containing sums $A=\lbrace\sum\limits_{i=-a}^a iX_i\rbrace$ where $X_i$ is a ...
1
vote
1answer
32 views

Domination and Contraposition Laws - Discrete Math

Im having quite a bit of trouble understanding the Domination and Contraposition Laws in the instance below. I just do not see how the Domination Law, $\rho \wedge \mathrm{F} \leftrightarrow ...
1
vote
1answer
46 views

Permutations through different points

I'm watching Next (2007) and I'm trying to figure out a formula. The premise of the movie is that the protagonist can look into the future for two minutes and he is able to use this to alter his ...
1
vote
2answers
42 views

Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1) $. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
1
vote
0answers
36 views

What is the total number of magic squares for given N?

A magic square is a layout of the numbers $1,2, ..., n^2$ in a square of size n where the total of each row, column and diagonal is equal to $n(n^2+1)/2$. In the book 'The Zen of Magic Squares, ...
0
votes
1answer
20 views

Discrete Random Variables Help in Understanding

A company wants to form a team of 6 employees. Suppose that 60% of all staff available for selection are male, and that all team members are selected at random. Let X be the random variable for ...
1
vote
1answer
52 views

How many bit strings of length 15 have exactly three 0s?

I need help with this question: How many bit strings of length 15 have exactly three 0s?
0
votes
0answers
18 views

Low pass filter to maintain edge information

I am looking for a kernel as low pass filter that satisfy as:I must find a kernel that statisfies as follows: In the my reference paper, the author suggest gaussian kernel that is The gaussian ...
0
votes
1answer
28 views

The height of a general complete binary tree

there's this weird question in my book that I cant seem to grasp. Q: Let $T = (V,E)$ be a complete binary tree and $|V| = n$. What is the maximum height of $T$? Now, the textbook says that it is ...
2
votes
2answers
77 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
2
votes
1answer
35 views

Expected Values

Let X be the number appearing on the first die when two fair dice are rolled, and let Y be the sum of the numbers appearing on the two dice. Show that E(X)E(Y) does not equal to E(XY). I found E(X) ...
0
votes
2answers
24 views

Discrete mathematics and the big O problem.

Let f(n) = n + 100 and g(n) = n^2, show that f(n) does not dominate g(n). My work so far is this and the parts that I will bold print is the work of textbook that I don't understand: Let n > max ...
1
vote
1answer
31 views

Computational complexity and the big $\mathcal{O}$

I have a question about this Big $\mathcal{O}$ problem. I have the question down $90\%$, but the other $10\%$ isn't getting to me. I will write out the entire question and I'll point out the step, ...
1
vote
1answer
44 views

Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are ...
1
vote
0answers
38 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
0
votes
1answer
255 views

proof of a theorem in a paper

I was reading a paper named Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths by P. K. Jha (Indian J. pure appl. Math. 23(8): 585-606, August 1992). In one ...
1
vote
1answer
26 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
50 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 ...
3
votes
1answer
24 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 ...
5
votes
3answers
364 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
2
votes
1answer
35 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
43 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
45 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
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
25 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
48 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. ...
2
votes
2answers
58 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 ...
2
votes
3answers
148 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
2
votes
2answers
47 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 ...
0
votes
2answers
63 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 ...
0
votes
0answers
25 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} = ...
1
vote
2answers
92 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 ...
5
votes
1answer
70 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
80 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
37 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
votes
3answers
43 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
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 ...
0
votes
2answers
56 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} = ...
2
votes
2answers
52 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
11 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 ...
4
votes
3answers
55 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$. ...