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
1answer
5 views

Expand the binomial (2x-1)^8

I have looked through my notes and am stumped at this question. This is for introduction to discrete mathematics. Other than that there isn't really any stipulations.
1
vote
2answers
14 views

permutation;discrete structures review

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Consider a group of n people, let ...
0
votes
2answers
28 views

Why does $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$

I was looking at a solution to the problem and it says that $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$. I am wondering why this is true? Any help would be highly ...
0
votes
1answer
19 views

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
0
votes
1answer
18 views

Approximating a binomial coefficient using Stirling's formula

I am working on a problem of modelling a rubber molecule as a one-dimensional chain consisting of $N=N_{+}+N_{-}$ links, where $N_{+}$ points in the positive $x$-direction a distance $a$ and $N_{-}$ ...
0
votes
1answer
31 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-2}-36a_{n-3}+2^n $$ Hint: Find both the homogeneous and particular solutions. You can leave the homogeneous solution with ...
0
votes
0answers
17 views

How to compare two strings and give the result in percentage according to how many letters are matched? [on hold]

Suppose I have two strings: "centre" and "formatted" How to compare two strings and give the result in percentage according to how many letters are matched? here e and t is matched..(Note if ...
0
votes
0answers
11 views

Problem in understanding the proof of master theorem case

I am going through the proof of master method or master theroem. This is the formula that is been given by the author for the Total Work =Cn^d*(∑(a/b^d)^j) where value of J=0 to logbn as per the ...
0
votes
1answer
26 views

Circular permutations problem with putting objects into circle

How many options do I have if I want to put red boxes and black boxes into circle so that no two black boxes are next to each other? I have 12 red boxes and 4 black boxes. Also all two red and black ...
0
votes
3answers
23 views

Determining the list elements of $U = \{(A,B)\in \mathcal P(X) ×\mathcal P(X)\mid A=(X−B)\}$

Define $X = \{1,2,3,\ldots,n\}$, for some positive integer $n$. The set $U$, is defined as: $U =\{(A,B)\in \mathcal P(X) ×\mathcal P (X)\mid A=(X−B)\}$. If $n=3$, show the elements of $U$. I ...
2
votes
1answer
21 views

Counting Review; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
0answers
9 views

Solving DFT of this array

I am told to solve the DFT of the following array (5,5,5,5) However, according to the answer sheet, it is suppose to be (5,0,0,0). I tried working it out by hand, and F(0) was correct. But my ...
0
votes
1answer
18 views

Counting Problem; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
32 views

Counting Question; Discrete Structure

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
22 views

Please explain counting; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
19 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
2
votes
2answers
79 views

If $a+1/a$ is an integer, then so is $a^t+1/a^t$ for $t\in\mathbb N$

I need to show if $a$ is in $\mathbb{R}$ but not equal to $0$, and $a+\dfrac{1}{a}$ is integer, $a^t+\dfrac{1}{a^t}$ is also an integer for all $t\in\mathbb N$. Can you provide me some hints please?
5
votes
2answers
374 views

Vertical bar sign in Discrete mathematics

I am little bit confused about the sign " | ". Some people call it the division sign and some call it "such that". In computer programming, it's known as pipe. ...
0
votes
3answers
26 views

Does a system om congruence equations have solutions?

I have a system of congruence equations $$ \begin{cases} x \equiv 17 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ I need to investigate the system and see if they've got any solutions. I know ...
0
votes
4answers
41 views

proof for a problem in propositional logic

I cant find a proof for given problem: $$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$ Please give proof to prove above statement.
0
votes
0answers
9 views

Define the Fuzzy set

Can any one explain what is the difference between ordinary set and fuzzy set. Give me some examples of fuzzy sets
1
vote
0answers
19 views

NIMO 16.8 Expected Value + Probability

Let $p=2^{16}+1$ be a prime. A sequence of $2^{16}$ positive integers $\{a_n\}$ is monotonically bounded if $1\leq a_i\leq i$ for all $1\leq i\leq 2^{16}$. We say that a term $a_k$ in the sequence ...
-2
votes
2answers
60 views

Combinatorics homework problem [on hold]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
1
vote
1answer
22 views

Question about some properties of combinatorial structures

Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let $i$ be an edge of $K_{n,n}$. Let $$ B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge ...
0
votes
2answers
33 views

How do I solve simultaneous congruence modulo equations

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$
1
vote
1answer
25 views

big-Oh prove or disprove 2^n is in big-Oh(3^n)

the definiton of Big-Oh says $\exists c\in$R+,$\exists B\in$ N,$\forall n\in$N, $n \geq B$$\implies$$2^n \leq c\times 3^n$. I believe $2^n \in O(3^n)$, but how to prove it? can anyone help. This this ...
0
votes
0answers
20 views

Multinomial theorem: find the coefficient of $x^3 y^4$ in $(x+2y+3)^{10}$

I have trouble solving this problem: Find the coefficient of $x^3y^4$ in $(x+2y+3)^{10}$ The reason for that I struggle with this problem, is because it has an higher order (10) the $x^3y^4$. ...
2
votes
1answer
25 views

Use induction to prove summation

Use induction on $n\in\Bbb N$ to prove that $$\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}\;.$$ I have got as far as to the induction step where I have: $$S(n+1)= 2-\frac{n+3}{2^{n+1}}$$ and this ...
3
votes
0answers
30 views

