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

Can a line be constructed from points? [on hold]

Points can´t touch each other, no matter how close you bring them together. It´s zero-dimensional. The object wich is one dimensional higher (one-dimensional) is the (continuously) line. But how can ...
-2
votes
1answer
49 views

Do the $2$ modulus $3$ can be $-1$ or just $2$?

I need to calculate $2$ modulus $3$ as $2<3$ then the answer should be $2$ but instead in a math problem they use it as $-1$. Is this possible? thanks
0
votes
1answer
22 views

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$. I've found the characteristic equation to ...
3
votes
4answers
32 views

Show that the $C_n \geq 4^{n-1}/2^{n}$ where $C_n$ is the Catalan number

I write $C_n=\frac{1}{n+1} {2n\choose n}$ and try to prove this claim by induction. But it didn't quite work out. Any idea how to do this without much computation?
0
votes
1answer
11 views

How to develop a formula for a function?

What are the general tips and techniques to define an explicit formula for a function when the mapping of that function is known. Say f: N to Z (N is natural numbers and Z is integers). In this ...
0
votes
1answer
39 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
3answers
64 views

Prove or disprove the congruence

Prove or disprove the congruence below: $$15 + 111^5· (−10)\equiv 5 \pmod{11}$$ I am not sure where to start because we cannot use a calculator this problem? Can anyone guide me?
1
vote
3answers
41 views

Find a close form expression for $f(x)$

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side ...
0
votes
2answers
41 views

Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$?

Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$? Any ideas on how to solve this one?
2
votes
1answer
9 views

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number ...
1
vote
2answers
89 views

How to deduce the size of C∩B from the sizes of A, B, C, A∩C, A∩B and A∩B∩C?

The original question was: A small school with 16 students has a cricket team with 11 players, a netball team with 7 players, and a chess team with 4 players. Each student is on at least one of ...
0
votes
0answers
38 views

Chromatic number of finite directed graph [on hold]

I can not solve this problem: There is 51 man in a company. Each man hates exactly 3 colleagues. We need to split this company into $n$ groups, such that people within group have mutual ...
1
vote
1answer
22 views

Show that $R(k,l) = R(l,k)$

Let $R(k,l)$ denote the Ramsey number.We proved in class a theorem that says $$R(k,l) \leq {k+l-2\choose{k-1}} $$ And supposedly we can use this to show that $R(k,l) = R(l,k)$ for all $k,l \in ...
0
votes
1answer
70 views

How to calculate P(A∩B), P(A∩C), P(B∩C) and P(A∪C), P(B∪C)?

A particular computer program outputs a number in {0,2,3} with probabilities as follows: $0 $ has a probability of $\frac{1}{3}$ $2$ has a probability of $\frac{1}{2}$ $3$ has a probability of ...
-2
votes
0answers
24 views

Discrete Mathematics Big O [on hold]

Doing some review studying for my discrete math class which starts tomorrow, it extensively covers big $O$ during the spring course. I ran into a few questions that I just wanted to confirm were ...
0
votes
1answer
23 views

Snakes and Ladders and Sample Space

for my Data class project we had to play a board game and do an analysis of it. My group chose rehashed version of Snakes and Ladders. I am almost done the majority of the project, but am stuck on ...
-3
votes
0answers
24 views

Combinatorics and Factorials. [on hold]

An urn contains 7 red, 8 yellow and 13 green balls; another urn contains 9 red, 4 yellow and 6 green balls. We pick a ball from each and record the colors. How many pairs (one ball from each urn) have ...
-2
votes
0answers
18 views

Discrete uniform circular distribution [on hold]

1) Have a distribution of a discrete number N of angular values in the interval [0:360] 2) Map these N values onto a unit circumference. 3) Automatically determine the two values between which all ...
0
votes
1answer
37 views

Find the expressions for the given binary strings and tertiary strings:

Find mathematical expressions for each of the followings: The number of ternary strings (strings of 0s, 1s and 2s) of length 10. The number of strings of 5 lower case letters (a-z) that do no ...
-5
votes
1answer
53 views

How many palindrome numbers between 1 and 1,000,000? [on hold]

Though trivial since a complete response will include a valid proof, single-digit numbers will be considered to count towards the total.
3
votes
1answer
27 views

Prove $2^{X \cap Y \cap Z} = 2^X \cap 2^Y \cap 2^Z$ for any three sets $X, Y, Z$

Could anybody check my solution to this question please? Question: Prove $2^{X \cap Y \cap Z} = 2^X \cap 2^Y \cap 2^Z$ for any three sets $X, Y, Z.$ My solution: If $a \in 2^X \cap 2^Y \cap 2^Z$, ...
-1
votes
0answers
39 views

Pigeonhole principle prove or disprove [on hold]

Please help me to prove this statement whether is correct: For all $f:\mathbb{N}\to \mathbb{N}$ and $t\in \mathbb{N}$, there exist distinct $i,j\in\{0,1,...,3^{t+3}\}$ satisfying: $$f(i+k)≡f(j+k) ...
0
votes
1answer
18 views

Discrete Math Big O Notations

I'm studying for my discrete math class and I don't fully understand how to proof how a function is not a big O for certain questions. I understand that you have to assume that it is big O and proof ...
0
votes
0answers
13 views

Set theory-commutative,idempotent property

Is $A \backslash B'$ commutative and idempotent? I think that this is commutative, but how can I prove it? With Venn diagram? And what about the idempotent property? I think this is idempotent too.
4
votes
4answers
682 views

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side? My approach: Since each side of the table seats two people, there are ...
-2
votes
0answers
17 views

Principle of Inclusion/Exclusion (PIE) Homework Help [duplicate]

