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
2answers
24 views

Property of the numbering in preorder traversal of the tree

$v$ denotes the vertex which has been asigned the number $v$. The vertices are numbered in the order visited. In preorder all vertices in a subtree with root $r$ have numbers no less than $r$. More ...
0
votes
1answer
27 views

A cycle in an undirected graph

A cycle is a simple path of length at least $1$ which begins and ends at the same vertex. In an undirected graph, a cycle must be of length at least $3$. Could you explain me why that stands??
0
votes
0answers
9 views

Prove the A x B lexicographical ordering is partially ordered

Is this proof? I think I may have the right ideas, but I'm not sure.
1
vote
2answers
47 views

Simple proof by contradiction in graph theory

The question is as follows: Let P be the longest path in a simple graph G, and let $\lambda$ be the length of P. Show that both the starting point and ending point of P must have degree $\le\lambda$. ...
0
votes
1answer
22 views

Encode WELCOME using RSA encryption

I am stuck on a problem using RSA encryption. We are encoding the message WELCOME. $W= 23$ $E= 5$ $L= 12$ $C= 3$ $O= 15$ $M= 13$ $E= 5$ $n =77$ $\text{and}$ $e =31$ I've come up with a couple that ...
0
votes
0answers
21 views

Define another Equivalence Relation from Geometric Figure?

Define relation $W$ on $R^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1−y_1=x_2−y_2$. I have the equivalence classes to be given by $f^{-1}(r)=\{(x,y)\mid x−y=r\}$, where $r∈R$. So how would you define ...
-2
votes
1answer
21 views

Prove the lexicographical ordering on $A \times B$ is partially ordered [closed]

Suppose that $(A, \preceq_A)$ and $(B, \preceq_B)$ are partially ordered sets. Then, the lexicographical ordering on $A \times B$ is also a partial ordering. Can anyone help me prove this?
0
votes
1answer
20 views

How many relations on a set with 6 elements?

I know there is a lot of information on this internet for this, I've been going through it the past 30 minutes. I'm getting confused to if the answer is actually 203 relations, because when I try to ...
0
votes
2answers
42 views

Injective and Surjective [duplicate]

Take it on faith that any nonempty subset of $\mathbb{N}$ has a smallest element. Write $P(\mathbb{N})$ for the power set of $\mathbb{N}$. Define a function $f : P(\mathbb{N}) \rightarrow ...
1
vote
2answers
28 views

How to go about counting the sample set of rolling dice based off previous rolls.

I'm in need of some help. I can't seem to wrap my mind around this question. Here's the task: I have this problem. It goes like this: I am to do an experiment with rolling a dice. There are 3 ...
0
votes
0answers
20 views

Properties of Functions 2

For each part of this problem, give sets A,B, and C, with C ⊂ A, and a function f : A → B satisfying the given conditions. Or, if no such function exists, prove that none exists. (There is no need to ...
0
votes
2answers
20 views

Relation on Funtion A

Suppose a function f : A → B is given. Define a relation ∼ on A as follows: a1 ∼ a2 ⇔ f(a1) = f(a2). a) Prove that ∼ is an equivalence relation on A. I know that I have to prove for the reflexive, ...
0
votes
0answers
30 views

Proof that no Eulerian Tour exists for graph with even number of vertices and odd number of edges

How would you prove that for a connected graph with an even number of vertices and an odd number of edges, at least one of the vertices has an odd degree? My first attempt at solving this has been to ...
1
vote
1answer
46 views

Proofs of Sets and Subsets

I have these proof problems that I need some help on, any direction would be great. Thanks Let A, B, and C be subsets of some universal set U (a) Prove the following: IF $A \cap B$ $\subseteq$ C, ...
0
votes
2answers
76 views

Inclusion-Exclusion Question.

Consider 100 students, each taking at least one of the courses: art, biology and computing. Let 20 students take both art and biology, 31 students take both art and computing, and 24 students take ...
0
votes
1answer
25 views

Properties of Functions

