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

learn more… | top users | synonyms

1
vote
1answer
20 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
0
votes
0answers
10 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + βj ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
1
vote
1answer
14 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
3answers
33 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
2
votes
2answers
43 views

At a party $n$ people toss their hats into a pile in a closet.$\dots$ [duplicate]

Question: At a party $n$ people toss their hats into a pile in a closet. The hats are mixed up, and each person selects one at random. What is the expected number of people who select their own hats? ...
0
votes
2answers
21 views

Let Alphabet have only one unary function of symbol f. Prove that every term must have 3K+1 symbols for some k≥0.

I believe in order to solve this question, I have to perform induction on the complexity of terms. But I'm not sure how to begin.
0
votes
2answers
10 views

Find the probability of each outcome when a biased die is rolled, if rolling a 2 or 4 is three times as likely as rolling each of the other$\dots$

Question:Find the probability of each outcome when a biased die is rolled, if rolling a $2$ or $4$ is three times as likely as rolling each of the other four numbers on the die and it is equally ...
0
votes
0answers
37 views

A city wants to encourage downtown

could you please help me with this ( part d ) A city wants to encourage downtown employees to use public transportation. Below is the time in minutes to get to work on one morning according to ...
1
vote
3answers
87 views

Discrete Mathematics Function Proof

The question is as follows : Let $f:A\rightarrow B$ be a surjective function and let $C$ be a subset of $B$. Prove $f(f^{-1}(C)) = C$. I understand what the question is asking. It's basically ...
1
vote
1answer
24 views

Number of ways distribute 12 identical action figures to 5 children

Need a little help with this problem. Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most ...
1
vote
1answer
29 views

Derivative of logistic loss function

I am using logistic in classification task. The task equivalents with find $\omega, b$ to minimize loss function: That means we will take derivative of L with respect to $\omega$ and $b$ (assume y ...
1
vote
1answer
33 views

How to find the Direct Discrete Laplace Transform of ${2n \choose n}$

Some time ago I developed a discrete version of the Laplace transform for the purpose of calculating sums and solve finite difference equations with constant coefficients. The notes below are a ...
0
votes
1answer
60 views

what is the coefficient of following expression

what is the co-efficient of $x^{50}$ in the expansion of $$\frac{1}{(1-x^{1.7})(1-x^{1.8})(1-x^{2.6})(1-x^{3.0})(1-x^{4.0})(1-x^{6.7})(1-x^{7.5})(1-x^{8.2})}$$ can you please explain me the logic
0
votes
2answers
25 views

Prove $n\in \mathbb{N}^+,\sum_{k = 0}^n C(n, k) = 2^n$, using $\dots$

Question: 55.) b.) Conclude that there are $C(m + n, n)$ paths from $(0, 0)$ to $(m , n)$. 57.) Prove $n\in \mathbb{N}^+,\sum_{k = 0}^n C(n, k) = 2^n$, using exercise 55. [Hint: Count the number of ...
2
votes
1answer
52 views

Prove that limits can be used for asymptotic analysis

True or false: If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number. I'm not sure what needs to be done to demonstrate this. I do ...
5
votes
3answers
649 views

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
1
vote
1answer
31 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
1
vote
1answer
13 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
1
vote
2answers
48 views

Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be ...
1
vote
2answers
26 views

Permutations and Discrete Math

can someone explain to me this permutations problem from my desicrete math textbook? Q: The board of directors of a pharmaceutical corporation has 10 members. Three members of the board of directors ...
6
votes
3answers
499 views

General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
1
vote
1answer
31 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
1
vote
1answer
14 views

How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers in the correct order

Question:How many 4-permutations of the positive integers not exceeding $100$ contain three consecutive integers in the correct order a.) where consecutive means in the usual order of the integers ...
2
votes
1answer
27 views

Discrete Cauchy integral formula : The interior values are always convex combinations of exterior values for harmonic functions?

Let $T={\mathbb Z}^2$. For $t=(x,y)\in T$, the neighborhood $N(t)$ of $t$ is the four-point set $\lbrace x\pm 1;y\pm 1\rbrace$. A map $f:T \to {\mathbb R}$ is harmonic iff $4f(t)=\sum_{s\in ...
1
vote
0answers
34 views

Color Cyclic Permutations

Suppose there are n people sitting in a circle,wearing 3 kind of shirts viz. white,red and green. When two people with different shirt color talk with each other, they both change their shirt to ...
0
votes
0answers
52 views

Prove the inequality $\sum_{i,j = 1}^n {{A_{i,j}}({x_i}^2 - {x_i}{x_j})} \ge 0 $

A is a square matrix with positive elements and x is a real vector (both of them n>1 dimensional). Prove that for any such matrix and vector $$\sum\limits_{i,j = 1}^n {{A_{i,j}}({x_i}^2 - {x_i}{x_j})} ...
1
vote
0answers
39 views

diagonal of pseudoinverse of laplacian matrix

I have to find the diagonal of the pseudoinverse of a laplacian matrix evaluated on a directed and weighted graph. My laplacian is defined as: L = D - A where: D is a diagonal matrix; Di,i the sum ...
1
vote
2answers
40 views

Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies$\dots$

Question:Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies, and there are either 3 mutual enemies or 4 mutual ...
1
vote
1answer
27 views

The amount of closed binary operations on A under these conditions are what?

I have this problem and I would love some feedback on some of the answers that I have gave if they are incorrect. For some that I couldn't explain can someone explain to me how answers were achieved?. ...
0
votes
1answer
39 views

Show that if M, N are non-zero commutative rings, then M×N always has zero divisors, and is not an integral domain or a field.

Show that if M, N are non-zero commutative rings, then M×N always has zero divisors, and is not an integral domain or a field. How do I do this?!
0
votes
2answers
78 views

Let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the homomorphism defined by $f (n) = (n + xZ, n + yZ)$…

For $x,y \geq 2$, let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the ring homomorphism defined by $f (n) = (n + xZ, n + yZ)$. (i) The kernel $K$ of $f$ is the ideal ...
1
vote
1answer
27 views

How many closed binary operations on A have x as the identity?

There is this one example in my book that explains how to do this, but it's very obsecure and I just can't follow it. It says if: A = {x,a,b,c,d} then there are 5^16 closed binary operations on A ...
0
votes
1answer
30 views

How many number of commutative closed binary operations are there for this problem?

If $A = \{a,b,c,d\}$ , then $|A\times A| = 16$ and there are $12$ ordered pairs in the form of $(x,y)$ where $x\neq y$. From this how does the textbook get the answer $$4^4 \cdot 4^6 = \text{number ...
1
vote
4answers
50 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
1
vote
1answer
19 views

How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_1, b_1)$ and $(a_2, b_2)$ such that $\dots$

Question:How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_1, b_1)$ and $(a_2, b_2)$ such that $a_1 \bmod 5 = a_2 \bmod 5$ and $b_1 \bmod 5 = b_2 ...
0
votes
1answer
23 views

