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

1
vote
1answer
31 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
36 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
19 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
43 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
57 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
26 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
19 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
26 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
73 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
33 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
18 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
62 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
33 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
25 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 > ...
0
votes
1answer
24 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
30 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$? [closed]

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
21 views

Discretization of nonlinear system for using extend Kalman filter in python

I have a continuous nonlinear system which includes three differential equations: $\dot{x}=f(x, u)+\omega_k$ Now I wanna use numerical method 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$ ...
0
votes
0answers
16 views

Graph Matchings Problem

There was A LOT of given information about 8 students doing research papers on 12 books in a library (I simplified it to letters and numbers). The problem wants to know if all students can work ...
-1
votes
1answer
47 views

Assuming that it was enciphered with a generalized Caesar cipher with multiplier…

Assuming that it was enciphered with a generalized Caesar cipher with multiplier $r$ and shift constant $s$, find $r$ and $s$ and decipher the message: ZWSTO BPJOG BYQIP JOUWO OZGVS MPJOS MPQAI So ...
0
votes
1answer
25 views

Non-isomorphic Unicyclic Graphs

How many different (non-isomorphic) connected graphs having N vertices, and exactly one cycle comprising K vertices exist?
2
votes
2answers
47 views

Combination and Probability

There are n students and n+2 different gifts. Each student have to receive 1 gift package. How many ways can we give out all the gifts. ...
-1
votes
0answers
8 views

Numerical Solution of Matrix with Diagonal Elements of Highly Varying Order

I am trying to solve following set of equations: A(i,i-2)*u(i-2) + A(i,i-1)*u(i-1) + (A(i,i)+β(i) )*u(i) + A(i,i+1)*u(i+1) + A(i,i+2)*u(i+2)= B(i) + β(i) where i=1:1000000 If values of β ...
0
votes
2answers
46 views

Induction on well formed formula

I need to prove in induction that - In a (WFF) well-formed formula between every two atoms there is a connective. Should my base case be about one atom or two ? In my proof(Induction step) should I ...