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

6
votes
1answer
304 views

Expressing Powers in Terms of Falling Powers

The falling power $n^\underline{k}$ (read $n$ to the falling $k$) is defined as follows: $$n^\underline{k}=n(n-1)(n-2)\cdots(n-k+1)$$ These are important in discrete calculus because their finite ...
6
votes
1answer
313 views

Recurrence relation satisfied by $\lfloor(1+\sqrt{5})^n\rfloor$

Let $L(n)=\lfloor(1+\sqrt{5})^n\rfloor$. What kind of a linear recurrence is satisfied by $L(n)$? I have no idea how to go about this, because of the presence of the greatest integer function. ...
6
votes
1answer
242 views

Prove that there's no fractions that can't be written in lowest term with Well Ordering Principle

This is from Class Note from 6.042 ocw courses at MIT: "Well Ordering Principle" section: ( Sorry for not posting latex; I have less than 10 reputations to post images ) You can read the original ...
6
votes
2answers
418 views

Elementary bound of binomial coefficient

I'm working my way through an Erdős paper from the sixties and some of the elementary bounds he claims seem to be just beyond my reach. The expression looks horrendous but maybe there is a clever ...
6
votes
1answer
31 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
6
votes
1answer
167 views

eHarmony combinatoric question, probability that I should get at least 1 compatible match. [closed]

Ok.. (as I type this with a smirk on my face) - in all seriousness I am trying to figure out, given 29 degrees of compatibility and 40 million members if I should be getting at least 1 match a day. ...
6
votes
1answer
452 views

Find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$

I'm asked in this exercise to find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$. What I have so far: We could write $x$(1 9 7 10 12 2 5)(3 6 8)=(1 9 7 10 12 ...
6
votes
1answer
225 views

Recursion relation of fourth order Runge-Kutta method applied on system

I'm trying to apply the Gauss-Legendre method of fourth order (as Runge-Kutta method) on the following system of equations $$\left\{ \begin{matrix} \dot{a} =& -b \\ ...
6
votes
1answer
59 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
6
votes
1answer
49 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
6
votes
1answer
357 views

A little fun with tournaments (graphs).

Assume $G$ is a tournament, i.e. a (finite) directed graph such that between any two vertices, $a$ and $b$, there is at least one edge in one of the two directions, $a\rightarrow b$ or $b\rightarrow ...
6
votes
1answer
205 views

Solve $\sum_{i=0}^k \binom{n}{i} = u$.

I would like to get as tight bounds as possible for $k$ from $\sum_{i=0}^k \binom{n}{i} =u $. In other words, the number of terms in the sum neeeded to get to $u$. We can assume that both $n$ and $u$ ...
6
votes
2answers
161 views

A function over the integers and its fixed points

Define $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows, $f(n)$ is the number of times the digit "1" is needed if we were to write all integers between 1 and $n$ (inclusive) in base 10. So for example ...
6
votes
1answer
400 views

In any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it : a+b=c

I need to prove, that in any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it, one of which is the sum of two others. Can anyone ...
6
votes
1answer
417 views

What is the expression for putting $n$ indistinguishable balls into $k$ indistinguishable cells?

I'm looking for the expressions for the number of ways in which $n$ indistinguishable balls can be placed into $k$ indistinguishable cells, with No cell being empty Some cells being empty I knew ...
6
votes
1answer
814 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
5
votes
9answers
636 views

How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$?

everybody, how can I prove that, for natural $m$ and $n$, $$ \left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor \; ? $$ Thanks a lot.
5
votes
3answers
279 views

Given 50 holes, what's the chance 2 balls fall into same hole

In a game, a ball can fall any of $50$ holes evenly spaced around a wheel. The chance that a ball falls into any particular hole is $\dfrac 1{50}.$ What is the chance $2$ balls circling the wheel at ...
5
votes
2answers
385 views

Predicate logic: “Everybody knows somebody who knows Alice”

I'm stuck on an undergraduate CS exercise: I am to translate "Everybody knows somebody who knows Alice" into predicate logic. I'm having trouble bending my head around it (being a complete beginner), ...
5
votes
4answers
253 views

Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of ...
5
votes
3answers
4k 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?
5
votes
4answers
368 views

Give a combinatorial argument

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$ Not quite where to starting proving this ...
5
votes
6answers
942 views

Quantifiers, predicates, logical equivalence

I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. I don't think they are but how will I prove it? Am I supposed to use ...
5
votes
3answers
834 views

How is “Some computer science majors take discrete math” not an implication?

"Some computer science majors take discrete math" S is the domain of all college students C(x) means "x is a computer science major" D(x) means "x takes discrete math" Can someone please explain why ...
5
votes
2answers
6k views

Strong Mathematical Induction: Why More than One Base Case?

I am trying to understand this example of strong induction. I know normal induction. In normal induction, if base case is true then we assume some number $n$ to be true. Afterwards, we prove $n+1$ is ...
5
votes
3answers
1k views

