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
3answers
785 views

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
6
votes
1answer
4k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
6
votes
3answers
114 views

Numbering students inequality problem

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new ...
6
votes
2answers
102 views

Show by induction that $2!4!6!…(2n)! \geq ((n+1)!)^n$

Show by induction that $2!4!6!...(2n)! \geq ((n+1)!)^n$ I stuck at $((n+1)!)^n (2(n+1))! \geq ((n+1+1)!)^{n+1}$, but cant progress to next step It will be great in someone can demonstrate how to ...
6
votes
1answer
147 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
6
votes
2answers
127 views

If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

I am trying to solve the following exercise. If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$ Here what I've done. If ...
6
votes
2answers
371 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 ...
6
votes
2answers
925 views

For all integers b, c, and d, if x is rational such that x^2+bx+c=d, then x is an integer

Prove or disprove the following statment: For all integers b, c,and d, if x is a rational number such that $x^2+bx+c=d$, then x is an integer. This is a homework question from the book Discrete ...
6
votes
3answers
103 views

Solve recursive equation $ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$

Solve recursive equation: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$ $f_0 = 0, f_1 = 1$ What I have done so far: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$ I ...
6
votes
2answers
191 views

Sipser Pumping Lemma Clarification

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me. Here is the Definition of Pumping Lemma: If A is a regular ...
6
votes
1answer
353 views

Backwards induction to show that $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

This question is from "Concrete Mathematics", by Knuth. Sometimes it's possible to use induction backwards, proving things from $n$ to $n-1$ instead of vice versa! For example, consider the ...
6
votes
1answer
321 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
248 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
420 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
2answers
113 views

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
6
votes
1answer
168 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
462 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
229 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
50 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
361 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
408 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
422 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
820 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
3answers
282 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
5answers
912 views

Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$.

Prove if $p$ is a prime then $p \,| \binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one.
5
votes
2answers
394 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
255 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
5answers
6k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
5
votes
5answers
215 views

For every positive integer $n, n^2 + 4n + 3$ is not a prime

Prove: For every positive integer $n, n^2 + 4n + 3$ is not a prime. I tried to disprove the statement, which I could not using several number examples with constructive proof. However I am not sure ...
5
votes
4answers
380 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
3answers
837 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
2answers
402 views

Vertical bar sign in Discrete mathematics

I am little bit confused about the sign " | ". Some people call it the division sign and some call it "such that". In computer programming, it's known as pipe. ...
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
283 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
369 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
377 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
269 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
994 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
180 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 ...