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

learn more… | top users | synonyms

1
vote
1answer
34 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits ...
1
vote
1answer
44 views

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers.

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers. I assume I'm supposed to use induction. base step is easy. ...
0
votes
3answers
47 views

Check if there exists any non negative integral solution to this equation

How to find out if there exists at least one non negative integral solution to the equation ax + by = c in x,y ? Note that a,b,c are integers in the range ...
0
votes
0answers
29 views

Notations for elementary set theory

I wish to understand the following notations which defined for every cardinals, $a,b$: $P(a,b) = \left| In(A,B) \right|$ $C(a,b) = \left| P_b(A) \right|$ $E(ab) = \left| Eq(A,B) \right|$ ...
0
votes
0answers
15 views

Cactus construction

Is there someone who can explain me how can one construct the cactus of the minimum cuts of a graph? Or someone who can suggest me a book about cactus construction theory? Thank you in advance
1
vote
1answer
26 views

Discrete math: Sum of Geometric series on a problem - Notes make little sense.

I've been reading a PDF of slides from my Discrete Math I professor. The title is Sums, Products and Asymptotic Estimations. He gives us a problem to fire off the lecture, which is the following: ...
2
votes
2answers
21 views

Elements with order 3 in group $F_{16}/\{0\}$

If you have the finite field $GF(16)$ and you define the group $GF(16)/\{0\},*$ this group is cyclic. I need to determine how many elements in this group have order 3. Of course you could just try out ...
1
vote
1answer
24 views

Prove summation related to cycles

Let $b_r(n,k)$ be the number of n-permutations with $k$ cycles, in which numbers $1,2,\dots,r$ are in one cycle. Prove that for $n \geq r $ there is: $$ \sum_{k=1}^{n} ...
1
vote
1answer
21 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
3
votes
1answer
45 views

Elements of subfield $F_{8}$ of $F_{2}[x]/(x^{6}+x+1)$

I need to find the elements of the subfield $F_{8}$ of $F_{2}[x]/(x^{6}+x+1)$ in their standard representation. I know that $F_{2}[x]/(x^{6}+x+1)$ represents the residu classes of polynomials modulo ...
0
votes
0answers
20 views

Discrete Math - domain and range

I for the life of me cannot figure this out. Can anyone help? Find the domain, range, and when A=B, the diagraph of the relation R. A={1,2,3,4,8}=B; a R b if and only if a|b. A.Domain {1,2,3,4,8} ...
3
votes
3answers
53 views

Prove that $3^n > 2n^2 + 3n$ for $n \in [4,\infty) \cap\mathbb{N}$

If $n$ is a natural number $n\ge 4$, prove that $3^n > 2n^2 + 3n$ I assume I am supposed to use induction. The base $n=4$ step is clear, but how do I prove the inductive step. I tried several ...
0
votes
1answer
31 views

Modulation and translation properties of DFT

