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

8
votes
2answers
391 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in ...
8
votes
2answers
11k views

Correct way to calculate numeric derivative in discrete time?

Given a set of discrete measurements in time $x_t, t \in \{0,\Delta t, 2\Delta t,\ldots,T-\Delta t,T\}$, what is the correct way to compute the discrete derivative $\dot x_t$. Is it more correct to ...
8
votes
3answers
6k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is ...
8
votes
3answers
970 views

Cardinality of a discrete subset

If I am correct, a discrete subset of a topological space is defined to be a subset consisting of isolated points only. This is actually equivalent to that the subspace topology on the subset is ...
8
votes
1answer
11k views

What is the prerequisite knowledge for learning discrete math?

To become a better computer programmer I would like to take the time to learn discrete mathematics, but I am positive that I do not have the required existing knowledge to do so. So I would like to ...
8
votes
3answers
4k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
8
votes
2answers
158 views

Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$ $$a_0=1, a_1=-\frac{1}{2}$$ Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$? I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ ...
8
votes
2answers
227 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
8
votes
2answers
507 views

Symbolic coordinates for a hyperbolic grid?

Rephrasing     (one year later)    (original question is below) Apparently the original question wasn't clear, or nobody knows an answer (or both). So I will try to rephrase it. Look at your ...
8
votes
3answers
166 views

Number of $n^2\times n^2$ permutation matrices with a 1 in each $n\times n$ subgrid

I found the following question in a paper I was trying to solve: The following figure shows a $3^2 \times 3^2$ grid divided into $3^2$ subgrids of size $3 \times 3$. This grid has $81$ cells, $9$ in ...
8
votes
1answer
13k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
8
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
8
votes
2answers
398 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
8
votes
2answers
305 views

Solve a summation

Hi guys I have an exercise I don't know how to approach, would be cool if you could give me a tip or two! A sequence $a_{n}$ is defined by a dependency : $$ \sum_{i, j, k \geq 0}^{i+j+k = n } ...
8
votes
1answer
396 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
8
votes
5answers
164 views

convert ceil to floor

Mathematically, why is this true? $$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$ Assume $a$ and $b$ are positive integers. Is this also true if $a$ and $b$ are ...
8
votes
2answers
159 views

What is the subword complexity function of this infinite word?

Let $w_{0}$ denote the finite word $01$ in the free monoid $\{ 0, 1 \}^{\ast}$, and for $i \in \mathbb{N}$ define $w_{i}$ as the word obtained by adjoining the first $\left\lfloor ...
8
votes
2answers
208 views

What is the right way to define a function?

Most authors define functions this way: Given the sets $A$ and $B$. A relation is a subset of $A\times B$. Then given a relation $R$, we define $Dom_R=\{x|(x,y)\in R\}$ and $Img_R=\{x|(y,x)\in R\}$. ...
8
votes
1answer
83 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of ...
8
votes
2answers
245 views

Counting number of distinct systems

This is an enumeration problem in conjunction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
8
votes
1answer
512 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 ...
8
votes
1answer
164 views

$n \times n$ lattice graph with partial derivatives bounded by $1$ has $n$ equal values.

I once proved this question many years ago but now I have completely forgotten how I did it. I remember it being a fun problem and wouldn't mind seeing a proof again, with the likelihood of it being ...
8
votes
2answers
905 views

Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
8
votes
1answer
142 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
8
votes
1answer
219 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is ...
8
votes
1answer
560 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
1answer
532 views

Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?

What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$. Clearly $r_{1}=2$. But ...
8
votes
2answers
169 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
7
votes
4answers
3k views

There are 31 houses on north street numbered from 1 to 57. Show at least two of them have consecutive numbers.

I thought to use the pigeon hole principle but besides that not sure how to solve.
7
votes
8answers
3k 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.
7
votes
6answers
2k views

Number of 6-digit passwords, starting with even or ending with odd digit

My problem is A password consists of six digits, each in $\{0,\ldots,9\}$ How many passwords start with an even digit or end with an odd digit? the answer is $750,000.$ I would like to know ...
7
votes
9answers
8k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
7
votes
9answers
734 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.
7
votes
3answers
7k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
4answers
9k views

Prove the cuberoot of 2 is irrational

I need to prove the cube root is irrational. I followed the proof for the square root of $2$ but I ran into a problem I wasn't sure of. Here are my steps: By contradiction, say $ \sqrt[3]{2}$ is ...
7
votes
6answers
136 views

How am I supposed to know that $\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } \binom{n+1}{n}x^n$?

I'm currently reading through the solution to a problem that involves finding generating functions. In some of the intermediary steps, it is written that $$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } ...
7
votes
3answers
15k 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?
7
votes
3answers
4k views

Counting zero-digits between 1 and 1 million

I just remembered a problem I read years ago but never found an answer: Find how many 0-digits exist in natural numbers between 1 and 1 million. I am a programmer, so a quick brute-force would ...
7
votes
5answers
185 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
7
votes
5answers
643 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
7
votes
2answers
229 views

Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

I need help to prove that the quantity of this division : $\dfrac{({10!})!}{{10!}^{9!}}$ is an integer number, using combinatorial proof
7
votes
4answers
283 views

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's ...
7
votes
3answers
1k views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...
7
votes
6answers
3k 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 ...
7
votes
5answers
1k views

discrete math book suitable for younger person?

When I took discrete math as an adult I realized that this was a subject I would have enjoyed and done well at much earlier in life, even in my early teens. Does anyone know if there are good books, ...
7
votes
3answers
250 views

Closed form for a binomial series

I am wondering if any knows how to compute a closed form for the following two series. $$\sum_{m=1}^{n}\frac{(-1)^m}{m^2}\binom{2n}{n+m}$$ $$\sum_{m=1}^{n}\frac{(-1)^m}{m^4}\binom{2n}{n+m}$$ ...
7
votes
4answers
747 views

Closed-form expressions for sums

I've got a problem with deducing closed-form expressions for sums: $1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ $2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$ Can anyone help me? ...
7
votes
1answer
1k views

Mathematical explanation for the Repertoire Method

There are a few questions already about this method, which has stumped me for a long while. The process is explained, for instance, here: Repertoire Method Clarification Required ( Concrete ...
7
votes
1answer
342 views

Spectrum of a real number

Whilst reading Concrete Mathematics, the authors mention something which they refer to as the "spectrum" of a real number (pg. 77): We define the spectrum of a real number $\alpha$ to be an ...
7
votes
5answers
4k views

If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese) A plane is divided by many lines. Show that it is possible to color the regions formed with only two ...