Solution of inhomogenous ODE (4th order)

Hello stackexchangers, I have an inhomogenous ODE in 4th order. This ODE is the constitutive law to describe a material by using the "Wiechert model" (p. 15) which is given by $p_0\sigma + ...
-2
votes
2answers
15 views

Proving a Relation that is a Function by Division Algorithm [duplicate]

Let A=B=$\mathbb{N}$ R is: (a,b)$\in$R iff for some q$\in$Integers a=5q+b WHERE 0$\leq$b<5 Given a relation, show that it's a function. To Show: 1) $\forall$a$\in$A$\exists$b$\in$B((a,b)$\in$R) ...
0
votes
1answer
36 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [on hold]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
1answer
27 views

Some proof about greatest common divisor

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = pcommon ...
0
votes
3answers
39 views

Modulo: Calculating without calculator??

Calculate the modulo operations given below (without the usage of a calculator): $101 \times 98 \mod 17 =$ $7^5 \mod 15 =$ $12^8 \mod 7 =$ $3524 \mod 63 =$ $−3524 \mod 63 =$ Ok with calculator ...
1
vote
1answer
31 views

Question about problem 53 in Problem Solving and Selected Topics in Number Theory

I solved problem 53 in Problem-solving and selected topics in Number Theory. The problem was: Find the sum of all positive integers that are less than 10,000 and whose square divided by 17 leaves ...
-1
votes
0answers
69 views

discrete math cryptography [on hold]

An affine cipher is encryption using a simple mathematical function. Consider the affine cipher $c = ax+b \pmod{26}$ where $x$ is the plaintext, the function applied to each letter of the plaintext ...
0
votes
1answer
54 views

Prove that every integer from 1 to p – 1 occurs exactly once among these residues.

Let $p$ be a prime and $1 \leq a \leq p-1$. Consider the numbers $a, 2a, 3a, \cdots, (p-1)a$. Divide each of them by $p$, to get residues $r_1,r_2, \cdots,r_{p-1}$. Prove that every integer from $1$ ...
1
vote
2answers
33 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
0
votes
1answer
36 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem: Each of the K knights from the round table needs to choose a card which is marked with a number from 1 to N, N >= K. The cards all have different number. ...
0
votes
1answer
61 views

Prove that if p is a prime, a and b are integers

(a) if p | ab, then either p | a or p | b or both. (b) if a | b, p | b, but a is not divisable by p , then p | b/a. I have no problem with the part a I solved that but need some serious help on ...
0
votes
0answers
26 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
0
votes
1answer
48 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
1
vote
2answers
16 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
1
vote
6answers
104 views

The function $G: x \mapsto 2^{x^2}$ maps $\mathbb{R}$ onto $\{ x \in \mathbb{R} : x \geq 1 \}$

Let $X = \mathbb{R}$ and $Y = \{x \in \mathbb{R} :x ≥ 1\}$, and define $G : X → Y$ by $$G(x) = e^{x^2}.$$ Prove that $G$ is onto. Is this going along the right path and if so how do get the ...
0
votes
0answers
19 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
1answer
38 views

Find all real numbers $x$ such that: $\lfloor 7x\rfloor = 7$

I'm not quite sure how to approach this. Does $x$ have to be very small for it to work?
0
votes
1answer
30 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
3answers
21 views

Let $ a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. use the result of par t $ a)$ to solve the Diophantine equation $ a+b=ab$

Not sure if I did part a right, not sure how to complete part $b)$ $a)$ Let $a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. Proof by contradiction suppose $\text{gcd}(n, n-1) = p > ...
-2
votes
1answer
22 views

Probability: How much days we need to play a game win

Suppose the probability of win a lotery game is : $1/1000$ If a person play the lotery every day with the same combination, how much time he need to wait to win the lotery? Im thinking to use a ...
0
votes
5answers
37 views

Give the number of solutions of $x+y+z = 30$, for $4 \leq x \leq 14$, $3 \leq y \leq 17$, $10 \leq z \leq 25$.

How would I find the number of solutions with both upper and lower bounds? Can anyone give a step by step way to solve this problem? This is question is in preparation for my discrete math final, so ...
7
votes
6answers
86 views

Solve $\lfloor \sqrt x \rfloor = \lfloor x/2 \rfloor$ for real $x$

I'm trying to solve $$\lfloor \sqrt x \rfloor = \left\lfloor \frac{x}{2} \right\rfloor$$ for real $x$. Obviously this can't be true for any negative reals, since the root isn't defined for such. My ...