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
148 views

Why is the function $f(x)=x^3 \pmod{10}$ periodic with this strange property?

I've noticed that the function $f(x)=x^3 \pmod{10}$ is periodic. For example, listing mod(x^3,10) we get: ...
6
votes
5answers
977 views

Inherently discrete concepts

Are there any concepts which are naturally defined only for the integers and so far has resisted any attempts at extension to other fields such as rationals or reals? Does not meet criteria: ...
6
votes
1answer
115 views

A group acting on colourings of a set

Suppose I have a set $L$ with some permutation group $G$ defined upon it, which I think of as a symmetry group. I want to consider the set $F$ of functions $f: L \to C$, for some set $C$. It seems ...
6
votes
3answers
84 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
6
votes
2answers
149 views

Construction of the projective plane over $\mathbb{F}_3$

I have a question about constructing projective plane over $\mathbb{F}_3$. We first establish seven equivalence classes $P= \{ [0,0,1], [0,1,0], [1,0,0], [0,1,1], [1,1,0], [1,0,1], [1,1,1] \}$. ...
6
votes
2answers
469 views

Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges ...
6
votes
3answers
843 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
104 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
240 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
6
votes
1answer
148 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
128 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
1answer
365 views

Prove parity of binomial coefficient

The task is to find the parity of ${2n\choose 2k+1}$ where $n,k\in\mathbb{N}$. How can I do that?
6
votes
2answers
382 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
929 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
105 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
195 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
355 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
340 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
5answers
237 views

Find least possible number of factors

Number $A$ has $24$ factors. Number $A\cdot B$ has $105$ factors. Find least possible number of factors of $B$. I have tried. But there seems to be no general approach.. The answer given is $12$.
6
votes
1answer
254 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
424 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
58 views

Number of ways to pick N numbers from 0,1,…,N-1, with possible duplication, with sum equal 0 mod N

We have the numbers $0,1,2,....,N-1$ in $\mathbb Z_N.$ I want to pick $N$ numbers from these. These are the rules: Duplication may occur We don't care about ordering, $00041$ is equivalent to ...
6
votes
2answers
118 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
177 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
834 views

Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices

I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it ...
6
votes
1answer
490 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
441 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
236 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
370 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
206 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
163 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
416 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
828 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 ...
6
votes
0answers
36 views

Discrete analogue of Green's theorem

Following formula concerning finite differences is in a way a discrete analogue of the fundamental theorem of calculus: $$\sum_{n=a}^b \Delta f(n) = f(b+1) - f(a) $$ We can think about the Green's ...
5
votes
3answers
2k views

Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$

I am quite new to generating functions concept and I am really finding it difficult to know how to approach problems like this. I need to find the sum of $1^3 + 2^3 + 3^3 +\dotsb+ n^3$ using ...
5
votes
3answers
297 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
965 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
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
2answers
400 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
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
4answers
247 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
387 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
870 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
173 views

What is the coefficient of $x^{18}$ in the expansion of $(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}$?

How to approach this type of question in general? How to use binomial theorem? How to use multinomial theorem? Are there any other combinatorial arguments available to solve this type of question? ...
5
votes
4answers
260 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
2answers
457 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. ...