Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
0answers
29 views

Two-dimensional Topology and Ordering

This question came up for me when thinking about an answer to this: http://stackoverflow.com/questions/16326318/finding-blocks-in-arrays. I had the idea of listing the 1's, for example: ...
1
vote
1answer
258 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
2
votes
1answer
187 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
0
votes
1answer
54 views

Conditional Probability, weather related

If it is raining, I take my car to work 90% of the time, I take my bike 9%, and I walk 1%. If it is not raining, I take my car 10%, bike 60%, and walk 30%. What is the probability it is raining if I ...
0
votes
1answer
29 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
8
votes
1answer
200 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is ...
1
vote
0answers
57 views

Non-independent two consecutive draws from two urns

Suppose there are two urns: in urn A, there are r red balls and w white balls. In urn B, there are b black balls. Suppose we do the following experiment: draw k balls from urn A. Among those k balls, ...
7
votes
2answers
214 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
2
votes
1answer
80 views

Proving this realtion is not a transitive relation

I have trouble proving how the following statement is false: The relation $g = \{\,(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\,\}$ is transitive. I know you have to use $yRx$, $zRy$, and $xRz$, but I'm ...
0
votes
0answers
137 views

Replace a continuous probability distribution with a discrete one

Say one wants to fit a curve $f(x)$ to a set of noisy data points $(x_i, y_i)$. If the error for each point $y_i$ is assumed to be normally distributed with variance $\sigma_i^2$, one wants to find ...
1
vote
2answers
79 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
-1
votes
1answer
1k views

Proof of divisibility by 2 and 3 if and only if divisible by 6

I can't find a way of proving that: For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6. I’m not sure where to go from here. Any help would be great!
3
votes
1answer
227 views

diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
49 views

Number of circular placements of $n$ identical letters such that no two letters are adjacent.

Suppose I have to place $3$ identical letters on a circular table which has $7$ slots in such a way that no two letters are in consecutive slots. In how many ways can I do this? Can this be ...
2
votes
1answer
81 views

Solving the equation for $x$ in $Z_n$

How do you solve for x in the the $Z_n$ specified? For example, for the equation: 1) $3\odot x\oplus8\equiv1(\rm{mod} 10)$ or 2) $342\odot x\oplus 448\equiv73(\rm{mod}1003)$ How would you solve for ...
3
votes
2answers
94 views

Counting problem: Assigning students to dorm rooms

This was a question on a recent test and I was hoping for a conclusive answer and reasoning behind it. A local university housing office has a problem. It has 11 students to squeeze into 3 dorm ...
2
votes
3answers
287 views

Prove that Statements forms are tautologies

Given variable statement forms $A$ and $B$. How to prove that if $(A\land B)$ is a tautology then $A$ and $B$ are tautologies too?. Mi approach would be a proof by contradiction, something like: If ...
2
votes
2answers
101 views

Number of rectangles with odd side lengths on a chess board?

Given an 8x8 chess board, how do we find the total number of rectangles with odd side lengths? (Both sides have odd length). In general, what would be an elegant method to deal with problems like ...
3
votes
1answer
86 views

