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
0answers
11 views
1
vote
1answer
123 views

Eccentricity in corona product

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
-1
votes
2answers
19 views

Reflexive, Symmetric, Anti Symmetric and Transitive

I am really struggling with these concepts. I understand the basic principle, but cannot really find a situation where something is not reflexive, symmetric or transitive. (Clearly I don't understand ...
-1
votes
2answers
68 views

How many ways can a woman polish her nails if she uses one of two colors on each nail?

A woman is preparing to go to a party and would like to have her nails polished. Suppose she wants to use either the light pink or red nail polish on each nail, how many ways can shepolish her nails? ...
2
votes
3answers
57 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
-5
votes
0answers
15 views

discrete mathematics matrix relation proof [on hold]

Show that if MR is the matrix representing the relation R, then M[n] R is the matrix representing the relation Rn.
-3
votes
0answers
29 views

SimRank Example? [on hold]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
3
votes
0answers
116 views
+500

Minimal “sumset basis” in the discrete linear space $F_2^n$

Let's $$ C\subseteq F^n_2, $$ $$ 2C=C+C=\{\bar\alpha+\bar\beta\ | \bar\alpha,\bar\beta\in C\}. $$ I need to find $C$ such that $2C=F_2^n$ and $|C|$ is minimal. I have found the following ...
1
vote
1answer
37 views

Find new generating function, given an arbitrary generating function

In a discrete mathematics past paper, I am asked to find the generating function for the sequence $$\langle a_0, 0, a_2, 0, a_4, 0, \ldots \rangle,$$ given that $A(x)$ is the generating function for ...
1
vote
3answers
86 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
0
votes
1answer
60 views

Proving set identities

I am attempting to work on some proofs for my math assignment, but I'll be honest in that I am really struggling to understand them. I read through the power point given by my teacher; however, even ...
0
votes
0answers
16 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
-5
votes
1answer
35 views

Discrete math halp!? [on hold]

Define the relation $\rho$ on $\mathbb{R}$ by the rule: $\forall x, y \in \mathbb{R},~ x \rho y$ if and only if $\exists n \in \mathbb{Z}$ such that $y = x + n\pi$. In other words, $x ρ y$ if and only ...
0
votes
1answer
28 views

q-binomial Identity

Unfortunately I am not able to solve the following problem: I tried finding a bijection similar to the prove of this binomial identity: $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$ ...
2
votes
3answers
5k views

Sum of digits and product of digits is equal (3 digit number)

My child got a question in school (grade) that is: Find biggest and smallest 3 digits number, which has sum of it's digits equal to product of those digits. Help please since I cannot explain my ...
5
votes
2answers
53 views

Find the generating function of this sequence

I need to find the generating function of the sequence $c_n = (a_0, a_1, a_2, \ldots)$, where: $$a_n = \begin{cases} 2^{n/2} & \text{if $n$ is even,} \\ 1 & \text{if $n$ is odd.} ...
0
votes
1answer
11 views

Maximization of a statistical property of a subset of random numbers

I have encountered a maximization problem which could be formulated as a discrete mathematics problem arising from statistics, but I don't know where to start or which techniques could be applied to ...
2
votes
3answers
64 views

Is $R=\left \{ (a,a),(a,b),(b,a),(b,b),(c,c),(c,d),(d,c),(d,d) \right \}$ an equivalence relation on $X$?

Let $X= \left \{ a,b,c,d \right \}$ and $R=\left \{ (a,a),(a,b),(b,a),((b,b),(c,c),(c,d),(d,c),(d,d) \right \}$. I want to show that $R$ is an equivalence relation on $X$. My work: $R$ is reflexive: ...
3
votes
1answer
433 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
7answers
183 views

How to show $\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$?

Show that $\,\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 ...
-1
votes
0answers
16 views

Stirling numbers: $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ [on hold]

How can I show $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ holds for the Stirling numbers, $n\geq m \geq k \geq 2$.
2
votes
1answer
31 views

Counting the functions with f(i) ≤ f(i+1) for all i=1,..,n-1

How can I determine how many functions are weakly monotone increasing from $[n]\equiv \{1,..,n\}$ to itself: $$ f:[n] \to [n] \text{ so that } f(i) \leq f(i+1) \; \forall i\in[n-1]$$ Thank you for ...
0
votes
1answer
330 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
0
votes
1answer
34 views

find the number of one-to-one function $[\pm n] \rightarrow [\pm n]$

the permutaion of $[\pm n]$ is a bijective (one-to-one) function $\pi:[\pm n] \rightarrow [\pm n]$ so that $\pi (-i) = -\pi(i)$ . $[\pm n]:=\{1, \dots, n-1, \dots, -n\}$. i have to find and determine ...
0
votes
2answers
2k views

DNF and CNF logic problem

So i want to find the DNF and CNF of : $ x \oplus y \oplus z $ . I tried by using $ x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y) $ but it got all messy and stuff, I also plotted it in ...
-1
votes
0answers
32 views

Significant Figures calculation [on hold]

$$400 \times 185=74\,000$$ I need to get this in least amount of Sig figs. Can someone please explain the rules of calculating the needed amount of significant figures?
0
votes
0answers
11 views

Prove Ackermann's function by induction

I have to prove the following property $$A(x,y)>x$$ of Ackermann's function. Do we do the following? We will show that $$A(x, y) \geq A(0, x+y)$$ by induction on $k=x+y$. Base case: For $k=0$ ...
2
votes
2answers
36 views

How can I determine the sequence which has this generating function?

In a discrete mathematics past paper, I must find the first eight terms of the sequence whose generating function is $$\frac{x^2}{(1-x)(1-2x)}.$$ I have looked at both of the following posts: How ...
0
votes
1answer
30 views

Sum of $n$ numbers dividable by $n$ from $(n-1)^2-1$ numbers.

I'm trying to solve some problem in the past few days(by the way, my first question here is some sort of a direction for solution - or maybe not). Problem: Suppose that we have a list of $(n-1)^2-1$ ...
0
votes
2answers
32 views

Closed form formula for discrete sums [on hold]

Is there a general way to obtain a closed form formula for any discrete sum of the form: $\sum_{a}^{b}f(n)$ with certain restrictions on the form of $f(n)$, much like how we can find closed form ...
1
vote
0answers
46 views

Books of set theory and algebra

Someone knows two good books they focus more on exercises: On following topics: 1) One of set theory and abstract algebra( Groups, ring, modules, ecc..) 2) Another on combinatorics, and discrete ...
1
vote
1answer
57 views

