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

2
votes
2answers
1k views

Let G be a graph in which every vertex has degree 2.

Is G necessarily a cycle? I suspect not but I'm having hard time showing this. Also, Let be a tree. Prove that the average degree of a vertex in T is less than 2. I know that the sum of degrees of ...
3
votes
2answers
340 views

Reducing Boolean expressions

Just learning mathematical proof writing and came upon this interesting question Writing an expression using logic. $$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P ...
2
votes
1answer
134 views

Counting flower and committee questions

$1$) You want dozen roses. The florist has white, pink, red, and violet roses. How many possible ways could you make the order? $2$) There are $35$ men and $15$ women. Committee needs to have four ...
2
votes
3answers
613 views

Use the Handshake Lemma to determine the number of edges in GK_n

In chess, a knight's move consists of two spaces either vertically or horizontally, followed by one space in the perpendicular direction. In this way, every knight's move results in an L shaped ...
2
votes
0answers
123 views

What is Algorithmic Graph Theory? [closed]

I'm an undergraduate and I signed up for a course next semester called Algorithmic Graph Theory. The course description doesn't give any details on the contents of the class, and there's no listing of ...
3
votes
2answers
107 views

Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem

So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
1
vote
0answers
87 views

Discrete fractional fourier transform

I have written a code for producing matrix of fractional fourier transform with the help of eigen vectors of fourier transfom matrix. Does anyone know the elements of this matrix ( for example a 4 by ...
2
votes
3answers
2k views

Set Distributive Property Proof

Prove the distributive property for sets: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ I'm not good with proofs but my understanding is that I have to prove 2 things: (1) $A \cup (B ...
4
votes
3answers
13k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
-2
votes
2answers
150 views

Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$

I need to solve this question using the modular exponentiation method.
1
vote
2answers
78 views

What is the set containing only integers congruent to 89 modulo 17?

What is the set containing only integers congruent to 89 modulo 17
2
votes
1answer
49 views

Even weighted codewords and puncturing

My question is below: Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight. (Hint: Do some puncturing ...
3
votes
2answers
111 views

A property of a prime divisor of a number consisting of 1s

For $n>0$ let $A(n) = \underbrace{111 \ldots 11}_{n}$. Prove that if $A(n)$ is divisible by a prime number $p>3$, then $\gcd(n, p-1) > 1$. It is no huge discovery that if $n$ is even, ...
1
vote
2answers
102 views

solving linear recurrence - general solution confusion

I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained. What is ...
1
vote
4answers
140 views

Writing an expression using logic

Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table: $$\begin{array}{ccc|c} P&Q&R&???\\ \hline T&T&T&F\\ T&T&F&T\\ ...
11
votes
3answers
699 views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
2
votes
3answers
303 views

How many numbers between 1 and 10,000,000 don't have the sequence 12? Inclusion-exclusion problem

I got the following question: How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried ...
0
votes
1answer
18 views

Clues to prove average in T is minor or equal than average in a smaller inner interval.

Suppose I want to prove (or disprove) this assertion Let $f$ be a discrete function, $T,h,k$ are constants So these terms are averages over $T$ and over $h$ $\sum\limits_{i=0}^{T}\frac {f(i)}{T}$ ...
1
vote
2answers
106 views

Proper way to define this multiset operator that does a pseudo-intersection?

it's been a while since I've done anything with set theory and I'm trying to find a way to describe a certain operator. Let's say I have two multisets: $A = \{1,1,2,3,4\}$ $B = \{1,5,6,7\}$ How ...
2
votes
2answers
82 views

Probability question about distinguishable and non distinguishable objects

so for part a I got the answer as m choose 1 times (1/m)^b but for part B I am having different approaches and dont know which one is correct approach 1: m choose 2 times (2/m)^m approach 2: m ...
2
votes
2answers
77 views

Polynomial discrete mathematics

I ran into this question: Let $p$ be a prime number. We will work on $\mathbb{Z}_{p}$. Let $d$ be a divisor of $p-1$, $(p-1)/d=r$. Show that the equation $x^{d}=1$ has exactly $d$ solutions on ...
0
votes
3answers
66 views

What does this mean: a polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ has at most $n$ solutions over $\mathbb{Z}_{p}$?

What does this fact mean: "the polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ has at most $n$ solutions over $\mathbb{Z}_{p} $" ? Thanks in advance, Yaron.
0
votes
1answer
141 views

What computer program can calculate Kemeny-Snell's median?

Unfortunately, I didn't find any computer realization for computing Kemeny-Snell's median.
1
vote
1answer
251 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
1
vote
3answers
587 views

Prove that connected graph G, with 11 vertices and and 52 edges, is Hamiltonian

Is this graph always, sometimes, or never Eulerian? Give a proof or a pair of examples to justify your answer Could G contain an Euler trail? Must G contain an Euler trail? Fully justify your answer
2
votes
2answers
92 views

Are these propositions equivalent?

Statement 1: Maria will find job if she learns mathematics. Statement 2: Maria will find a job unless she does not learn mathematics. I know the answer is probably that these are same, but ...
1
vote
1answer
78 views

binary circle - difficult question

I ran into this question and I'm not really sure how to start. we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$, we'll define $n_{w}$ as the number of times ...
1
vote
1answer
36 views

Combinatorial Techniques: Putting two and two together

This is a $3$-part question. I got the first two parts, but could not get the third part (which uses the first two parts): Pick sequence of $8$ coins from sack of $40$ coins, containing $10$ pennies, ...
0
votes
2answers
3k views

Probability 2 people have a birthday in the same month out of 7

What is the probability that 2 people in the group have a birthday in the same month out of 7 people? I know the answers 88.85% however I want to know how to work it out using factorials instead of ...
1
vote
1answer
940 views

Placing beads on a necklace, 7 colours. How many can be made

Dude wants to make a necklace with 7 beads, each a diffrent color. (red, orange, yellow, blue, green, indigo, violet) placed on a chain that is then closed to form a circle. How many different ...
0
votes
1answer
140 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
2
votes
2answers
538 views

Graph Theory adjacency matrix

Is it possible for a graph to exist that meets these conditions. For Graph G the adjacency martix has all 1's in the first row and all 0's in the second row. What I think: it cant exist because if ...
1
vote
1answer
62 views

Is there an explicit solution to: $\arg \min mn : mn \geq k, l_0 \leq n \leq l_1$?

Is there an explicit solution or a fast algorithm to compute: $$\underset{(m, \ n) \in \mathbb{N}_{+}^2}{\arg \min} \ mn \ : \ mn \geq k,\ l_0 \leq n \leq l_1$$ for given constants $k, l_0, l_1 \in ...
1
vote
0answers
84 views

Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
3
votes
2answers
137 views

Symmetric Groups and Commutativity

I just finished my homework which involved, among many things, the following question: Let $S_{3}$ be the symmetric group $\{1,2,3\}$. Determine the number of elements that commute with (23). Now, ...
2
votes
2answers
128 views

Let $A$ be a set, $R$ an empty relation on $A$, what is $A/R$?

Let $A=\{0,1,2\}$ be a set and $R=\{\}$. I know that $R$ is not an equivalence relation, but does it have to be? What is $A/R$ if $R$ is empty? Examples: $R_1=\{(0,0),(1,1),(2,2)\}$, $A/R_1=\{[0], ...
2
votes
0answers
154 views

Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
0
votes
1answer
1k views

Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in ...
1
vote
1answer
29 views

Convergence of Discrete Poisson equation

Are there any sources that show the convergence of the discrete poisson equation? To be clear, by convergence I mean: given the poisson equation in a domain $ M \subset R^2 $, $\Delta \psi = f $, one ...
1
vote
2answers
183 views

Map-Coloring Problem

When we are faced with map-coloring problem, why do we allow countries that meet at only one point to receive the same color? Is it because they do not share the same boundaries or common boundaries? ...
2
votes
2answers
2k views

How do I prove the arithmetic-geometric mean inequality?

I am following along with this bare-bones proof of the arithmetic-geometric mean inequality with two real numbers. I'm having difficulty understanding the logic behind this step: $$ ...
4
votes
1answer
98 views

Finding maximum score in a “bubble pop” game

Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
0
votes
1answer
37 views

Do these two expressions mean the same?

So for a given database we have the sets Persons, Married, Women, Men and Children. I want to express all Women who are not Children and not Married: $$Women\setminus \left ( married \cup children ...
1
vote
1answer
30 views

Prove the existence of a row and a column in the Boolean matrix which satisfy the conditions

"Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove that there is a row and a column such that when the total entries of the row and column are added, the sum is greater than 13." I have ...
2
votes
5answers
187 views

Solving the recurrence relation [closed]

I'm interested in learning how can we solve this linear non-homogeneous recurrence relation? $$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
0
votes
1answer
73 views

Finding a reccurence relation for the following problem

A circular disk is cut into n distint sectors, each shaped liek a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
-2
votes
1answer
147 views

Given the following recurrence relation, prove using mathematical induction

How can we prove this using mathematical induction? $m_1 = 0$ $m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$ Prove using mathematical induction that ...
0
votes
6answers
3k views

Finding the number of subsets of S

How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6? Thanks!
1
vote
2answers
139 views

Use the binomial theorem to expand

How can we expand this using the binomial theorem? $(x^2 + 1/x)^7$
3
votes
3answers
571 views

Why all odd numbers not ending with 5 divide exactly into a number comprising only 9's?

Help me!!It's really frustrating I can't understand this simple thing.The maths instructor in my video,the renowned Arthur Benjamin,states (clip linked below) the following: ...