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
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 ...
0
votes
1answer
29 views

True/False question in Propositional logic

I need to Prove of disprove this statement If $S$ $\cup$ $\{a\}\models{b} $ and $ S$ $\cup$ $\{\neg a\}$$\models{b}$ then $S$ $\models b$ Looks to me like a True statement , but found it hard ...
0
votes
0answers
11 views

Discrete Mathematics Program Correctness Initial Assertion

As an example in my discreet mathematics textbook I have the following: Verify that the program segment if x < 0 then abs := −x else abs := x is ...
0
votes
1answer
43 views

Finding a recurrence that satisfies a sequence

Consider the sequence: $1,1,1,3,5,9,17,31,\ldots$ Find both a recurrence and a different sequence that satisfies this recurrence. Saw a decent pattern until the 31 appeared...Pretty ...
0
votes
1answer
17 views

Binary Decision Trees

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is: "Create a binary decision tree that reflects ...
0
votes
1answer
7 views

Conjunctive Normal Form (CNF) of a propositional formula

These are my notes for Discrete Math. I'm having trouble understanding how to convert the given formulae at the end into CNF. The example seems to have skipped the steps and jumped straight to the ...
0
votes
0answers
6 views

About conclusion part of an implication

Suppose $G$ is a cyclic group containing more than $12$ elements of order $13$. Suppose $a \in G$ with $\operatorname{ord(a) = 13}$. Hence, $(a)$ is finite subgroup of $G$. $(a)$ is a subgroup of ...
0
votes
2answers
41 views

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?, assuming that the coins all have different dates and so are distinguishable from each other, and the ...
-2
votes
0answers
16 views

Number of antisymmetric relations on a three element set, A = {1,2,3}? [duplicate]

Number of antisymmetric relations on a three element set, A = {1,2,3}? Do we find this by doing $2^{n} 3^{\binom{n}{2}}$? I seriously don't get this.
0
votes
1answer
18 views

For a set $A = \{1,3,6,14,18\}$, $x$ relates to $y$, if $y$ is divisible by $x$. Is this set reflexive, symm. antisymm. or transitive?

For a set $A = \{1,3,6,14,18\}$, $x$ relates to $y$, if $y$ is divisible by $x$. Is this set reflexive, symm. antisymm. or transitive? Heres what I have so far for relation $R (1,3), (3,6), (1,6) ...
1
vote
1answer
22 views

How many antisymmetrical relations are there on a set $B =\{ 1,2,3\}$? [duplicate]

How many antisymmetrical relations are there on Set $B$ if Set $B = \{1,2,3\}$? I believe its three?
0
votes
2answers
19 views

Is this reflexive, symmetric, antisymmetric or transitive?

Set A contains all points $(x, y)$ on a coordinate plane. The relation $R$ is defined as: point $(x_1,y_1)$ is related to point $(x_2,y_2)$, if $y_1=y_2$. Is this set (A) reflexive, symmetric, ...
1
vote
4answers
106 views

Does it hold/can you prove that if $\frac{1}{x} + x$ is an integer, then $x = 1$? [closed]

I am trying to show that if $\frac{1}{x} + x$ is an integer, then $x = 1$, where $x$ is a positive integer. Not sure where to begin
0
votes
0answers
8 views

We have a relation R on $Z^ +$ , defined as follows. mRn if and only if m|nDetermine the set B = { m ∈ $Z^ +$ | 52 Rm }

We have a relation R on $Z^+$ , defined as follows. mRn if and only if m|n Determine the set B = {m ∈ Z + | 52 Rm}. I am not so sure how to go about it. However I can give a cardinality
1
vote
1answer
14 views

Find the value of the Infinite product in terms of k which is a positive integer

$$\prod_{n=k+1}^{+\infty}\left(1-\frac{k^2}{n^2}\right)$$ The only help we have been able to find is that of Euler, anything would be amazing!
-1
votes
2answers
50 views

a/b + b/a is an integer if and only if a = b

So for an iff, I know you must prove it both ways. I have proven the converse by the idea that $\frac{a}{b} + \frac{b}{a} = \frac{a}{a} + \frac{a}{a} = 2 $ which is an integer. But I am struggling ...
0
votes
0answers
8 views

Optimization Problem, including block bids.

Block order optimization Hello, We're a bit stuck on this problem, which involves bidding in blocks. We're given $Q, K, s(1),s(2),...s(24)$ $$ \underset{q}{\text{maximize}} ...
0
votes
3answers
51 views

explicit formula for $a_n$ and $b_n$ [duplicate]

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$
0
votes
0answers
10 views

BFS and bipartites graphs

I have the lemma Lemma. Let G be a connected graph, and let $L_0$, …, $L_k$ be the layers produced by BFS starting at node s. Exactly one of the following holds: (i) No edge of G joins two ...
1
vote
3answers
52 views

Show Latin Square is not a group.

If we fix the first two rows in the above figure, then there are many ways to fill in the remaining rows to obtain a Latin square. Show that none of these Latin squares is the multiplication ...
5
votes
2answers
144 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority ...
1
vote
3answers
36 views

General Big-O operations.

Suppose $T_1$(n) = O(f(n)) and $T_2$(n) = O(f(n)). Determine if the following is true or false. If false, provide a $T_1$,$T_2$ for which it is false. $T_1$(n) - $T_2$(n) = O(f(n)). My solution: ...
0
votes
0answers
28 views

Finding unknown in modular arithmetic.

