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

3
votes
2answers
35 views

Probability Independence - Determining if two sets are independent (drawing two cards)

I've got a few problems here that I feel pretty confident on. I am asking for confirmation on these answers. However, I am stuck on problem #3. Please let me know if you need more information. Two ...
1
vote
1answer
28 views

Rolling a pair of dice, conditional probability of neither die showing a 2 given they sum to 7.

This question is identical to this one, but I am not finding the explanation I am looking for in that question. My sample space would be $S = \{1,2,3,4,5,6\}^2$ and $P(s) = \frac{1}{36}$ for all $s ...
1
vote
1answer
17 views

Given that you have exactly one pair, what is the probability you have two aces?

You are drawing 5 cards from a 52 card deck in a game of Poker. Here's what I've got so far, but I'm a bit stuck on how to proceed. Let $S = \{h \in 2^D : |h| = 5\}$ and $P(h) = \frac{1}{52 \choose ...
2
votes
1answer
34 views

Is there a simpler way to do this modulo operation?

Question is: $38^7 \pmod{3} \equiv $ ? I do this: $38^7 \pmod 3 \equiv [(38 \pmod{3})^7]\pmod{3} \equiv [2^7] \pmod{3} \equiv 128 \pmod{3} \equiv 2$ Is there a way to do this without ...
2
votes
1answer
17 views

Can you verify my solutions to these probabilities, given a coin is flipped 10 times?

I'm fresh into probability and I think it's important to ask a lot of questions since it seems probability really challenges your intuition. I'm working on the following problem, and have found a ...
1
vote
1answer
25 views

Prove using generating functions the equality of amount of solutions for provided equation with two given groups of limitations

At first, I hope the title for the post is fine, because I wasn't able to sum up the question to a better title. Anyways, this is the problem: I've got to prove that $a_n=b_n$ for every $n$ while: ...
1
vote
1answer
45 views

What math do I need to know for MD5?

This could fit into a lot of areas of SO but I feel like mathematics will know best. What area of math is used for something like an MD5 or SHA algorithm? Is there a mathematical equation/skeleton ...
0
votes
1answer
18 views

Why some of the value in inverse matrix become positive?

Ans: But why? Isn't it calculate something like this: Please help explain. Thank you!
1
vote
1answer
25 views

How do I translate sentences from English to predicate logic?

This question was taken from the MIT OCW Math for Computer Science course. Translate the following sentences from English to predicate logic. The domain that you are working over is $X$, the set of ...
0
votes
0answers
32 views

How many partially ordered sets(poset) does a set have on 4 elements?

A partially ordered set has the following properties: a ≤ a (reflexivity); if a ≤ b and b ≤ a, then a = b (antisymmetry); if a ≤ b and b ≤ c, then a ≤ c (transitivity); I think that the easiest ...
1
vote
1answer
56 views

Show that the sum $\sum_{k = 0}^n 2^k \binom{n}{k}$ is equal to $3^n$

How can I show that the sum $$ \sum_{k = 0}^n 2^k \binom{n}{k}$$ is equal to $3^n$?
-2
votes
1answer
83 views

How to solve given recurrence relation?

From the following recurrence relation: $a_n =- a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14$, for $n\geq3$ Where $a_0=6, a_1 = 0 $ and $a_2=57$. My attempt: I have generated a ...
0
votes
1answer
30 views

Deterministic finite automaton parity bit question

for a university assignment ive been tasked with creating a DFA that accepts the regular language (00010 + 1101 + 1010)* and must contain a parity bit at the end to make sure there is an even amount ...
0
votes
0answers
16 views

Discrete Structures - Sets, graphing, and set builder notation help

Have attempted to assess and produce answer, though teacher is very very particular, and doesn't give partial credit. I'm really not confident I can solve this. If anyone is great enough to illuminate ...
1
vote
1answer
25 views

Need help understanding algebra steps taken in proof of why an even minus an odd is odd

I don't understand the algebra used in the below example proof from my textbook. Where does the + 1 come from? Is it okay to just add 1 anywhere you want? Or is there some rule here or reason you ...
0
votes
1answer
56 views

Direct proof that if mn is odd then m is odd and n is odd

I found the converse here, although that's not what I want. I have thought of a proof by contradiction and by contraposition, although I can't seem to figure out a way to finish a direct proof. $mn ...
0
votes
1answer
18 views

Proof that $t^m=t^{j}$ if $t$ is an $r^{th}$ root of unity such that $r \mid k$.

