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

learn more… | top users | synonyms

3
votes
1answer
411 views

How Entropy scales with sample size

For a discrete probability distribution, the entropy is defined as: $$H(p) = \sum_i p(x_i) \log(p(x_i))$$ I'm trying to use the entropy as a measure of how "flat / noisy" vs. "peaked" a distribution ...
2
votes
5answers
432 views

Finding the number of non-neg integer solutions?

How would I find the number of non negative integer solutions to this problem? $$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.
1
vote
2answers
84 views

Help solving recurrence relation, $a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$

This is in my homework, and I am not sure how to go about this, I've read the book but I can't seem to grasp what to do. Help? $$a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$$ where $a_0 = 2$, $a_1 = -1$, ...
0
votes
2answers
140 views

find recursive solution $T(n)=2T(n/2)+n-1$

I want to solve this: $$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$ I try : \begin{align*} n &= 2^m \\ T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\ 2 ^ m &= B \\ T(B) ...
5
votes
3answers
162 views

Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$

Bring the following recursion relation to an explicit expression: $$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$ $a_{0} = 0$, $a_1 = 1$, $a_2 = 2$ All the examples I have seen were with maximum 2 steps back ...
1
vote
1answer
38 views

Details about a Recurrence Relation problem.

I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step: If $H_n$ is the number of moves it takes for n rings to be ...
3
votes
1answer
196 views

Solving a recurrence relation, $a_n = \sqrt{n(n+1)}a_{n-1} + n!(n+1)^{3/2}$

I'm trying to solve the following recurrence relation, but I have a problem with the factorial part. I would like to evaluate its particular solution. I would like also to suggest a textbook for ...
4
votes
3answers
3k views

How many options are there for 15 student to divide into 3 equal sized groups?

How many options are there for 15 student to divide into 3 equal sized groups? Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why. Can anyone please enlighten me?
2
votes
0answers
97 views

Expansion vs Sparsest cut

let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is $$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$ where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
18
votes
4answers
3k views

Are these 2 graphs isomorphic?

They meet the requirements of both having an $=$ number of vertices ($7$). They both have the same number of edges ($9$). They both have $3$ vertices of degree $2$ and $4$ of degree $3$. However, ...
0
votes
1answer
88 views

Is there a formula to calculate the minimum height of an n-nary tree with L leaves?

I'm trying to figure out if there is a way to calculate the minimum height of an n-nary tree with L leaves. Is there such a formula?
1
vote
1answer
106 views

Prove that the existence of a bridge is an invariant

An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies ...
2
votes
3answers
149 views

Ball-counting problem (Combinatorics)

I would like some help on this problem, I just can't figure it out. In a box there are 5 identical white balls, 7 identical green balls and 10 red balls (the red balls are numbered from 1 to 10). A ...
5
votes
4answers
269 views

Prove or disprove the following statements involving greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
1
vote
3answers
301 views

Does the following graph have a Hamilton circuit?

A Hamilton circuit (or path) is a path that visits each vertex exactly once (except the start/end point) and ends at the starting point. I've stared at this for quite a while and cannot find a ...
2
votes
4answers
374 views

Transitivity of union of two transitive relations

I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union ...
2
votes
2answers
56 views

Confused about combinatorials

How do I solve 4$\cdot$6 = 8$\cdot$3 by a combinatorial proof? How can I start this proof? I know that I can show a two pictures that represent 24 but I'm not entirely sure how to go about this. ...
2
votes
2answers
79 views

Show using induction (coupled linear recurrences)

Some homework help would be greatly appreciated, took a screenshot and made an image to make it easier to show and get help with. (2) Consider the numbers defined recursively by $a_1=3$, $c_1=5$, ...
3
votes
2answers
70 views

How to show: if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$? [duplicate]

A little stumped on this problem, any help would be greatly appreciated. Show that for all $a,b,c \in \mathbb{Z}$, if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$.
2
votes
0answers
29 views

functional dependencies

Consider the schema R(ABEFJK) with functional dependencies {BE->JK, J->FA, F->B}. I was told to find all the keys for this function this is what I did I dont know if im correct ...
0
votes
1answer
107 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
2
votes
1answer
114 views

Inclusion Exclusion Principle Problem

There are 28 people in your family consisting of 18 adults, 13 females, and 11 who have purple hair. There are 11 adult females, 6 of whom sport purple hair. There are 10 adults with purple hair. ...
1
vote
1answer
48 views

question about sets

I have this as a beggining to a question: $A\subseteq Z^2$ $$ A = \left \langle \left ( 1,7 \right );\left ( 7,2 \right );(2,3) \right \rangle = \left \{ ...
1
vote
2answers
132 views

Trees with vertex set

I am having hard time understanding and solving the following question: There are exactly three trees with vertex set {1,2,3}. Note that all these trees are paths; the only difference is which ...
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
299 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
128 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
543 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
121 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
95 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
79 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 ...
3
votes
3answers
11k 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
143 views

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

I need to solve this question using the modular exponentiation method.
-1
votes
1answer
85 views

Convert $435_{10}$ and $220_{10}$ to both their hexadecimal and octal expansions [closed]

I need to convert 435 and 220 from their decimal form, to their hexadecimal and octal expansions.
1
vote
2answers
76 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
42 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
103 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
96 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
134 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
552 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
270 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
103 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
73 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
74 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
136 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
242 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
557 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