I know how to work something like $19x \equiv 4 \pmod{141}$ (using the method of checking if $141$ divides $19x - 4$ when $x = 0,1,2, \ldots$), but for some reason, I don't know how to solve an ...
0
votes
0answers
11 views

Determining if Poset based on Domain and Comparison Operator?

Can someone help me with how to think about the below problem? I know that a poset is a relation which is reflexive, antisymmetric, and transitive, but unless I'm dealing with finite sets I have a lot ...
1
vote
3answers
43 views

Concrete Mathematics - 2.4 - sum of 1/k-j

On the last part of finding the final solution for $$\sum_{j=1}^n\sum_{k=j+1}^n \frac{1}{k-j}$$ After replacing $k = k+j$, will result to: $$ S_n = \sum_{1 \leqslant j < k+j \leqslant n} ...
0
votes
1answer
28 views

Strong Induction Proof of amounts of money

I am so confused about this kind of question which is referring to amounts of money. I know we should use strong induction to prove if we meet some questions asking you which amounts of money can be ...
0
votes
1answer
26 views

How we can represent $a^b$ in following form

Consider $$a^b= a ^ {101101} $$ As if we split the binary representation of $b$, $$b = 1 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2+ 0 \cdot 2^1 + 1 \cdot 2^0 $$ Then how are we able to ...
0
votes
1answer
22 views

Let A, B, C be sets, with B ⊆ C. Prove that (A x B) ⊆ (A x C).

I understand why this is true but I need help answering it in a mathematical way, not just using common sense.
1
vote
0answers
46 views

Need help in deciding the type of function and their range and inverse for the functions $p,q,r$ and $s$.

Let $p,q,r$ and $s$ be the following functions $p: R\to R$ defined by $P(x) = (1/2)x + 1$. $R$ represents set of all real numbers. $q:Z \to \{0,1\}$ defined by $q(x) = \{ 1,$ if $x \geq 1; 0,$ if ...
0
votes
1answer
13 views

Determine if given relation is an equivalence relation, and describe the partition?

Can someone walk me through how to do these types of problems in my Discreet Mathematics II Textbook? (ex.): Determine whether the given relation is an equivalence relation on the set. Describe the ...
1
vote
1answer
3 views

Finding pairs with respect to lexicographic order that meet a condition from a set?

I am working some problems out of my textbook for Discrete Mathematics II and was wondering if someone could tell me how to think through and go about solving the following type of problems (there are ...
1
vote
2answers
17 views

Question about the exclusive or operator

Let $R_1$ be the “less than” relation on the set of real numbers and let $R_2$ be the “greater than” relation on the set of real numbers, that is, $R_1 = \{(x, y) | x < y\}$ and $R_2 = \{(x, y) | x ...
0
votes
0answers
28 views

Variant on the Subset Sum problem

I was working through the subset sum problem and came across what looks like a general rule, but I can't prove that it's always the case. I hope I explain this clearly... If I have a set of numbers ...
0
votes
1answer
26 views

Show that in a binary tree, if B is the number of branch points (including the root) and L is the number of leaves, then one has the relation L = 1+B

We have been discussing trees lately, but have yet to even touch on the topic of a binary tree. I understand what a leaf is, but we didn't have one for the term "branch points" Without being 100% sure ...
1
vote
1answer
61 views

An interesting puzzle from Jiří Matoušek's book

There is an interesting puzzle from Jiří Matoušek's book Invitation to Discrete Mathematics, problem 1.2.8, which confused me lots of time. Divide the following figure into $7$ parts, all of them ...
0
votes
0answers
13 views

How to Compute Discrete Intrinsic Curvature

Given a function $f$, a region $S$ where this function is twice differentiable, and the property that all of its discrete difference series centered in $S$ converge within $S$ We have that $$ ...
-1
votes
1answer
42 views

How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge? My attempt: Tree is a connected graph which has no cycle, and in a connected graph, bridge is a edge whose removal disconnects the graph. Let ...
1
vote
1answer
58 views

Decode the message $(1,1,1,0,1,1,1)$ using the Hamming $ (7,4)$ code

The question is asking me to decode $(1,1,1,0,1,1,1)$ using Hamming $(7,4)$ code. I know that I am suppose to set a $3 \times 7$ matrix ${\bf H}$ and multiply it by ${\bf r}$ and set it equal to zero, ...
1
vote
3answers
49 views
1
vote
1answer
25 views

Suppose $P (1) + P (2) = 3P (3)$ and $P (2) + P (3) = P (1)$ for a sample space $(S,P)$ . Find the probability function.

So we have the following equations: $P(1) + P(2) = 3P(3)$ $P(2) + P(3) = P(1)$ I know that by definition, $P(1) + P(2) + P(3) = 1$ I'm not entirely sure what I'm looking for as my answer though. ...
0
votes
1answer
17 views

Can you verify I set up these sample spaces correctly?

I'm doing a practice problem that asks to set up sample spaces. A bag contains 25 marbles. The experiment is to draw 4 marbles from the bag. What are the sample spaces with the following ...
0
votes
1answer
21 views

Calculating time using modulus

In my textbook, the question is as follows: What time does a 24 hour clock read: a) 100 hours after it reads 2:00 b) 45 hours before it reads 12:00 c) 168 hours after it reads 19:00 And provides ...
0
votes
0answers
46 views

Is f a 1-1 function from {0,1} to N?

Let $f(x) = 2x-1$ and $g(x) = (x+1)/2$. Is $f$ a 1-1 function from {0,1} to $N$? Is $f$ an onto function from {0,1} to $N$? Is $g$ a 1-1 function from {-1,1} to $N$? Is $g$ an onto function from ...