I need help with the following proof. Let $j$ = $0,1,\ldots, k-1$. Also, let $t$ be an $r$th root of unity other than $t=1$ such that $r \mid k$. We know $m=j\pmod k$. Furthermore, $m$, $j$ and $k$ ...
2
votes
3answers
46 views

Prove by mathematical induction: $n! < n^n$ for $n\geq2$ [closed]

I'm having issues figuring this out. I have the base case but I'm a bit stuck on the inductive case. Prove: $n! < n^n$ for $n\geq2$ Thanks in advance.
0
votes
1answer
23 views

Finding a Regular Grammar

so I have to find a regular grammar to generate the following sets: $(1)$ $\{aa, ab, ac\}$ $(2)$ $\{ab^n,ba^n\mid n\ge 0\}$ $(3)$ $\{ab^{2n}\mid n\ge0\}$ I'm wondering if anyone can check my ...
0
votes
2answers
25 views

Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...
0
votes
2answers
67 views

Discrete one-dimensional 2-cycle system

Is it possible to classify all maps $x_{k+1} = f(x_k)$ that have the property that all orbits are period 2 cycles only? Also, how would I do it for period 3 system?
0
votes
2answers
32 views

Equivalence relation and equivalence classes given function and relation

Given a function $f : A → B$, let $R$ be the relation defined on $A$ by $aRa′$ whenever $f(a) = f(a′)$. Prove that $R$ is an equivalence relation and determine the equivalence classes. To prove that ...
0
votes
1answer
17 views

Time complexity for loops

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. int j = 1; int n = any; ...
0
votes
1answer
37 views

How to prove something is an equivalence class?

I don't understand equivalence class and representative function: http://www.cdhmhome.com/uic/math215/S.pdf , I'm looking at examples 37, 1-7 and have already determined which ones are equivalence ...
3
votes
1answer
59 views

How to prove a regular pentagon is formed by knotting a rectangular strip of paper?

