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

learn more… | top users | synonyms

2
votes
1answer
89 views

Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
0
votes
1answer
44 views

Prove by Induction that: $1+nx\le (1+x)^n$?

$1+nx\le (1+x)^n$, for all real numbers $x>-1$ and integers $n\ge 2$. Can you please also explain a little of the basic step and the inductions step. Thank you in advance.
1
vote
3answers
49 views

Flip a coin 3 times. What is the probability that number of tails is odd?

We flip a fair coin (independently) three times. Define the following events: A = "the number of tails is odd" B = "the number of heads is even" What is the probability of event A and event B?
0
votes
1answer
31 views

Flipping a fair coin 3 times. T/F

We flip a fair coin (independently) three times. De fine the following two events: A = "the number of tails is odd" B = "the number of heads is even" True or false: The events A and B are independent. ...
1
vote
2answers
32 views

choice of integers,so that a condition is satisfied

With how many ways can we choose the integers $x_1,x_2, \dots , x_k$ such that the condition $1 \leq x_1<x_2< \dots <x_k \leq n$ is satisfied? Do I have to find $(y_1,y_2, ...
0
votes
2answers
21 views

Problem with multiply choice counting question

Hi I was working on this question for my exam review: Consider a multiple choice exam with 100 questions, in which for each question, four options are given to choose from. You answer each question ...
1
vote
1answer
22 views

how many different choices exist?

If we choose $k$ objects from $n$ with replacement and we don't ignore the order of the choices(e.g if we choose $3$ objects of $A,B$ with replacement,the results $AAB$ and $ABA$ are considered as ...
0
votes
3answers
45 views

How many subsets of a set $S$ of size $37$ contain $x$, but not $y$, where $x,y$ are distinct?

Let $S$ be a set of Size $37$, let $x$ and $y$ be distinct elements of $S$. How many subsets of $S$ are there that contain $x$, but do not contain $y$. Can you explain why the answer is $2^{35}$?
1
vote
4answers
52 views

arrangement of digits

With how many ways can we arrange the digits $1,2, \dots, 9$,so that $1$ precedes $2$ and $2$ precedes $3$? Also,with how many ways can we arrange these digits,so that between $1$ and $2$ there are ...
0
votes
1answer
36 views

Prove that if $n\geq1$ and $a_1, a_2, \ldots, a_n$ are any real numbers, then $|a_1 + a_2 +\ldots+ a_n| \leq |a_1|+ |a_2| +\ldots+ |a_n|$

I understand that if all values of $a$ are positive, then $|a_1 + a_2 +\ldots+ a_n| = |a_1|+ |a_2| +\ldots+ |a_n|$. I also understand that if any values of a are negative, then $|a_1 + a_2 +\ldots+ ...
0
votes
1answer
17 views

Need to get summation formula?

I have: $$ Y[k]= \frac 1N \sum_{n=0}^{N-1} exp^{j2\pi\epsilon n/N} $$ After simplification, I have to get: $$ Y[k]= \frac {\sin \pi\epsilon} {N\sin(\pi\epsilon/N)} \cdot ...
1
vote
1answer
40 views

Are every prime (except 2,3,5) divisor of some of 10^n+1?

Referring to Is it true, that every prime (except 2) can be found as a divisor of enough long series of 1-s? , I have the same question. I have the intuitive hyptohesis, that every prime can be found ...
1
vote
2answers
42 views

one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
0
votes
1answer
8 views

Congruent question with multiple congruence conditions?

Say if x ≡ 3 (mod 7) and y ≡ 5 (mod 7) How would I use the above given information to solve the problems below? xy ≡ 4 (mod 7) x ≡ y (mod 7) If you could explain it, that would be greatly ...
0
votes
1answer
46 views

sequences of six digits (0-9)

How many sequences of six digits(0-9) contain at least one 3, at least one 5 , and at least one 8? Can someone please give me a hint?
0
votes
1answer
38 views

Defining a bijective function from $2\mathbb{N}$ to $3\mathbb{Z}-1$?

$2\mathbb{N}=\{2n:n\in\mathbb{N}\}$ and $3\mathbb{Z}-1=\{3n-1:n\in\mathbb{Z}\}$ Work: So far, my plan is to first define a bijective function from $2\mathbb{N}$ to $\mathbb{N}$ and then define ...
0
votes
1answer
23 views

Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +…+ n(n+1) = n(n+1)(n+2)/3

The problem is :Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +....+ n(n+1) = n(n+1)(n+2)/3 I have established a base case for n=0, 0*1 = 0(0+1)(0+2)/3 = 0 I have also ...
1
vote
1answer
43 views

How to guess an explicit formula using iteration

EDIT: Adding in more information that is hopefully useful. This is part of a multi step question I'm trying to answer for my homework. First we were given a1 = -3 and a formula ak+1 = ak -1, for all ...
0
votes
3answers
52 views

Proving that function $f:[0,\infty)\rightarrow [0,\infty)$ defined by $f(x)=\frac{x^2}{1-x}$ is bijective.

I am having a bit of trouble with the algebra for proving that the function is injective. Basically I set $f(a)=f(b)$ for $a,b\in[0,\infty)$ and $a,b\neq 1$. ...
2
votes
1answer
61 views

How do I do this summation? [closed]

$$\sum_{i=0}^{N-2}\frac{(N-2)!(i+1)(i+2)(i+4)}{2(N-2-i)!N^{i+1}}$$ The answer is N.
0
votes
1answer
28 views

Statistics with discrete math

I am working on a homework problem and I think that I am doing this correctly but i am not sure. This is the question: An upper-level math class has 13 students: 4 of them are females. Two of the ...
3
votes
3answers
101 views

How many even functions are there from $\{-n, \dots,n \}$ to itself?

If $A=\{-n,-n+1, \dots, n-1,n \}$, how many functions $A \to A$ are there,that are even,so they satisfy the condition $f(-x)=f(x), \forall x \in A$? Is it maybe $(\frac{|A|}{2})^{|A|}$ ?
1
vote
1answer
17 views

how many arrays exist with specific elements?

How many $m \times n$ arrays exist with elements $0,1 \text{ or } 3$? I thought that there are $(m \cdot n)^3$ arrays,but I am not sure..Could you tell me if it is right?
1
vote
2answers
30 views

Why are there $n^m$ such functions?

A function from the set $A$ to the set $B$ is just a correspondance from each element of the set $A$ to an element of $B$.If $|A|=m$ and $|B|=n$,how many such functions exist?I saw that the solution ...
2
votes
0answers
13 views

Finding the number of relations on set S

I know the number of reflexive relations on a finite set is: $2^{n^{2}-n}$ The number of symmetric relations is: $2^{n+1 \choose 2} $ The number of antisymmetric relations: $2^{n}3^{n \choose 2}$ ...
0
votes
0answers
39 views

Removing backups in an exponential fashion

Background: I want to create a backup system that utilizes the full space of a hard-disk. Given that all backups are approximately equal in size this means that I can save a fixed amount of backups. ...
0
votes
2answers
31 views

Proving the statement?

In the case, if the statement is true, prove it, if false, give a counterexample. $$\forall a,b \in \mathbb N^+, 3| (a^2+b^2) \implies 3 |a \land 3|b$$ How do I prove this?
-1
votes
1answer
59 views

Exercise in discrete math [closed]

Find $q$ and $r$ as defined in the Division Algorithm when $a = 549$ and $b = 236$ Define $f : \mathbb{N} \setminus \{1\} \to \mathbb{N}$ by setting $f(n)$ equal to the largest prime divisor of $n$. ...
1
vote
1answer
20 views

calculate the number of different lottery columns

How many different lottery columns exist(of length $13$,with $1,2 \text{ or } X \text{ at each position}$) ? I have to use this theorem: Let $k$ a natural number and $E$ the set of all different ...
1
vote
0answers
24 views

How many decimal integers can be written?

Using the theorem,I am asked to answer the question,that I have written under the theorem. Let $k$ a natural number and $E$ the set of all different $(x_1,x_2, \dots , x_k)$,where $x_1 \in E_1, ...
0
votes
2answers
28 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...
2
votes
2answers
57 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
5
votes
4answers
358 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...
0
votes
1answer
54 views

Determine the probability that a randomly selected integer is divisible by one of several integers.

If you choose an element x uniformly at random from the set {1,2,...,100}, what is the probability that x is divisible by 4 or 5? Can someone explain why the answer is 2/5 please, thanks.
2
votes
2answers
58 views

In how many ways we can choose $3$ subsets from set $|S| = 20$ …

In how many ways we can choose $S_1$, $S_2$ and $S_3$ from a set which consists of $20$ element, so that : $S_1 \cap S_2 \cap S_3 = \emptyset$
0
votes
2answers
31 views

how do I figure out Which of the following is true?

I am studying for my exam and I am kind of stuck on this question, how is it that the answer is a)? can someone explain this please. Which one of the following is true? a) $$\sum_{k=0}^{n} ...
2
votes
4answers
66 views

