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

Translating “some student asked every faculty member a question” into a logical expression.

$ S(x) $ is the predicate "$x$ is a student" $F(x)$ is the predicate "$x$ is a faculty member" $A(x,y)$ is the predicate $x$ asked $y$ a question I need to translate this sentence into logic: Some ...
1
vote
1answer
31 views

to change a pair (a,b) into pair (c,d) with conditions

We have two positive integers a and b .We need to change it into (c,d).We have a puzzle associated with this. ...
-1
votes
1answer
18 views

changing from base 3 to base 9 using given information

(a) Given a sequence of non negative integers $\{a_r\}$ show that $\displaystyle\sum_{r=0}^na_r(x+1)^r(\!\bmod x)=\sum_{r=0}^na_r(\!\bmod x)$ where $x\in\{2,3,4,\ldots\}$. ...
1
vote
0answers
25 views

What are the first three values for the following recursive sequence?

$a_0 = 3$ $a_n = (a_{n-1})^2 + (a_{n-2})^2 +\cdots + (a_0)^2$ for all integers $n\geq 1$. Would that mean $a_1 = a_0^2 = 9$? Thanks!
1
vote
1answer
22 views

Which of the following is NOT true for $G$?

$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ...
1
vote
1answer
40 views

How does $\frac{1}{2}(n-s+1)(n-s)$ equal $\binom{n-s+1}{2}$?

Maybe a basic question, but I'm strolling through graph theory at the moment after a few years out of tertiary mathematics. There is a theorem that if a graph $G$ has $s$ connected components, then $$ ...
2
votes
2answers
46 views

How does ~ distribute over parentheses?

In my recent Discrete Math final exam, we had a question where I thought the answer was false but apparently it is true. It is the following: $$((\forall x)P(x)) \rightarrow ((\forall y) Q(y))) ...
2
votes
2answers
66 views

Discrete Math: Multiplying a set by ∅

