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

0
votes
2answers
55 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
585 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 ...
1
vote
3answers
276 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
213 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
430 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
46 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
72 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
31 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
106 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 ...
6
votes
3answers
1k 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
366 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)$ ...
2
votes
1answer
26 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
109 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
36 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 ...
5
votes
4answers
784 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 ...
0
votes
1answer
42 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
498 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
69 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
41 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
260 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})} ...
4
votes
0answers
141 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
3answers
1k 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
64 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
48 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
88 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
61 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
65 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
5answers
71 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
142 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
2answers
158 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
27 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
82 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 ...
1
vote
2answers
40 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
55 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
36 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
102 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
18 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
59 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
42 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
180 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
4answers
55 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
6answers
179 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 ...
5
votes
2answers
148 views

Alternate translation for: “Every real number except zero has a multiplicative inverse.”

A given text states, “Every real number except zero has a multiplicative inverse" (where mul- tiplicative inverse of a real number x is a real number y such that xy = 1). It offers the following ...
4
votes
0answers
126 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
2
votes
1answer
74 views

Prove a statement with elements for Set Theory

I am stuck on this proofing question and I would like some clarification. Q: $A\subseteq B \iff A\cap B^{\prime} = \emptyset$ I already proved that LHS goes to RHS, but I am confused for the other ...
4
votes
1answer
424 views

The well-ordering principle can be used to show that there is a unique gcd of two positive integers…

Question The well-ordering principle can be used to show that there is a unique gcd of two positive integers. Let $a$ and $b$ be positive integers, and let $S$ be the set of positive integers of the ...
2
votes
1answer
48 views

Particular solution of the recurrence equation $u_{n+2} + u_n = \sqrt{2}\cos[(n-1)\pi/4]$

I would like to solve the equation xx recurrence using the operator $E$, ie, $$ (E^2 + 1)u_n = \sqrt{2}\cos[(n-1)\pi/4] \quad \Rightarrow \quad u_n = \dfrac{1}{E^2 + 1}\{\sqrt{2}\cos[(n-1)\pi/4]\} $$ ...
10
votes
1answer
123 views

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
0
votes
1answer
75 views

The Pigeonhole principle and sum of integers in subset of Z

S⊂{1,2,3,...} and the cardinality of S is 7. m is the maximum element in S.Find the possible values of m so that there exists distinct subsets B,C with s(B)=s(C) [s(B) means the sum of the objects in ...
1
vote
3answers
34 views

The range of function in Discrete Math

If A = {1,2,3} and B = {w,x,y,z},then the domain of f is A and codomain is B. However what about the range? Why is the range f=f(A)={w,x}, why cant it be {w,z}? Edit: f ={(1,w),(2,x),(3,x)}