Proving for all n that $\sum_{i=0}^n \frac1{2^{i}} < 2$

Proving for all n $\in \mathbb N$, $$\sum_{i=0}^n \frac1{2^{i}} < 2$$ Hint. First prove that the left hand side can be expressed in closed form, i.e. without using the summation operator. This is ...
0
votes
1answer
37 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
0
votes
1answer
10 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
0
votes
0answers
66 views

Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
0
votes
0answers
32 views

How to calculate the combined frequencies of a DCT matrix?

Given a 2D matrix of dimensions w1,h1. I preform a DCT 2D transform on the matrix (DCT = DCT type 2). I get a 2D result matrix. This matrix has two frequency axes - x,y (which are simply the ...
1
vote
1answer
30 views

Pumping lemma contradiction

I have to prove that the language $A_{1}= \{\alpha \in \Sigma^{*}|c^{a}(\alpha)>c^{b}(\alpha) \}$ where $\Sigma=\{a,b\}$, where $c^{a}(a)$ means the number of $a$ in $\alpha$, and $c^{b}(\alpha)$ ...
0
votes
1answer
17 views

choosing poker hand with a specific card

How many ways can you choose at least one A from a deck of card in a poker hand? I just wanted to double check my answer, would it be C(52,5)- C(48,5) Help is much appreciated,
1
vote
2answers
36 views

Different ways of picking a committee of $12$ women and $10$ men

$12$ women and $10$ men are on the faculty. How many ways are there to pick a committee of $7$ if (a) Claire and Bob will not serve together, (b) at least one woman must be chosen I'm not sure ...
0
votes
2answers
30 views

rolling dice 6 times, outcomes showing of 2 sixes

If 6 dices are rolled, in how many ways will exactly 2 sixes show up? I was thinking that it would be 6*6*5*5*5*5, am I right?
1
vote
1answer
192 views

Derive expressions for the formal power series $\cos(kz)$ and $\sin(kz)$, where $k$ is an arbitrary integer

I'm working on some past exam questions, and I am struggling with the second part of this question: Define the formal power series by the formulas: $$\sin(z) = \sum^{\infty}_{n=0} ...
2
votes
1answer
31 views

Eulerian connected graph [closed]

I have a question on grap theory as follows $G=(V,E)$ is a connected graph. Prove that G is Eulerian if and only if there is a partition $E_j$, $j=1,...,m$ of the set of edges such that every $E_j$ ...
0
votes
1answer
26 views

Can't understand trivial discrete logarithm problem

I have a seemingly trivial problem with description: Find all discrete logarithms of base 2 of all non-zero elements in $Z_{11}$ field. I'm basing my learning on the notes I managed to grab ...
0
votes
0answers
26 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
1answer
28 views

Proving questions about posets

How do I tackle a proof about posets? I have know idea how to approach this problem. Thanks! Prove that if all subsets of a poset P have least upper bounds, then all subsets of P have greatest lower ...