how many squence $a_1, \dots ,a_n$ there are so that the product of $a_1 \cdot a_2 \cdot \dots \cdot a_n$ divisible by 10?

i have to provide how many squences $a_1, \dots ,a_n$ with $a_i\in \{1,\dots,9\}$ so that the product of $a_1 \cdot a_2 \cdot \dots \cdot a_n$ divisible by 10? how can i begin with this problem?
2
votes
1answer
21 views

Multiplying a floor function to a number

Is it correct to write: $\cfrac{\left\lfloor{\cfrac{\pi y^2}{3\sqrt{3}x^2}}\right\rfloor}{n} \times\sqrt{3}x =\left\lfloor\cfrac{\pi y^2}{3xn}\right\rfloor$ ?
0
votes
0answers
19 views

Write the following statements in symbols [on hold]

(a) Every integer x has a paired integer y such that the difference between x and y is exactly 2. (b) There exists a real number z such that the product of z and any other real number is 0.
3
votes
2answers
32 views

proving a function as surjective

How can I prove a function is surjective? In the function $f: \Bbb{R}\to \Bbb{R}$, $$f(x) = 4x+7$$ we take $x = y-\frac{7}{4}$ and show that $f(x)=y$. How can this method prove that this function is ...
0
votes
1answer
21 views

what is differences between digraph and subgraph