How to prove the identity $(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$?

I am stuck in proving the following : $$(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$$ NOTE: I don't want any combinatorial proof. I think it is some algebraic manipulation.
1
vote
1answer
74 views

Proof by Induction solution not understood

Here is a question and solution but I don't understand what's happening after $m = m+1$. How does $(3(m+1))!$ equal $(3m)!(3m+1)(3m+2)(3m+3)$? Should it not be $(3m+3)!$? Same thing with the ...
1
vote
1answer
77 views

True/False cardinal question in Discrete Maths

I would like some help on these claims. Thanks in advance! True or false? If true, give a proof, if not, give a counterexample. If $A$ is a set of functions $\Bbb N \rightarrow \Bbb N$ and for ...
1
vote
2answers
1k views

Solving Linear Congruence Equation: Finding the Nonnegative Integer Representation

I have a question for a part of the following problem: Solve the linear congruence 7x ≡ 6(mod 29) I understand how to find the linear combination equality using ...
0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
1
vote
2answers
484 views

Monotonic Lattice Paths and Catalan numbers

Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia I do not understand ...
0
votes
4answers
117 views

the probability of guessing a number [closed]

Choose any natural number. For example I would choose: 3852011231231280130218920382342312420234801232321241231212131234 (and so for for another few bilions of digits) What's the probability that ...
0
votes
1answer
94 views

Graph with 5 vertices - # of spanning trees

If a graph has 5 vertices, all of them connected to each other vertex, how many different spanning trees exist? I'm thinking the answer might be $4*3*2$, because the first point has 4 options to go ...
0
votes
3answers
51 views

Prove that the set of all arithmetic progressions is a countable.

I just didn't have an idea of how to solve this problem. Prove that the set of all arithmetic progressions is a countable. Thanks in advance for any assistance.
1
vote
1answer
113 views

Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane

A question I found hard to solve. Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane Thanks in ...
1
vote
1answer
117 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
1
vote
2answers
605 views

Prove logical equivalence

\begin{gather} (p \to q) \equiv (\lnot p \lor q) \\ \lnot(p \land q) \equiv (\lnot p \lor \lnot q) \end{gather} Can these be proven without truth tables?
-2
votes
1answer
145 views

How to write a recursive algorithm?

Write a recursive algorithm SUM(A,k) that can be used to calculate the summation $\sum_{k=0}^na_k$ , where $\{a_0,a_1,a_2,…,a_n \}$ is an arbitrary (given) sequence of numbers stored in array A. Use ...
0
votes
0answers
32 views

Expected number of generations

Consider the following simplistic model of transitions between social classes as defined by Sociologists. Only males are considered, and by assumption every male has exactly one son. Let Xn denote the ...
0
votes
2answers
159 views

Domain of a Relation from A to B

The latest versions of Susanna S. Epp's Discrete Mathematics book (both the First Brief Edition, and the full Applications 4th edition) define a relation from $\mathcal{A}$ to $\mathcal{B}$ as a ...
1
vote
1answer
65 views

How do i find the matrix iteration sequence?

Matrix: $$ A=\left(\begin{matrix} 25 & 8 \\ 10 & 30 \end{matrix}\right) $$ Iteration sequence: $$ \begin{align*} x_{n+1}&=Ax_n, & x_0 &= \left(\begin{matrix} 1 \\ 90 ...
3
votes
2answers
94 views

Probability distribution of product of integers

I have a scoring system based on 5 factors with integer values from 1 to 5: Score = A * B * C * D * E So the Score can range from 1 to 3125. Each of the factors ...
2
votes
2answers
83 views

Is there a tutorial that uses english to form an example of a proof, or a very simple way to show how a proof works?

I am in a discrete math in college and would like to understand proofs. I had to prove the fundamental theorem of calculus in Calc 1, and did horribly in Linear algebra because of proofs. How does one ...
1
vote
2answers
201 views

Function - Test of Transitivity

Relation R in the set N of natural numbers defined as R = $\{(x, y): y = x + 5 $and $x < 4\}$ We can make set : (1,6)(2,7)(3,8) Is this a transitive function please guide..
0
votes
1answer
57 views

Random variables and permutations [duplicate]

I'm trying find the number of ordered triples of non-negative integers $a, b, c$ whose sum $a + b + c$ is a given positive integer $n$. I've related it to the concept of distinguishable balls in ...
2
votes
1answer
156 views

Ackermann’s function $A(m,n)$

Please show the shortest steps possible. thanks. \begin{align*} A(0, n) &= n + 1,\ n \geq 0;\\ A(m, 0) &= A(m − 1, 1),\ m > 0;\ \text{and}\\ A(m, n) &= A(m − ...
3
votes
6answers
1k views

Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$).

How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large ...
1
vote
3answers
205 views

Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
3
votes
2answers
192 views

Seating Multiple People at Multiple Tables

In how many ways can we seat 100 people around 20 different circular tables in such a way that there are five people per table? Am I right in assuming that we're only considering unique ...
3
votes
2answers
58 views

Modular Exponentiation

Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$ I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
2
votes
2answers
134 views

Probability of Choosing a Card from a Deck

There were quite a few deck of cards probability problems and I went through a few but couldn't find anything close so please forgive me if this is a repeat. The question is as follows: Two cards ...
0
votes
2answers
51 views

How to Count Possible Orderings of Digits with Required Substrings

The question is as follows: How many orderings of the digits from 1 to 8 contain the sub-strings 12, 23 or 34? For example, 57238614 is one such ordering since 23 appears, and 12345678 works, ...
1
vote
2answers
86 views

How can be done by the method of mathematical induction?

We are given that $P(x+1)-P(x)=2x+1$ We also know that $P(0)=1$ We want to prove that $P(2004)=(2004)^2 +1$ Can someone explain how can be solved with mathematical induction? Thank you in advance!
2
votes
3answers
94 views

Solve for $x$: $4x = 6~(\mod 5)$

Solve for $x$: $4x = 6(mod~5)$ Here is my solution: From the definition of modulus, we can write the above as $ \large\frac{4x-6}{5} = \small k$, where $k$ is the remainder resulting from ...
1
vote
2answers
133 views

Strategies to solve congruence problems

Which strategy is best to use when solving problems of the following sort? $$x^{29} \equiv 3\pmod {184}$$
1
vote
2answers
42 views

Do not understand what this question is asking… or the notation, Discrete Structures/Relations

Let X = {1,2,....,10} Define a relation R on X x X by (a,b)R(c,d) if a + d = b + c I lose track of what it is asking on the part italicized. I have a similar question that ends in ad = bc as well ...
0
votes
1answer
59 views

Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$. This is seen ...