# Tagged Questions

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.

1k views

### Notation Question: What does $\vdash$ mean in logic?

In a "math structures" class at the community college I'm attending (uses the book Discrete Math by Epp, and is basically a discrete math "light" edition), we've been covering some basic logic. I've ...
6k views

### Why a complete graph has $\frac{n(n-1)}{2}$ edges?

I'm studying graphs in algorithm and complexity, (but I'm not very good at math) as in title: Why a complete graph has $\frac{n(n-1)}{2}$ edges? And how this is related with combinatorics?
431 views

### How, if at all, does pure mathematics benefit from $2^{74207281}-1$ being prime?

So a couple of days ago the $17$ million digit number $2^{57885161}-1$ was beaten by the $22$ million digit number $2^{74207281}-1$ at being the largest known prime number. Are there any specific (...
2k views

### True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
406 views

### Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
2k views

### Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
95 views

### Find all $A\subseteq\mathbb{N}$ such that $A=\{|a-b|:a,b\in A\}$.

For a set $A$ of real numbers, denote $$A^\ast:=\{|a-b|:a,b\in A\}.$$ Question: Find all finite subsets $A\subseteq\mathbb{N}$ of the natural numbers such that $$A^*=A.$$ Attempt: The empty ...
1k views

### How many different shapes can I make with this toy?

I have the following toy, perhaps some of you have seen it before. It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this: Or this: ...
2k views

662 views

### Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
2k views

### 9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
430 views

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
275 views

### Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
341 views

### Do any of these sequences have infinitely-many distinct iterates under run-length substitution?

Let $$S = \{x \in \{1,2\}^\mathbb{N}: \ \text{every run in }x\text{ has finite length}\}$$ and define $$T: S\to \mathbb{N}^\mathbb{N}$$ such that for any $x\in S$, ${T}x$ is the sequence of run-...
### $1^2+2^2+\cdots+24^2=70^2$ and squarily squaring the torus
The unique nontrivial solution to $1^2+2^2+\cdots+n^2=m^2$ is $(n,m)=(24,70)$. (This fact has connections to modular forms, special functions, lattices and string theory.) Martin Gardner, in the ...