Domain, codomain, and range

This question isn't typically associated with the level of math that I'm about to talk about, but I'm asking it because I'm also doing a separate math class where these terms are relevant. I just want ...
5
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
5
votes
2answers
279 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
5
votes
5answers
4k 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 ...
5
votes
3answers
325 views

Is “$n$ is an integer and $\frac{n}{n+1}$ is an integer” true or false?

I am working through a suggested exercise "If $n$ is an integer, $\frac{n}{n+1}$ is not an integer" - I can prove this is false, and I can prove the converse is false, and I can prove the ...
5
votes
4answers
2k views

what are the applications of the isomorphic graphs?

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after ...
5
votes
4answers
105 views

How to prove that if $2x^2-x=2y^2-y$, then $x=y$, for $x,y\in\mathbb{Z}.$

How to prove that if $2x^2-x=2y^2-y$, then $x=y$, for $x,y\in\mathbb{Z}.$
5
votes
5answers
147 views

Help understanding $x=y\Rightarrow(x=z\Rightarrow y=z)$

I was reading a proof that opened with the integer axiom of $x=y\Rightarrow(x=z\Rightarrow y=z)$ What would be an accurate statement in English to express this? The "implies" within the first ...
5
votes
3answers
364 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
5
votes
4answers
374 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...
5
votes
3answers
265 views

Generating Functions- Closed form of a sequence

We are given the following generating function : $$G(x)=\frac{x}{1+x+x^2}$$ The question is to provide a closed formula for the sequence it determines. I have no idea where to start. The denominator ...
5
votes
2answers
983 views

Showing there are no integer solution to equation $\;2^x = 4y+3$

I am stuck on this problem and I'm not sure how to approach it. Can anyone help me out with figuring how to approach the proof? My task is to: Prove that it is impossible to find integers $\,x,\, ...
5
votes
3answers
178 views

Comparison of 2 sets and the '+' operator in set theory

I would like clarification on a set theory question I have. The question reads: Suppose $X$, $Y$ and $Z$ are sets: Does $X \times (Y +Z)=(X\times Y)+(X\times Z)$ (Where $\times$ is the cartesian ...
5
votes
1answer
189 views

How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?

I am trying to solve the recurrence: $$ a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}} $$ but here is a problem for me. After few steps I have this: $$ a_n^2 = a_{n-1}\cdot a_{n-2} $$ and I don't now what to do ...
5
votes
4answers
215 views

How would you solve this recurrence equation: $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$

How would you solve $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$ ? I don't understand the text in my textbook. I Would like somebody to explain it to me.
5
votes
3answers
795 views

Analysis of Algorithms: Solving Recursion equations-$T(n)=3T(n-2)+9$

I need your help with solving this recursion equation: $T(n)=3T(n-2)+9$. with the initial condition : $T(1)=T(2)=1$. I need to find $T(n)$, the complexity of the algorithm which works that way. I ...
5
votes
4answers
650 views

Sum of cubes proof [duplicate]

Prove that for any natural number n the following equality holds: $$ (1+2+ \ldots + n)^2 = 1^3 + 2^3 + \ldots + n^3 $$ I think it has something to do with induction?
5
votes
2answers
329 views

Showing one set is a subset of another

Let's say you have sets $A,\, B,$ and $C.$ How would you show that $[(A-B) - C]\subseteq (A-C)$ using a venn diagram or logical translations? How can this even be done when you don't know the ...
5
votes
2answers
523 views

A wheel has the numbers 1 to 25 randomly placed on it. Show that there are three adjacent numbers whose sum is at least 39.

Any thoughts on understanding how to do this using the Principle of Mathematical Induction would be great. A wheel of fortune has the integers from 1 to 25 placed on it in a random manner. Show that ...
5
votes
1answer
227 views

Pigeon Hole Problem

Prove that of any 100 different twelve digit numbers (first digit cannot be zero) there are two of them with the same first and fifth digit. I'm new to this principle and need some assistance. I've ...
5
votes
2answers
480 views

Proof that no polynomial with integer coefficients can only produce primes

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
5
votes
3answers
216 views

Interesting tea-time problem

Problem A: Please fill each blank with a number such that all the statements are true: 0 appears in all these statements $____$ time(s) 1 appears in all these statements $____$ time(s) 2 appears in ...
5
votes
1answer
279 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
5
votes
3answers
786 views

Could someone please explain to me how (p ∨ q) = (p NAND p) NAND (q NAND q)

I can prove it all the way to: What is the proof for those two equaling? So far I have: (p ∨ q) = (p ^ p) ∨ (q ^ q) Negate it… ~((p ^ p) ∨ (q ^ q)) You get… ~(p ^ p) ^ ~(q ^ q) = (p NAND p) ^ ...
5
votes
2answers
3k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...