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
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
53 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
38 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
17 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
25 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
23 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 ...
0
votes
1answer
41 views

Prove that the set of the subsets of N of size n is countable [closed]

How can I prove that the set of subsets of N of size n is countable? X∈P(N) | |X| = n. Where do I go on from here? Also how can I prove that the set of all finite subsets of N is countable.
2
votes
3answers
141 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
1answer
24 views

Graph theory 27 cube cheese and mouse problem [duplicate]

A cubic cheese consists of 27 smaller cubes of cheeses (3x3x3). A mouse will eat the first cheese cube and then eat an adjacent cheese cube (no diagonal eating allowed). Show that the mouse can't end ...
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
0
votes
0answers
19 views

On discrete log calculation - safe primes need

Given a prime $r$ consider $g^z=h\bmod r$ where $z$ is unique mod $r-1$ where $r-1=2pq$ for primes $p,q$. Does this help simplify the discrete logarithm problem?
0
votes
0answers
24 views

what will be closed form of $P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$

Let $$P_0=1,$$ $$P_1=x,$$ $$P_n(x)=xP_{n-1}-P_{n-2}.$$ For some $v∈\{1,2,…,n+1\} $, what will be closed form of $$P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$$ I want a close form like ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
0
votes
0answers
19 views

Discrete Math - RSA Encryption problem

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly ...
0
votes
0answers
14 views

Show there are 2 distinct paths that connect two foreign subsets of a 2-connected graph

Let $G$ be a simple 2-connected graph with at least 4 vertices. If $V(G)$ the set of vertices, let $U,W$ be subsets of $V$, with no common elements, with $|U|=|W|=2$. Show that there are 2 distinct ...
0
votes
1answer
29 views

Show there is a subgraph of G with minimum degree k

Let $G$ be a simple, connected graph with $n\ge k+1$ vertices and $m\ge (k-1)(n-k-1)+{k+1 \choose 2}$ edges. Show there is a subgraph of $G$ with minimum degree at least $k$. (Not necessarily ...
1
vote
2answers
11 views

function relations anti symmetric

I have the following relation $(x,y) \in R$ iff $x=y^2$. The book says it is anti-symmetric but it doesn't show the proof. Can you help me out by showing how to prove it?
2
votes
1answer
22 views

Need help proving this set identity

I need some help with this question for Discrete Math... It says: Let $A$, $B$ and $C$ be sets. Establish the identity: $A\cap(B-C) = B\cap(A-C)$ Now I've worded what I have, but just let me ...
-1
votes
3answers
49 views

How many numbers from 1 to 99,999 contain exactly one of each of the digits 2,3,4,5? [closed]

How many numbers from 1 to 99,999 (in their ordinary decimal representations) contain exactly one of each of the digits 2,3,4,5? I'm trying to solve this problem using rules of ...
0
votes
1answer
31 views

big theta question,not sure is book mistake or my misunderstand…

I have $\Theta$-notation question from my new book example solution... the example question is: Find $\Theta$ bound for $$f(n)={n^2\over 2} - {n\over 2}$$ and the book solution is : $\displaystyle ...
0
votes
2answers
15 views

How is this base conversion property explained?

converting $(7)_9$ to base 3 = 21, converting $(77)_9$ to base 3 = 2121 and so on. I am curious as to what exactly makes this true. I am guessing it has something to do with the relation of powers as ...
-1
votes
0answers
70 views

Find $A^n$ for n=0,1, and 3: Languages and FSM

I am having trouble trying to work out this finite state machine and languages question. Let $A=\{11,00\}$. Find $A^n$ for $n=0,1, 3$. Where would I begin?
16
votes
4answers
6k views

What is the smallest number of people in a group, so that it is guaranteed that at least three of them will have their birthday in the same month?

How should I begin solving this? I know that for months, there are 12, and 3 people from a small group suppose to have birthdays in the same month. Do I just multiply $12\times 3 = 36$ people? Or ...
1
vote
5answers
43 views

Stuck : Using inverses to solve linear congruences?

Question : What are the solutions of the linear congruence 3x ≡ 4 (mod 7)? Step 1 - We know that −2 is an inverse of 3 modulo 7. Step 2 - Multiplying both sides of the congruence by −2 shows that ...