Consider the discrete fourier transform over a finite field $GF(q)$. Let also $\omega$$\in$$GF(q)$ be an element of order $n$ and which is an $n$-th root of unity. Definition 1. Let $v$ = ($v_0$, ...
0
votes
1answer
39 views

How many ways you can make change for an amount N using A and B monets.

I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1. Any idea how to solve this? It ...
0
votes
2answers
27 views

Find the general solution to the following recurrence

Find the general solution to the following recurrence: $$nC_n=anC_{n-1}+bC_{n-1}$$ where a and b are constants.
0
votes
0answers
24 views

Min cuts of a graph with odd edge-connectivity

Let $G=(V,E,w)$ be a weighted graph with integer weights, odd edge-connectivity $k(G)$ and $|E|$ minimum cuts that are linearly independent (i.e. every edge is contained in a minimum cut). Is it true ...
4
votes
4answers
81 views

Find a generating function for $\sum_{k=0}^{n} k^2$

Find a generating function for $\sum_{k=0}^{n} k^2$ I know my solution is wrong, but why? My solution: If $F(x)$ generates $\sum_{k=0}^{n} k^2$ then $F(x)(1-x)$ generates $k^2$. ...
2
votes
2answers
89 views

Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
1
vote
1answer
25 views

Number of ways to partition a set into three subsets with given sum.

Given a set S, with n elements out of which if any element is repeating then it is repeated at maximum 2 times. How to count the number of ways in which S can be partitioned into 3 subsets such that ...
3
votes
2answers
55 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
0
votes
1answer
79 views

counting runs of empty bins

Here is a variation of balls and bins problem. Throwing $m$ balls uniformly and independently into $n$ bins labeled $0,1,2,\ldots,n-1$. Counting empty bins of run length $k$: There is a $k$-gap ...
1
vote
1answer
22 views

Is the property reflexive, symmetric, anti-symmetric, transitive, equivalence relation, partially ordered given the relation below?

I'm working on this and I'm supposed to figure out if the following properties apply to the below relations. Properties are: ...
0
votes
0answers
36 views

Simple Math Problem on Interval

It's not clear for me. I see this wikipedia page for a difference of half interval on $\mathbb{R}$ and interval on $\mathbb{R}$? For example $$ \{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} ...
1
vote
1answer
31 views

Easy Z-Transform doesn't match in Wolfram/Matlab

I have this function: $$g(k)=2*(\frac14)^{k-1}+(\frac18)^k$$ I calculate the Z-transform in this way, applying the delay property: $Z[x(k-1)]=z^{-1}X(z)$ $$G(z)=\frac{8}{4z-1}+\frac{8z}{8z-1}$$ ...
0
votes
1answer
17 views

Curve fitting to connect certain points

Well the image says everything, anyone has any idea how to, or where should i look to be able to draw the BLACK curve ? in fact i need a function that would connect the summits of these red dotted ...
0
votes
2answers
42 views

Using the resolution proof system

so I can't figure out something when using the resolution proof system. We are given: {¬a → ¬b, b} on a what I can't figure out is why: ¬a → ¬b becomes a ∨ ¬b I understand it becomes an ∨, but why ...
2
votes
0answers
45 views

Which of the following 5 statements are true?

I am having trouble finding which of the following statements are true: Which of the following statements are true? [a] Pizza does NOT have mushrooms [b] Pizza does have mushrooms AND ...
1
vote
1answer
12 views

Composition on sets

[(1,2,3,4) ○ (1,2)(3,5)]^-1 The solution has the following steps: f=(1,2,3,4) g=(1,2)(3,5) Compute f○g: Where can I find information regarding what the steps are doing in this problem? I understand ...
2
votes
2answers
37 views

GCD(a,b) as a linear combination of a,b

I know that the GCD(a,b) can be written as a linear combination of a,b (ma + nb = GCD(ab)). How can I select which coefficient (m or n) is positive? In other words, for example, if after executing ...
0
votes
0answers
21 views

Obtaining Z-transform from the Laplace Transform

I'm learning Z transform, and the teacher has given us this equation: (which i can't prove.) F(z)= Sum of residues {(F(s) / (1 - exp(sT)Z^-1 )}|poles of F(s) where: F(z) is the z transform of ...
0
votes
0answers
32 views

Relation R on the property of the set of all real functions, Discrete Mathematics

0 down vote favorite So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: ...
0
votes
1answer
34 views

Total number of additions and multiplications in the following code?

Really stumped on this question... I think it's n(n+1)? or is it(n+1)^2? Will someone help me? Thank you!! What is the total number of additions and multiplications in the following code? ...
1
vote
1answer
28 views

Expected utility representation

I am stuck on some question on utility theory. The question is as follow: Consider $A=[0,+\infty)$, and $Q=${F-cumulative distribution function on $A: \int^{+\infty}_0 x dF(x)<\infty$}, the set of ...
0
votes
0answers
37 views

Big O notation problem

Can someone please explain to me why this is true? Thank you in advance! If $f(n)=Θ(n^2)$ and $g(n)=Θ(n^2)$ then $(f+g)(n)=Θ(n^4)$ where we define $(f+g)(n)=f(n) +g(n)$ for all $n$.
1
vote
0answers
21 views

element subset for adjacency matrix

I am trying to create an element of a matrix that is a subset of a larger matrix. However, I am told that my subscripts do not match. I wanted other people's opinion as to what I am doing wrong and ...
-1
votes
0answers
32 views

Relation R on the property of the set of all real functions

So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: Reflexive Symmetric Anti-Symmetric Transitive ...
1
vote
1answer
24 views

Equality of binomial coefficients

I have seen that the following equations are equal, but are wondering how this is shown ${n \choose m} \cdot 1 \cdot 3 \cdots (2m-1)\cdot 1 \cdot 3 \cdots (2n-2m-1) = \frac{n!}{2^n} {2m \choose m} ...
-1
votes
3answers
83 views

Basic facts on $\ker(f)$ [closed]

If $A, B$ are groups for: $f:A \rightarrow B$ $f(xy) = f(x) f(y)$ $\forall x,y \in A$ and $\ker(f)=$ { $a \in A$ | $f(a) = e$ }. Prove that: $\ker(f)$ is a subgroup in $A$ $\ker(f) ...
0
votes
1answer
24 views

What is the time complexity of an $O((\ln n)^{\ln n})$ algorithm?

How can the time complexity of an $O((\ln n)^{\ln n})$ algorithm be simplified and compared to some other time complexities?
0
votes
1answer
27 views

How to find the number of possible permutations in a composition function

So I am given 2 maps. $$h = \begin{pmatrix} 1&2&3&4\\2&3&4&1 \end{pmatrix}$$ and $$k=\begin{pmatrix} 1&2&3&4\\ 2&1&4&3 \end{pmatrix}$$ I am asked to ...
1
vote
2answers
19 views

Inverse of a composite function

In a homework assignment, I am asked to find $(P_3 \circ P_1)^{-1}$ knowing: Let $P_1 = (3\ 4\ 1\ 2\ 5), P_2 = (3\ 5\ 1\ 2\ 4)$ and $P_3 = (5\ 1\ 4\ 2\ 3)$ be three permutations. I am second-guesing ...
-2
votes
1answer
36 views

Comparing floor and ceiling fractions

Is the following true for all integers x>1: $\lfloor{\frac{2x}{3}}\rfloor \geq \lceil \frac{x}{2}\rceil$
0
votes
1answer
58 views

Find this 2 groups? [closed]

Let $X$ be a group such that $Y\trianglelefteq X$. Find group $X, Y $ such that $Y\trianglelefteq X$ and $Y$ has a subgroup $Z\leq Y$ such that $Z\trianglelefteq X$.
0
votes
1answer
29 views

Discrete math Group - Isomorphism and Automorphism

Let G be a Cyclic group Prove or disprove: A.let $ a,b \in G \quad $ so the function $ f:G \to G,f(a^k) = b^k$ is Automorphism of G(which means G is Isomorphism to herself) B.let a,b generators ...
0
votes
1answer
35 views

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=\Theta(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ ∀$n$.

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=Θ(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ $∀ n$. Is the above true or false. I would say its false but honestly its a guess and i ...
2
votes
2answers
53 views

Prove that n!+1 contains a prime factor greater than n and use this to prove that there are infinte many primes [duplicate]

Prove that $n!+1$ contains a prime factor greater than $n$ and use this to prove that there are infinitely many primes. I said assume that $n!+1$ contains a prime $p$ which is less than or equal to ...
1
vote
1answer
43 views

Cartesian Product of $\emptyset \times \emptyset$

A bit of homework that I'm not sure on. The question reads: Let $A=\{a\}$ and $B=\{1,2\}$. Find the following: $$\mathcal{P}(A) \times \mathcal{P}(B)$$ The worked out solution is as follows. $\{ ...
0
votes
1answer
46 views

How many 10-bit strings with more 0’s than 1’s?

I have to pick the answer from: a.512 b.386 c.256 d.252 e.none of these The number of bit strings of length 10 with n 0's (or n 1's in fact): is C(10,n) , where C(a,b) = a! / [(a-b)!b!] is the ...
0
votes
1answer
38 views

Probability Question on Urns and numbered balls

An urn contains $10$ balls numbered $1$ to $10$. A set of $3$ balls is drawn from the urn. Let $X$ record the largest number showing. Compute $P(X=7)$. I have to do this on excel. I'm assuming I ...
4
votes
2answers
55 views

What is the value of the following? $3^{302} \mod 5.$

I have to choose from a. 0 b. 1 c. 2 d. 3 e. 4 I think its e. 4 because $$3^{302} = 3^{300} \cdot 3^2 = 3^{4\cdot 75} \cdot 3^2 = (3^4)^{75} \cdot 3^2.$$ Applying Fermat's Little Theorem to ...