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

10
votes
4answers
9k views

How would I figure out how many anagrams of mississippi don't contain the word psi?

I'm really confused how I'd calculate this. I know it's the number of permutations of mississippi minus the number of permutations that contain psi, but considering there's repetitions of those ...
10
votes
3answers
430 views

bijection = bijection + bijection on symmetric integer intervals

Given a bijection $f:\mathbb Z \to \mathbb Z$ where $\mathbb Z$ is the set of all integers, does there always exist two bijections $g:\mathbb Z \to \mathbb Z$ and $h:\mathbb Z \to \mathbb Z$ which ...
10
votes
1answer
126 views

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
10
votes
1answer
529 views

outer automorphisms of $S_6$

$$ \begin{array}{|l|c|c|} \hline \text{cycle structure} & \text{number of permutations} & \text{order} \\ \hline 6 & 120 & 6 \\ 5+1 & 144 & 5 \\ 4+2 & 90 & 4 \\ ...
10
votes
2answers
173 views

Determine Fastest 3 horses out of 125 when only 5 racing track are given without using stopwatch?

We have 125 horses, and we want to pick the fastest 3 horses out of those 125. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races ...
10
votes
1answer
102 views

Examples of classes $\mathcal{C}$ of structures such that every finite group is isomorphic to the automorphism group of a structure in $\mathcal{C}$

Since it is not the case that every group is the automorphism group of a group (see Is every group the automorphism group of a group?), it is natural to ask: what are some examples of classes $\...
10
votes
1answer
226 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a &...
10
votes
2answers
245 views

Counting sets by their connectedness

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
10
votes
1answer
177 views

$(123)!$ divided by $(25!)^x$. What is the maximum possible integral value of $x$?

The answer given is $5$. But I am getting $4$. Here is what I have done. $$25!= 2^{22}\cdot3^{10}\cdot5^6\cdot7^3\cdot11^2\cdot13\cdot17\cdot19\cdot23$$ $$123!=2^{117}\cdot3^{59}\cdot5^{28}\cdot7^{19}...
10
votes
1answer
217 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
10
votes
0answers
177 views

A group acting on functions of functions of functions

Given a group acting on a set $X$, there is a standard way to define an action of the group on the set of functions of $X$. This can be extended to the set of functions of functions of $X$ as I show ...
9
votes
4answers
24k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^{|a|}$ ...
9
votes
3answers
33k 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 ...
9
votes
3answers
803 views

How to prove indirectly that if $42^n - 1$ is prime then n is odd?

I'm struggling to prove the following statement: If $42^n - 1$ is prime, then $n$ must be odd. I'm trying to prove this indirectly, via the equivalent contrapositive statement, i.e. that if $n$ ...
9
votes
3answers
449 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
9
votes
2answers
5k 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 $q$...
9
votes
3answers
793 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
9
votes
2answers
3k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
9
votes
4answers
2k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in the ...
9
votes
2answers
3k views

Minimum degree of a graph and existence of perfect matching

I was reading a result where the following proposition appears as a preliminary step (and left as exercise): Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with ...
9
votes
2answers
225 views

How find that $\left(\frac{x}{1-x^2}+\frac{3x^3}{1-x^6}+\frac{5x^5}{1-x^{10}}+\frac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$

let $$\left(\dfrac{x}{1-x^2}+\dfrac{3x^3}{1-x^6}+\dfrac{5x^5}{1-x^{10}}+\dfrac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$$ How find the $a_{2^n}=?$ my idea:let $$\dfrac{nx^n}{1-x^{...
9
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 ...
9
votes
2answers
14k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
9
votes
4answers
547 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
9
votes
1answer
223 views

How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even ...
9
votes
2answers
511 views

A modified NIM game

Let's play a game of NIM, but with a catch! We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different. We move in turns. In every move, we can select a pile and ...
9
votes
1answer
534 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 ...
9
votes
2answers
948 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 ...
9
votes
1answer
149 views

How and what to teach on a first year elementary number theory course?

In the late 80’s and early 90’s there was the idea of ‘calculus reform’ and some emphasis and syllabus changed. The order of doing things in calculus also changed with the advantage of technology. ...
9
votes
1answer
342 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
9
votes
1answer
117 views

$\{1, 2, . . . , 49\}$ is partitioned into $3$ subsets. Prove that at least $1$ of them contains $3$ different numbers $a,b,c$ such that $a+b=c$

As the title says, I'm asked to prove that at least one of the subsets contains three different numbers $a, b$ and c such that $a + b = c$. I tried to prove it but it is more difficult than it ...
9
votes
1answer
772 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where $$f_l(\...
9
votes
1answer
259 views

Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers

In our discrete mathematics exercises I came of with the question: Prove that the coefficients of $\prod_{n\geq2}{(1-x^{F_n})}=1-x-x^2+x^4+x^7+\dots$ can only be $-1,1$ or $0$, where $F_n$ ...
9
votes
1answer
317 views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. $2$-...
9
votes
1answer
162 views

Interesting shapes using probability and discrete view of a problem

Suppose we have a circle of radius $r$, we show the distance between a point and the center of the circle by $d$. We then choose each point inside the circle with probability $\frac{d}{r}$ , and turn ...
9
votes
1answer
209 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
9
votes
1answer
159 views

Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)

I know that $$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$ Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
9
votes
2answers
134 views

Why isn't finite calculus more popular?

I'm reading through Concrete Math, and learning about finite calculus. I've never heard of it anywhere else, and a Google search found very few relevant sources. It seems to me an incredibly powerful ...
8
votes
9answers
1k views

prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

I'm having some trouble with this question and can't really get how to prove this.. I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$. I have tried doing $\dfrac{m}{3}=n$ and ...
8
votes
6answers
1k views

If $xy$ and $x+y$ are both even integers (with $x,y$ integers), then $x$ and $y$ are both even integers

The title statement can be proven using the contrapositive, note that $x$ odd or $y$ odd means that at least one of $x\cdot y,x+y$ is odd. Is there a way to prove the statement directly? To ...
8
votes
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: $$...
8
votes
4answers
2k views

Coin problem with $6$ and $10$

I am doing a coin problem where: In a city where you only have denominations in $6$ and $10$. What is the largest value that this city cannot pay? In another problem that my teacher showed me, ...
8
votes
3answers
1k views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
8
votes
3answers
5k views

The number of ways to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
8
votes
2answers
276 views

How does $2^{k+1} = 2 \times 2^k$?

I ask only because my textbook infers this in an example. Where should I go to learn more about this? I'm trying to learn mathematics by Induction but my knowledge of simplifying algebraic equations ...
8
votes
2answers
530 views

Is the given relation transitive?

Consider the relation: $$R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}$$ on the set $A = \{a,b,c\}$. Is $R$ transitive? I said no because $$[(c, c) \wedge (a, c)] \Longrightarrow (c,a)$$ is a ...
8
votes
4answers
196 views

Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting $$f_0(x) = \frac{1}{...
8
votes
5answers
245 views

How to distinguish between combination and permutation questions?

How do you distinguish combination and permutation question? An example of a combination question: Example: How many different committees of 4 students can be chosen from a group of 15? ...
8
votes
4answers
303 views

“How many different integers does this give us?”

How many unique integers can you get from $\lceil2012/n\rceil$ where $n$ is a positive integer? I don't know at all where to begin to approach this problem. I thought it maybe had something to do ...
8
votes
1answer
937 views

Puzzle: Give an algorithm for finding a frog that jumps along the number line

You are playing a game, your goal in this game is to catch a frog that's leaping between natural numbers. At first, the frog is found at the number $a \in \mathbb N$ which is not known to you. Each ...