Each user on a computer system has a password, which is six to eight characters long,$\dots$

Question: Each user on a computer system has a password, which is six to eight characters long, where each character is an upper-case letter or a digit. Each password must contain at least one digit. ...
0
votes
1answer
22 views

$m=17 \cdot 23 = 391$. With an exponent $e=3$ and encrypted word is $c=21$. Decrpyting exponent $d=235$. Find $w$.

Say $m=17 \cdot 23 = 391$. With an exponent $e=3$ and encrypted word is $c=21$. Decrpyting exponent $d=235$. Find $w$, when $w \equiv c^{d} \pmod{m}$. So far I have split it up like this: ...
1
vote
3answers
59 views

How many ways to arrange $6$ children in $4$ bedrooms if at most $2$ kids per room

If I have $6$ children and $4$ bedrooms, how many ways can I arrange the children if I want a maximum of $2$ kids per room? The problem is that there are two empty slots, and these empty slots are ...
0
votes
2answers
20 views

Rounding a real number w.r.t. a given amount of steps

Let $x$ be a real number, $x \in [0,1]$. Suppose a system can only provide a noisy signal about the value of $x$, given the granularity allowed by the system, $N \in \mathbb{N}^*$. I'm looking for an ...
0
votes
1answer
21 views

Is there a way to modify the exponential smoothing function to account for varying sample rates?

I am using a simple exponential smoothing formula to smooth a signal. X(n) = a * S(n) + ( 1 - a ) * X(n-1) However on certain setups, the sample rate is much ...
0
votes
2answers
24 views

Induction and trig identity question.

I am in need of help for this question that I am stuck on, my work so far is this. $s(n) = ( \cos (\theta) + i \sin (\theta))^n = \cos (n \theta) +i \sin (n \theta)$ s(1) = true $s(k)=( \cos ...
0
votes
1answer
48 views

What is purpose of correlation kernel? IIs it high pass filter or low pass filter?

I am research about correlation kernel and I have some questions that need your help. Let see the pp. 3302-3303 in the http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6517250&tag=1 The special ...
0
votes
1answer
13 views

Need help with the proof of “If a graph $G$ contains a $u − v$ walk of length $l$, then $G$ contains a $u − l$ path of length at most $l$”.

$Proof$. Among all $u − v$ walks in $G$, let $P = (u = u_0, u_1, \ldots, u_k = v)$ be a $u − v$ walk of smallest length $k$. Therefore, $k \le l$. We claim that $P$ is a $u − v$ path. Assume, to the ...
0
votes
1answer
41 views

Solving ODE with matrices

I have an equation in ODE $M{'}(x)= M(x)*A(x)$. Issue here is $A(x) = C_1+C_2* x $ where $C_1,C_2 $ has dimension $3 \times 3$. And x is a scalar variable Doubt What is M(x)? Can any one give ...
1
vote
0answers
21 views

Weak compositions with bounded partial sums

Is there an easy way to count the number of weak m-compositions of n whose partial sums are lower bounded by some function? Example: Let K be a weak 3-composition of 4 K = (k1, k2, k3) Let s(t) be ...
0
votes
2answers
56 views

How many positive integer solutions are there to the inequality $x_1+x_2+…+x_r\le n$?

The original problem is there are $r$ identical boxes and $n$ identical balls. Every box is nonempty. Then how many ways of putting balls in boxes? It is equivalent to the problem of finding ...
0
votes
5answers
37 views

Recursive definitions of sequence $a_n = n(n+1)$ and $a_n = n^2$

Question: Recursive definitions of sequence $a_n = n(n+1)$ and $a_n = n^2$. My Attempt: For the first one,$a_n = n(n+1)$, I first manually generate a sequence using $n \geq 1$, $$2, 6, 12, 20, 30, ...
0
votes
0answers
20 views

Probability of x pocket pairs at a table of n people (NLHE)?

With n people at a table, what is the probability that x of them are dealt pocket pairs? There are several easy ways to approximate this but I was wondering there was an elegant solution. Any takers?
0
votes
6answers
55 views

How does one find the equivalent of this expansion of a summation formula?

For the summation with the form 1 + 4 + 9 + 16.. n^2 (don't know how to write it in sigma form on keyboard, sorry) does anyone know how we derive its equivalence which is n(n+1)(2n+1)/6? My textbook ...
0
votes
0answers
26 views

Problem calculating the average power of a vector?

I am calculating the average power of a vector. I would like to compare the final expression with the simulation. However, they are not equal. Please help me to point out which steps are wrong. Thank ...