Prompt Suppose Sue is a Mail Carrier who is crazy. He likes to ensure that none of the n houses on his delivery route get the mail they are supposed to. Your goal, should you choose to accept it, for ...
7
votes
8answers
2k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
1
vote
1answer
34 views

Combinatorial problem of tournament

Suppose there are $n$ teams playing a tournament. Each team plays exactly one game against each of the other teams. In each game the winner is awarded $1$ point, the loser gets $0$ point and each of ...
5
votes
5answers
8k views

Calculate number of small cubes making up large cube given number in outermost layer

I have a large cube made up of many smaller cubes. Each face of the cube is identical, and all of the smaller cubes are identical. I need to calculate the number of small cubes that make up the large ...
3
votes
2answers
80 views

Understanding counting.

I encountered this question recently: Suppose there are 3 benches in the front row and 7 benches in the second row, how many ways a group of 10 children can be seated in such arrangement? ...
0
votes
1answer
22 views

Find normal basis of the field $GF(3^6)$ and find the normal matrix

I am working with a homework is about normal basis on fields GF and I want opinions and maybe if you can help me in some doubts. 1) Find normal basis of the field $GF(3^6)$ which is understood as a ...
-2
votes
0answers
22 views

Mathematical reasoning [on hold]

I need help starting this questions. i got the first one done. Let [a] ∈ Zn be invertible: there is a class [b] ∈ Zn such that [a] · [b] = [1]. Prove that then [a][x] = [a][y] if and only if [x] = ...
0
votes
1answer
24 views

Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any ...
1
vote
1answer
17 views

Method for calculating minimum number of transmissions?

(This is a real issue I face.) I have $42$ files I want to transmit. I tried sending them in a single archive but four of them had issues, and as a result the entire archive was rejected. I do know ...
-1
votes
2answers
46 views

Using the definition of $f$ is $O(g)$ proof:

I'm studying for my discrete math class and I don't understand how to prove big O notation. I understand that $f$ is $O(g)$ of another if $f(x) \le c g(x)$ holds. How would I go about proving $\sin ...
0
votes
1answer
17 views

Cut property for minimal spanning trees.

The question is presented as follows: Prove the following cut property. Suppose all edges in $X$ are part of a minimum spanning tree of a graph $G$. Let $U$ be any set of vertices such that $X$ does ...
0
votes
2answers
19 views

How to calculate three constants in a linear recurrence problem.

Question: Verify that $x^3 - 3x^2 + 4 = (x^2 - 4x + 4)(x+1)$ And solve linear recurrence: $f(0) = 1$, $f(1) = 0$, $f(2) = 14$, $f(n) = 3 f(n-1)- 4 f(n-3)$ The characteristic equation is already ...
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
15 views

Give formal proof for following basic conversion

Give formal proof for following basic conversion A ^ B ⇒ (A ⇒ B) This is instruction that I got to solve the problem This not an equality. It can be proven, but it isn't an equality! I did ...
2
votes
3answers
63 views

How many ways are there to distribute 26 identical balls into six distinct boxes such that…

How many ways are there to distribute $26$ identical balls into $6$ distinct boxes such that: (a) The number of balls in each box is odd (b) The first three boxes contain at most $6$ balls each I ...
-3
votes
0answers
30 views

Discrete circular distribution [on hold]

Having a distribution of a discrete number N of angular values [0:360], not necessarily all adjacent, ordered in time. How to determine the angular maximum and the minimum of this distribution? ...
0
votes
1answer
16 views

Stirling number of first kind monotone for a half

Show that every $n>0$, there is some m(n) such that $$s_{n,0}<s_{n,1}<... s_{n,m(n)}>s_{n,m(n)+1}>...>s_{n,n}$$ Where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and $s_{n,k}$ is ...
1
vote
1answer
27 views

How many binary relations can be defined on a set of $5$ elements?

Let $X$ be a set with $5$ elements. How many binary relations on $X$ are either reflexive or symmetric or both? show work. you need not simplify the answer.
1
vote
1answer
124 views

Forward Algorithm Hidden Markov Model matrix help [Discrete]!

So this may seem like a bioinformatics question but it is the math part that is giving me trouble. I'm using a Python package called YAHMM to model DNA sequences. I created a model with two states ...
0
votes
2answers
40 views

Why does $\sum_{k=1}^{\infty}\sum_{\ell=0}^{k-1} = \sum_{\ell=0}^{\infty}\sum_{k=\ell+1}^{\infty}$

I'm trying to understand why this is true $$ \sum_{k=1}^{\infty}\sum_{\ell=0}^{k-1} = \sum_{\ell=0}^{\infty}\sum_{k=\ell+1}^{\infty} $$
3
votes
0answers
46 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
3
votes
1answer
67 views

Using Euclid's algorithm to find Multiplicative Inverse 71 mod 53

I begin by writing out the recursion until a mod b == 0 53 -> 71-> 53-> 18-> 17 ->1 -> 0 to get in the form $sa+tn$ starting with $1 = 18-17$ I then substitute $17 = 53-(18\cdot2)$ this gives me ...
0
votes
1answer
16 views

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game: In a pile there are two red balls, four green balls, four blue balls, and ...
3
votes
3answers
51 views

Prove that $24^{31}$ is congruent to $23^{32}$ mod 19.

According to my knowledge, to prove that $24^{31}$ is congruent to $23^{32}$ mod 19, we must show that both numbers are divisible by 19 i.e. their remainders must be equal with mod 19. Please correct ...
-2
votes
1answer
34 views

How do we know that $c|a$ if $c=\gcd(a,b)$ [on hold]

Prove that if $c = \gcd(a, b)$ then $c^2| ab$. Proof: If $c = \gcd(a,b)$ then $c|a$ and $c|b$, therefore $c^2|ab$. I do not understand how $c|a$ and $c|b$ if $c = \gcd(a,b)$