For each part of this problem, give sets A,B, and C, with C ⊂ A, and a function f : A → B satisfying the given conditions. Or, if no such function exists, prove that none exists. (There is no need to ...
2
votes
3answers
31 views

Why is a Symmetric Relation also Transitive?

A relation R on set A is as follows: R = {(1,1), (2,2), (3,3)} R is symmetric! But WHY is R Transitive?
0
votes
1answer
27 views

Bijection Proof on

Can anyone help me prove this? This is what I have so far.
1
vote
1answer
28 views

Prove that it is transitive

Below is what I have so far. I'm pretty sure that it is transitive, but I'm not sure how to prove that it is. Prove that A is or isn't transitive.
-5
votes
1answer
37 views

Prove onto and one to one [closed]

Let $f:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$ be defined by $f(m,n)=2n-4m$. Is $f$ onto and/or one-to-one or neither? Prove.
0
votes
2answers
24 views

Proof with multinomial.

Let $p$ be a prime number. Prove that $p$ divides the multinomial $$\binom {p}{n_1,n_2,\dots, n_k}$$ such that $n_i \neq p$. I tried some approaches but honestly i have no idea what to do.
0
votes
0answers
45 views

Solve recurrence equation problem

I'm given a recurrence equation $g(n) = 6g(n - 1) - 7g(n - 2)$ $ g(0) = 1 \text{ and } g(1) = 3$ I found out $g(2) = 11, g(3) = 45,$ and $g(4) = 193$ and I can't see a pattern still I also ...
-2
votes
1answer
27 views

Permutations and image of numbers [closed]

How can I solve this? How many is permutations of the numbers 1,...,10 in which no even number maps to itself. Thanks
2
votes
3answers
44 views

How can I prove that the square of an even number ends in 0/4/6?

I am trying to prove that the last digit of the square of an even number is either 0, 4, or 6 but I'm completely lost and have no idea how to tackle this problem.
0
votes
0answers
37 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
1answer
27 views

how to prove this expression (preferably by induction)

for all integers n>=1 if A and B1 ,B2,B3,... are any sets! $$\cup_{i=1}^n(A\times B_i)=A\times\cup_{i=1}^nB_i$$ induction way is better.
0
votes
3answers
32 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
0
votes
1answer
25 views

Relations on set based off Cardinality [closed]

Let A be a set with cardinality 6. How many relations on A are there? How many are reflexive? symmetric? Not sure where to go with only this information. Thanks!
0
votes
1answer
29 views

Function Relations

Suppose a function $f : A → B$ is given. Define a relation $∼$ on $A$ as follows: $a_1 ∼ a_2 ⇔ f(a_1) = f(a_2)$. a) Prove that $∼$ is an equivalence relation on $A$ b) Since $∼$ is an equivalence ...
0
votes
1answer
18 views

Show that $W$ equivalence relation on $\mathbb{R}^2$

Define relation $W$ on $\mathbb{R}^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1-y_1=x_2-y_2$. Show that $W$ is an equivalence relation on $\mathbb{R}^2$. I believe it is reflexive, not sure about ...
1
vote
2answers
39 views

Flipping a coin until 4 heads occur, or until flipped 7 times. How many combinations are possible?

Question: A coin is tossed until either 4 heads occur or until the coin has been tossed 7 times. How many heads/tails sequence are possible? For example, HTHTTHT, HHHH, THHTHH, and TTTTTTT are all ...
1
vote
1answer
24 views

Help to describing a recurrence for $l_n$

I have to describe a recurrence for $l_n$, the number of lobsters caught in year $n$. The task says: a hobby fisherman estimates the number of lobsters he will catch in a year as the average of the ...
1
vote
2answers
23 views

Probability of selecting three of the same thing from a collection

Question: A collection of 6 items is to be randomly drawn from a bin containing 100 good items and 8 defective items. What is the probability that exactly 3 of the items chosen are defective? My ...
0
votes
1answer
20 views

Formula to find the sum of digits

I want to know if there is a way to find the sum of the digits of a power $a^b$ For exemple $9^{14}$ = 22876792454961 , Sum is 2 + 2 + 8 + .... + 6 + 1 Thanks in advance.
0
votes
0answers
13 views

Green's Function of second diff equation

