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
votes
0answers
32 views

Significant Figures calculation [closed]

$$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
12 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 [closed]

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
1answer
58 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
23 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
21 views

Write the following statements in symbols [closed]

(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.
0
votes
1answer
29 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}$$ ...
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
23 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
40 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
15 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
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 ...
-2
votes
2answers
29 views

One-to-one and binary strings [closed]

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 [closed]

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 .
1
vote
2answers
71 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 ...
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
37 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 ...
4
votes
2answers
420 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 ...
-1
votes
2answers
102 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? ...
0
votes
1answer
36 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 ...
0
votes
0answers
31 views

Example of nonempty partially ordered set (S, R)

When asked a question like this: Give an example of a nonempty partially ordered set (S, R) that does not have incomparable elements. Draw the Hasse diagram for this partially ordered set would this ...
-1
votes
1answer
51 views

Binary strings and discrete math

Question: Let $S$ be the set of binary strings of length $30$ with $10$ $1$’s and $20$ $0$’s. Let $A$ be the set of the first $30$ positive integers $\{1,2,3,\dots,30\}$. Let $B$ be the set of all ...
4
votes
1answer
80 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
2
votes
1answer
26 views

Apply Hall's theorem to a problem

I have only seen Hall's theorem applied on the marriage problem. For the problem below I have to use this theorem I guess. For me it's still difficult to apply this to a problem. Problem: Consider ...
-1
votes
2answers
30 views

Preimage of the set of $x$-values

What is the preimage of the set of $x$-values between $0$ and $1$? i.e. $f^{−1}(\{x\mid 0<x<1\})$? Explain. I get that we have to find the inverse image $f^{-1}(S) = \{a\in A \mid f(a) ...
0
votes
1answer
30 views

cardinals proves - bigger or equal than [closed]

Let $k_1, k_2, m_1, m_2$ be cardinals. Prove that if $k_1 \leq k_2$ and $m_1 \leq m_2 \implies k_1m_1 \leq k_2m_2$. I dont know where to start from. Any help will be appriciated.
0
votes
1answer
25 views

Floor fuctions question as it relates to image

What is the image of x values between 0 and 1? i.e. 𝑓({𝑥|0<𝑥<1}? Explain. I do not want the answer i just want to understand how to get the answer. While my professor has explained this in a ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
0
votes
1answer
23 views

Another Venn problem

We are to create a Venn Diagram for $B \cap A = A$. I have created this, I do not think this is correct. Can anyone shed some light on this?
0
votes
2answers
44 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 ...
3
votes
5answers
127 views

Solve $x^{2}\equiv 24 \mod 125$

Here's a congruence I'm trying to solve: $$x^2\equiv24 \mod 125$$ What are the techniques I could use to solve it? I know about Euler's phi function, Fermat's little theorem and Chinese remainder ...
2
votes
1answer
44 views

Given a set S of ten positive real numbers whose product is 32, show that S contains six numbers whose product is at least 8.

Given a set $S$ of ten positive real numbers whose product is $32$, show that $S$ contains six numbers whose product is at least $8$? I tried to prove it, but it seems that the question is ambiguous. ...
0
votes
1answer
32 views

How to represent n-cube graph in form of a set?

Can we represent an n-cube graph in the form of a set of edges? If so, then how can we represent a Q4 graph?
0
votes
1answer
13 views

Anti-symmetric or asymmetric for a relation between pairs in the set of Z x Z?

Is this anti-symmetric or asymmetric? I at first thought asymmetric because anti-symmetric would mean a = c and b = d which would not be true. But because the domain is the Cartesian product of ...
4
votes
1answer
47 views

Struggling with inequality involving a bunch of binomial coefficients

I want to find a lower bound on $n$, i.e. isolate $n$, or more realisticly, approximate $n$ that satisfies the following : $$ {n \choose k}\left( 1 - \frac{{n \choose \frac{n-1}{2} - k}}{{n \choose ...
0
votes
1answer
19 views

Show that if n and K are poitive numbes then

Show that if $n$ and $k$ are positive integers, then $ {n+1 \choose k}= \frac{(n+1) {n \choose k-1} }{k}$ I am most likely doing this wrong, but here is what I have: There exist integer $a$ such ...
0
votes
0answers
17 views

Venn Diagram issue.

In my Discrete math class we have to figure out how to draw each question into a Venn diagram. I know how to do the simple A U B and so on, I have found many examples of those. My issue is we need to ...
0
votes
1answer
23 views

What is the set complement

If $A = \{x \ |\ 0 < x < 10\}$ (where the universal set is the set of positive real numbers less than or equal to $20$), what is the complement of $A$? I am thinking that it is the integers ...
0
votes
1answer
28 views

Probability of tossing a coin 1000 times and coming up with heads

I have this problem on my final review sheet and was wondering if someone can go over it with me You are tossing a fair coin 1000 times. Find what is the probability that it comes up heads (a) $500$ ...
0
votes
2answers
20 views

Probability of losing and gaining money in a card game

I have done some simple flipping coin problems but I am not sure how to solve this one. This is from a review sheet for my final. In each round of a game, three cards are dealt from the standard ...
0
votes
1answer
23 views

Determining if the relation is a poset

We have this question on our final review sheet and I want to make sure I fully understand it before the exam. I looked up several examples but they did not help. Determine whether the following ...
0
votes
1answer
24 views

Differentiating social surplus function

Can someone possibly explain how to >>make sense<< of the following identity: $\int \frac{\partial \ max_d \{ u(x,d) + \epsilon(d) \} }{\partial u(x,d)} q(d\epsilon \lvert x) = \int I\{d = ...
0
votes
1answer
33 views

For which values of $n$ is $f$ one-to-one/onto?

for each $n \in \mathbb Z$ the mapping $f: \mathbb Z \to \mathbb Z$ is defined by $f(x) = nx$. Let $z_1, z_2, n \in \mathbb Z.$ Let $nz_1 = nz_2$. Then $z_1 =z_2.$ Now suppose $n = 0,$ and $0z_1 ...
2
votes
1answer
21 views

Using Inclusion-Exclusion Principle to find number of ways to distribute envelopes

I have encountered this problem on a past paper: In how many ways can 675 identical envelopes be divided, in packages of 25, among four student groups so that each group gets at least 150, but no ...
1
vote
1answer
56 views

Expressing conditional statements using quantifiers and predicates in Predicate Logic: how to recognize the hypothesis and conclusion in statement

I was solving questions of Discrete Mathematics and Its Applications By Kenneth H. Rosen Chapter 1 The foundations: Logic and Proofs , when i got stuck at this problem; two similar problems are ...
0
votes
1answer
38 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...