what is the difference between digraph and subgraph in discrete-mathematics. Any one explain the example of these graphs.
5
votes
1answer
33 views

Sets raised to exponents

"Find two non-empty sets $A$ and $B$ for which $A^B$ and $B^A$ are not the same size." I'm really not sure what this means or how to even go about attempting this... Can anyone provide an example of ...
0
votes
1answer
37 views

Inductive step in Proof of Induction

Prove by induction: $1^2 + 3^2 + 5^2 + · · · + (2n − 1)^2 =\frac n3 (2n − 1)(2n + 1)$ So first I proved the base case ($n = 1$) which holds true. Tried doing the Inductive step where $n = n + ...
1
vote
1answer
35 views

Proving by Contradiction

Prove by Contradiction Suppose $a, b \in Z$. If $4|(a^2 + b^2)$, then $a$ and $b$ are not both odd. So the contradiction: Assume $4|(a^2 + b^2)$, where $a$ and $b$ are both odd. Then $a=2k+1$, ...
0
votes
1answer
33 views

How to calculate the shielding time and determine the time step

The problem is illustrated as follows. A shielding plate scans over a target plate at a constant speed $v_{scan}$ and dynamically shadows the target plate to adjust the exposure time of the light ...
1
vote
2answers
2k views

Let A and B be sets. Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C.

Can you verify my proof if it is right? Let A and B be sets. (a) Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C. (b) Show that A is a subset of ...
0
votes
1answer
14 views

Correctness of a set with respect to another set.

Is there a specific measure for correctness of a Set w.r.t another set? e.g. Consider there's a base set A, and a set B whose correctness needs to be measured w.r.t set A. Now B might contain some ...
0
votes
2answers
42 views

Show that the average depth of a leaf in a binary tree with n vertices is $ \Omega(\log n)$.

Let $T$ be a tree with$n$ vertices, having height $h$. If there are any internal vertices in $T$ at levels less than $h — 1$ that do not have two children, take a leaf at level $h$ and move it to be ...
4
votes
2answers
410 views

What is meant by the delta equivalent sign?

What is the meaning of the delta equivalent ($\overset{\Delta}{=}$) sign? I met this in a communication theory text. It said, signaling rate: $r\overset{\Delta}{=} 1/D$ symbols/s or also called ...
0
votes
1answer
23 views

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other. For example, this is not allowed ...
1
vote
2answers
69 views

How to prove that $C\cdot\aleph_0=C$

How can I prove that $C\cdot\aleph_0=C$? I tried this: Given that $k\cdot 1=k$ and $C\cdot C=C$ if $C\cdot C = C \wedge C\cdot 1 = C \wedge C>|\mathbb N|>1$ then $C\cdot |\mathbb N|= C$ c is ...
-2
votes
2answers
29 views

One-to-one and binary strings [on hold]

Assume $T$ be the set of binary strings of length $30$ with $10$ $1$’s and $20$ $0$’s. Let $X$ be the set of the first $30$ positive integers $\{1,2,3,…,30\}$. Let $Y$ be the set of all subsets of $X$ ...
-4
votes
0answers
21 views

Gauss elimination [on hold]

Why we change row in matrix ? a=2 0 1, 0 22 1, 0 -3 -23, this is matrix. ~ a=2 0 1, 0 -3 -23, 0 22 1 Here, in first matrix , why we change second row to third row .
0
votes
1answer
38 views

Prove by either direct proof or contraposition

I have a question like this: By direct proof or by contraposition: Let $a \in Z$, if $a \equiv 1 \pmod{5}$, then $a^2 \equiv 1 \pmod{5}$. Hypothesis: $a \in Z,~a \equiv 1 \pmod{5}$ Conclusion: $a^2 ...
1
vote
3answers
36 views

Trouble understanding One-One and Onto function.

So I have a question like this: Let $g$ be a function $g : \mathbb{Z} → \mathbb{Z} \times \mathbb{Z}$ such that $g(n) = (2n, n + 3)$. And I want to find if this is onto and one-one. But I'm ...