How can I calculate the Green's function of following equation ? $$ G(r,z|r_0,z_0)? $$ $$ \frac{1}{r}\frac{d}{dr}\left(r\frac{dE}{dr}\right)+\frac{d^2E}{dz^2}+\left(k_0^2-\frac{k_x^2}{r^2}\right)E=0 ...
-3
votes
0answers
26 views

Help with computation [closed]

The function m(n) for every 1 ≤ n ≤ 220. The value of m(n) depends on the prime factorization of n. Describe how to compute m(n). n :1,2, 3, 4, 5, 6, 7, 8, 9, 10 M(n):1,-1,-1,0,-1, 1,-1, 0, 0, 1
2
votes
0answers
35 views

Help in deriving a formula

Background I am working on a vocabulary building application under which I am trying to build an adaptive test for the student. The test would be adaptive to the user's response: When the student ...
-3
votes
0answers
32 views

Prove Discrete Math [closed]

This is a prove that I have been trying to solve and I have no idea how to do this. Anything will help! ...
1
vote
2answers
103 views

Permutations / Combinations - suppose a word is a string of 8 letters of the alphabet with repeated letters allowed

1.) How many words are there? Not sure how to solve this since repeated letters are allowed. $n^r$ is the formula we are told to use for permutations with repeated objects, but $26^8$ seems like too ...
0
votes
2answers
23 views

Help with large modular power [closed]

as title said, specifically trying to compute 7^64 mod 101 by hand
0
votes
2answers
23 views

Prove following argument is valid

Prove the following argument is valid. If Ralph doesn't do his homework or he doesn't feel sick, then he will go to the party and he will stay up late. If he goes to the party, he will eat too much. ...
0
votes
1answer
37 views

Making reccurence relation

I have trouble in understanding how to make recurrence relations. I read some of the questions on stack exchange but this stuff is not intuitive to me. For example, when we want to find a number of ...
-4
votes
0answers
22 views

University sets and functions [closed]

Let $A = (1,2,3,4,5,6,7,8,9)$ a) How many functions $f:A\to A$ are there so that $f(1) = 2$ b) How many functions $f:A\to A$ are there so that $f(f(1)) = 2$ c) How many functions $f:A\to A$ are ...
1
vote
1answer
17 views

Sn−1 Sn-2 Sn−3 pattern generalize it n-k substitute for base case prove by induction..need to know how to do this question using these steps

A sequence $S_0,S_1,S_2,\dots$ is defined recursively as follows $S_0:=3,\quad$$S_n:=S_{n−1}+2n$ for $n≥1$ Calculate a few terms and conjecture a formula for $S_n$ as a function of $n$. Prove the ...
1
vote
2answers
68 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
1
vote
1answer
22 views

Proof of discrete logarithm?

If you have that $a$ is a primitive root mod p. How can you prove this discrete logarithm property? $log_{a}(b_1b_2) = log_{a}(b_1) + log_{a}(b_2)$ (mod $p-1$) I see the proof for the regular ...
0
votes
2answers
50 views

Prove that a function in one to one and onto.

Let $f: \mathbb{R} \to \mathbb{R}$ be the function $f(x) = 2\lfloor x\rfloor - x$ where $x \in \Bbb{R}.$ So my current idea using $x = n + r$. So $2\, \mbox{floor}(x) - x = 2n-(n+r) = n-r$. And then ...
2
votes
1answer
94 views

Fight against the Hydra - Graph Theory

The following problem is supposed to be a nice application of the basic knowledge of graph theory. I consider it however as difficult and I would be happy if someone could help me find a solution. ...
2
votes
2answers
26 views

Prove that for any integers x,y there are integers a,b such that gcd(x,y) = ax + by

How would I go about proving that: For any integers x,y there are integers a,b such that gcd(x,y) = ax + by? One thing I noticed is that when x is a multiple of y or vice versa, the smaller number is ...
0
votes
0answers
34 views

Poker Hand Equivalent Relation

Let $P$ be the set of all possible poker hands. Define a relation $J$ of $P$ by $a$ is $J$-related to $b$ iff $a$ and $b$ have no cards in common. Is $J$ reflexive? Symmetric? Transitive? Having a ...