I found this interesting problem from a friend (From Arthur Engel's-Problem Solving Strategies book). The method to begin the problem is as follows- Step 1.Take a rectangular strip of paper ...
0
votes
0answers
32 views

Create the following wffs(axiom rules for domain) for the domain of lists over alphabet A

Recall that in the domain of Lists over Alphabets, the function cons(a,x) where a is an element in an alphabet and x is a list, produces a new list with a at the beginning of L. The predicate ...
0
votes
2answers
23 views

Difference between Depth first search and Breadth first search algorithm

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a ...
1
vote
1answer
40 views

Finding the general term

I'm having some trouble with trying to find the general term of this sequence. It has a non-linear recurrence. I would really appreciate it if anyone could help me! $ a_{n}= ...
17
votes
6answers
3k views

Is there a way to write an infinite set that contains only irrational numbers without integer multiples?

Is there a way to write an infinite set that contains only irrational numbers without integer multiples? The infinite set must not contain integer multiples of any other members of that set. For ...
0
votes
0answers
28 views

mathematical formula to compute sum of all sub sequences of a number N

We have a number say N and we list down all its sub- sequences and sum them up.SAY for n=123 ,the sum is 177(123+12+23+13+1+2+3). I came across this mathematical formula which computes the sum taking ...
1
vote
1answer
16 views

How do i use the fundamental theory of arithmetic to proof the nth root of a positive integer is irrational?

In this example i'll try to use the FTA to prove that the $\sqrt[3] {81}$ is irrational. So first i say that $$\sqrt[3] 3 \times \sqrt[3] {27} = \sqrt[3] {81}\implies \sqrt[3] 3 \times 3 = \sqrt[3] ...
0
votes
0answers
17 views

Solve using math induction with steps. [duplicate]

$$\sum_{i=1}^{n+1} i2^i = n2^{n+2} + 2, \forall n \geq 0$$ Getting stuck.
5
votes
2answers
54 views

Find the number of tuples consisting of $0, 1$ and $3$

How can I find the number of tuples $(k_1, k_2, ...,k_{26})$ such that each $k_i$ equals $0, 1$ or $3$ and $k_1 + k_2 + ... + k_{26} = 15$. I can reduce this problem to finding the coefficient of ...
1
vote
0answers
13 views

Symmetric and reflexive closure on positive integers

Finding the symmetric and reflexive closure of the relation $R = \{(a, b) | a > b\}$ on the set of positive integers. For symmetric closure I have: $R = \{(a, b) | a > b\} U \{(b, a) | a > ...
-2
votes
0answers
44 views

I have the word ONOMATTOPPOEIA , how many strings can be formed and how? [closed]

I am looking for how many strings can be formed using ONOMATTOPPOEIA
-1
votes
0answers
16 views

Determine how many strings can be formed by ordering the letters ABCDEFGHIJKL so the string “ABC” or the substring “CDF” or both? [closed]

I need help answering this question its quite hard for me on what it is asking and what would be the answer
-1
votes
1answer
26 views

In how many ways can we select a chairperson, vice - chairperson and president from the group of 25 people? [closed]

Well a group of 25 people with 3 man team basically so would i just do $25^3$ then $3!= 6*25 = 150$ as the answer, basically.
-1
votes
1answer
29 views

Given letters ABCDEFGH : how many strings of length 5 can be formed using the letters ABCDEFGH if repetitions are not allowed [closed]

well i was thinking like this 9*8*7*6 for each string there is 5 slots and since theres no repetition the number gets lower, can anyone be of help?
-2
votes
1answer
40 views

Find all possible solutions between 0 and 2π [closed]

I really could use help here, i am trying to find all possible solutions between 0 and 2 pi.
0
votes
1answer
23 views

Every connected graph contains at least 2 vertices of the same degree

Theorem:Every connected graph contains at least 2 vertices of the same degree. (In the Finite and Simple Graph Context) What can I do to prove ? Can you give me any suggestion ?
0
votes
1answer
30 views

Number of errors detected from a generator matrix

Consider the encoding function $\alpha : \mathbb{Z_2^2} \rightarrow \mathbb{Z_2^5} $ given by the Generator matrix $$ G = \begin{bmatrix}1&0 &1& 0& 0 \\0& 1 & 0 & 1 & ...
2
votes
0answers
38 views

Positive integers $<100000$, how many contain exactly one $3$, one $4$ and one $5$

So I use $5$ positions for range $00000$ to $99999$ Choose $3$, choose $4$ and choose $5$ as follows: $5C1 \cdot 4C1 \cdot 3C1$ Remaining $2$ digits have $7$ possible digits as input Ans: $5C1 ...
0
votes
0answers
18 views

What is Z-tranform of signum function?

If Z-transform of x(k) is X(z), then what will be the Z-transform of sign(x(k))? Furthermore, what will be the Z transform of sign(x(k-1))?
-1
votes
1answer
29 views

Prove using formal methods

Prove using formal methods ∀x ¬(P(x) ∧ Q(X)) --> ∀x(¬P(x) v ¬Q(x)) So I tried this problem ∀x ¬(P(x) ∧ Q(X)) P ∀x ¬P(x) v ¬Q(X) Distributing the not. Can I do something like ...
1
vote
1answer
23 views

Proof by induction of a specific series

First of all please excuse the weird formatting, this is the first time I'm asking a question here! Problem: $2*6*10*14\dots (4n-2) = \frac{(2n)!}{n!}$ My solution: I proved base case with both ...
-1
votes
0answers
11 views

Is f(n1 x n2) = Θg( n1 x n2 ) true?(Discrete mathematics, Algorithm)

I have a question about Theta Notation. For X={1,2,3 .....} n1 and n2 are elements of X If f(n1) = Θg(n1) and f(n2) =Θg(n2), then is f(n1 x n2) = Θg(n1 x n2 ) true? My speculation is that for n1 x n2 ...
2
votes
3answers
57 views

In how many ways can four integers be selected from $1, 2, 3, \ldots, 35$ so that the difference of any pair of the four numbers is at least $3$? [on hold]

I want to choose $4$ integers from the numbers $1$ to $35$. Condition: The difference of any pair of the $4$ numbers should be $\geq 3$. How do I model this problem?
0
votes
0answers
33 views

In how many different ways can a schedule be created for all rounds in a ping pong table tournament?

In a ping pong table tournament participate 8 competitors and the following rules apply: Each competitor plays with every other competitor exactly one match If in the $i$-th round there ...
0
votes
0answers
19 views

Discretization of nonlinear system for using extend Kalman filter in python

i have a continuierlich nonlinear System includes three Differential equations: $\dot{x}=f(x, u)+\omega_k$ Now i wanna use numerical methode to make discretization of it. Then I can use it in a ...
0
votes
0answers
36 views

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$.

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$. The progress I have made so far: H A L T $07, 00,11,19$ Since, $m =1$, we break this up into $2*m$ ...