How would you multiply any set by $\varnothing$? Lets say $A \times \varnothing$. Would that simply be equal to $\varnothing$? or Would I write out $(a, \varnothing ), (a_1, \varnothing), (a_2, ...
1
vote
1answer
30 views

Using the Euclidean algorithm to show that $\gcd(11k+7, 5k+3)=1$

Came across this question in the textbook and I've ran into some difficulties whilst attempting it: $11k+7 = 2(5k+3) + (k+1)$ For $\gcd(5k+3,k+1)$ I am not sure on how to factor $k+1$ into $5k+3$, ...
0
votes
2answers
68 views

Proof: Probability of a pair when rolling 7 dice is 1.

I know that the probability should be over or exactly 1 since out 6 possible values the 7th dice will always be a duplicate. My calculations are wrong though: $\frac{{7\choose2} 5! 6*1}{6^7}$ ...
4
votes
1answer
43 views

Prove that if $n$ and $m$ are positive integers such that $n^n|m^m$ then $n|m$.

This is how I did it, but not sure if it is a correct proof. Assume that $n^n | m^m$. And we write $m= p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ and $n=q_1^{b_1}q_2^{b_2}...q_l^{b_l}$. So, $$m^m = ...
1
vote
5answers
34 views

Give an example of a function from A to B that is not one-to-one. Explain why it is not one-to-one

A= {a,b,c,d} B= {1,2,3,4,5} Currently studying for a final. I know that a one-to-one function cannot map to 2 elements. There are more elements in B than in A. I don't know how to give a specific ...
0
votes
1answer
35 views

Showing that the polynomial $f = x^4+x^3+1 \in Z_2[x]$ is primitive?

I have shown it is irreducible. I've tried considering $\alpha = \bar{x} \in \mathbb{Z}_2[x]$ s.t. $\alpha^4+\alpha^3+1 = 0$. From my understanding you use the fact that $\alpha^{16-1} = 1$ and hence ...
-2
votes
1answer
16 views

Expected Utility Decision Theory Problem [closed]

Consider a person who choose among lotteries. Each lottery is of the form (p1, p2, p3) where p1 is the probabilty of getting Rs.5, p2 is the probabilty of getting Rs.1 and p3 is the probabilty of ...
1
vote
4answers
79 views

Prove that identity element is unique

During an exam I tried to prove that the identity element of group (G.•) is unique. I approached this way: Suppose there are two identity elements $e_1$ and $e_2$. Then: $a^{-1}•a=e_1$ ...
0
votes
1answer
29 views

recursive definition of a palindrome help

Recall that a bit string is a string using the alphabet {0, 1}. A palindrome is a string that is equal to the reversal of itself. Consider the following recursive definition of a palindrome: Basis ...
1
vote
0answers
19 views

Minimum Column/Row Matrix “Covering”

I'm not sure if Column/Row "Covering" is the correct terminology. I have a square matrix. I would like to know how to determine the minimum number of lines (rows and/or columns) needed to "cover" the ...
2
votes
1answer
25 views

unfolding of a recurrence

I've been reading the book "Concrete Mathematics" from Graham et. al. And there is a relation (on pg. 27) $s_n = s_{n-1}a_{n-1}/b_n$, and authors point that this relation can be unfolded, resulting ...
1
vote
0answers
19 views

Pollard Rho - DLP Algorithm Implementation

I am working with Pollard Rho Algorithm DLP. I have developed in Java and Python the way to calculate the table to find the collisions, and then using congruences and some others tricks I am getting ...
1
vote
0answers
14 views

Irreducible factorization - Discrete Mathematics revision

Q Determine the irreducible factorization of each of the following polynomials $f$ in the indeterminate $x$ over the field $\mathbb{Z}_p$ of integers module the prime $p$. $f = x^5 + x^4 + x^3 + ...
1
vote
0answers
52 views

How can I verify logical equivalence without using Truth Table?

I have an assignment and I need to prove the following logical equivalence using Laws of Logic and not using Truth Table: p → q ≡ ~q → ~p LAWS OF LOGIC: 1.Commutative Law: p ↔ q ≡ q ↔ p ...
0
votes
1answer
37 views

Pigeonhole Principle Painting a Plane

I need help with this question, because I do not understand some points. PidgeonHole Question: Paint every point of the plane with either blue or red color. Show that there are 2 points on the plane ...
1
vote
4answers
26 views

Help Proving this Propositional logic

Can someone help me with my proof? Let p, q, r and s be propositions. Consider the hypothesis $(p\space\lor\space q \to r)$, $\lnot s$, $r \to s$ and conclude $\lnot p$. My Proof $ r \to s\\ \lnot ...
0
votes
2answers
25 views

Probability in Discrete Mathematics

I need help with some probability questions. I answered the best I can but I'm not sure if any are correct. Consider the following character {1,3,5,7,9,a,b,c,d,e} (a) How many 6 character passwords? ...
0
votes
1answer
49 views

If n is a positive integer that is not square free

Determine if the statement is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be ...
2
votes
2answers
59 views

Give a graph model for a permutation problem

Describe a graph model for solving the following problem: Can the permutations of $\{1,2,\ldots,n\}$ be arranged in a sequence so that the adjacent permutations $$p:p_1,\ldots,p_n \text{ and } ...
0
votes
1answer
49 views

Proving that $n$ is a Carmichael number

Determine if the statement is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be ...
0
votes
1answer
16 views

Graph theory, finding the degree of a vertex?

Ok so that is the graph. I am trying to find the degrees of the vertex. My book said that the degree of vertice D is 4, but I am not seeing how that is possible. I know the degree is the number of ...
1
vote
0answers
15 views

How would you write the OGF for the sequence {hk}

Write the ordinary gen. function for the sequence. So trying to work this out. I ended up with (1+x)^7. But I am not sure if this is correct. Thanks for any help.
0
votes
0answers
25 views

Finding a shorter recursive equation

The assignment is the following: (a) Given a sequence $(a_n)_n$ which satisfies the recursive equation $a_n = \sum\limits_{k = 1}^d c_k \cdot a_{n-k}$ with $c_d \not= 0$. Furthermore $Q = 1 - c_1t - ...
0
votes
2answers
32 views

Proving equivalence classes for a equivalence relation

I am having a bit of trouble trouble understanding how to start problems such as this one. I feel like I am given information that I understand separately but I can't seem to figure out how to they ...
0
votes
1answer
60 views

How to find $P(X=1 ∧ Z=2)$ where $P(X=1)$ and $P(Z=2)$ is given?

$P(X=0) = 1/4$, $P(X= 1) = 1/4$, $P(X=2)= 1/2$ $P(Y=0)= 1/2$, $P(Y= 1) = 1/3$, $P(Y= 2) = 1/6$ It is given X and Y is independent and $Z$ is defined by $XY$ So $P(Z=0) = 5/8$, $P(Z=1) = 1/12$, ...
0
votes
1answer
24 views

Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block. Are there ...
-1
votes
1answer
16 views

Self-avoiding walks from one diagonal to the other on $mxn$ lattice is ${m+n \choose m,n} $

According to wikipedia "self-avoiding walks from one end of a diagonal to the other, with only moves in the positive direction, there are exactly $$ \binom{n+m}{n,m} $$paths for an $m × n$ ...
0
votes
1answer
22 views

Is a boolean algebra closed under countable disjunction/conjunction?

I'm just curious if the properties in a sigma algebra is also satisfied in a boolean algebra. In a boolean algebra, the two operators are closed under finite operations, but can we say they are closed ...
1
vote
1answer
27 views

Do not understand algebra technique used to computer summation

I am going through a practice exam for my Discrete Mathematics class and do not understand the algebra used in the following summation computation. Summation to compute: Answer: What I don't ...
0
votes
0answers
22 views

prove de Rham cohomology of S,the “spherical universe,” is 0-dimensional?

How to prove de Rham cohomology of S,the "spherical universe," is 0-dimensional?(Here, S is a rectangle where if you exit the right, the enter from the top and if you exit the left, the enter from the ...
0
votes
1answer
10 views

Group-theory,discrete mathematics, trichotomous property

Is the intersection of trichotomous relations trichotomous? Generally, trichotomy is the property of an order relation < on a set X that for any$ x$ and $y$, exactly one of the following holds: ...
0
votes
2answers
30 views

How can I compute these values in groups? [closed]

In the group of $\mathbb{Z}_{17}^* $, $ \overline{13}^{-1}=?$
-1
votes
0answers
13 views

A number of 0,1-sequences

Could you find a number of binary sequences length n,which is not more than r units in a row? For example, number of these sequences A(n,r) for n=2 A(n,r)=1 if r=0; A(n,r)=3 if r=1; A(n,r)=4 if r=2;
4
votes
2answers
55 views

Counting numbers of fruit baskets

Suppose you have $10$ apples, $12$ bananas, and $8$ peaches, and you want to divide them into $3$ baskets containing $10$ fruit each. In how many ways can you do this, if the fruit of each type is ...
0
votes
0answers
24 views

How to solve this recurrence relation with a summation in it?

How would one go about solving this recurrence relation: $T(n)$=$\sum_{i=1}^{k}T(n - d_i)$ ? For this recurrence relation, $k$ is the number of coin denominations, and $d_i$ is the specific coin ...
1
vote
1answer
26 views

How many surfaces have $4$ edges…

A 3 regular, plane, connected graph have all surfaces either $4$ or $6$ edges (including the outer surface). How many surfaces has $4$ edges? Let $x$ be the number of surfaces that have $4$ edges ...
1
vote
0answers
32 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
1answer
26 views

Alternate form of Modus tollens applicable?

The definition states that not(q) p--> q ---------- not(p) Is the following form is also true? ...
0
votes
0answers
40 views

congruence solution

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
3
votes
2answers
48 views

Combinatorics - Number of Paths in a Grid with a Hole

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$. I tried using inclusion-exclusion by counting the ...
4
votes
1answer
63 views

If $a$ is not divisible by $7$, then $a^3 - 1$ or $a^3 + 1$ is divisible by $7$

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
0answers
62 views

If $m =4^{n +1}$ with $n>0$ and m is prime then $3^\frac{m-1}{2}$ =-1(mod m)

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
1answer
30 views

Let p be a odd prime, If ord p (a) = h and h is even, then a^(h/2)= -1 mod p

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...