# Tagged Questions

Do NOT use this tag; instead you might use co.combinatorics or various more specific tags.

332 views

### Hidden points in polygons

Let $h(n)$ be the largest number of mutually invisible points that can be located in a polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment $xy$ contains a point ...
320 views

### a conjecture about a specific subset of $S_n$

Let $n>3$ be a positive integer.We denote the symmetric group of $n$ elements by $S_n$ and the identity mapping by $id$. For every $f\in S_n$, $f(1,2,\ldots,n)=(a_1,a_2,\ldots,a_n)$, denote $a_n$ ...
74 views

1k views

### Graph Theory and Subgraphs [closed]

Let T = (V , E) be a tree with |V | = n ≥ 2. How many distinct paths are there (as sub graphs) in T? I already have the answer to this question as (n/2). The problem that I'm having is finding ...
174 views

### Question on weights and minimal degree

Edit: question has been changed from 'lexicographic' (cf. "D K"'s answer below) to 'degree' minimality. Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k> 3$. Consider the set $M$ of all ...
903 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it. There should be an easy argument, but I have not yet found it. Informal version An integer $k\geq 2$ is fixed. We are given a matrix (...
169 views

### How to determine the number of a cube within a bigger cube?

Hi all, I have a cube, sized 39 x 13 x 8. I need to find out how many of them can fit in a cube of 100 x 100 x 100. I need to find the highest number possible. Do you know of a way to do that ...
284 views

418 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...
981 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...
129 views

339 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...
3k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each be ...
441 views

### How do quantifiers limit scope?

I'm teaching a discrete math class at the high school level and realize that I'm fuzzier on a topic than I should be. In their last problem set, I asked my students to translate "There is a triangle ...
559 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
350 views

### The cycle structure of twisted wires, connected

Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$, connected to a remote junction box $B$, where the wires are now arrayed along a line in a randomly permuted order, i.e., each ...
3k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating. It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...
564 views

### Calculating a specific joint probability involving sums of binomial distributions

The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...
503 views

### Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$ ...
563 views

### Cylinders dividing $\mathbb{R}^{3}$

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$. For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...
845 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
1k views

### Continuous notions with compelling discrete analogues

Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not ...
551 views

### Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question, "Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$. View an $n \times n \times n$ cube $C_3(n)$ as ...
288 views

### Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$. Define a blocking set for a lattice cube to be a set of points in ...
2k views

### Discrete Mathematics textbooks for undergraduates

For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students. I intend to focus on practical applications. I would be grateful if ...
819 views

### Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
334 views

Continued fraction $[a_0,a_1,...,a_n]$ may be expressed as quotient of two polynomials of $(a_0,a_1,...,a_n)$, named continuants (see http://en.wikipedia.org/wiki/Continuant_%28mathematics%29 ) $[a_0,... 7answers 2k views ### Special arithmetic progressions involving perfect squares Prove that there are infinitely many positive integers$a$,$b$,$c$that are consecutive terms of an arithmetic progression and also satisfy the condition that$ab+1$,$bc+1$,$ca+1$are all perfect ... 1answer 376 views ### Die-rolling Hamiltonian cycles Let$R$be a rectangular region of the integer lattice$\mathbb{Z}^2$, each of whose unit squares is labeled with a number in$\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled$R$is die-... 0answers 212 views ### Trigonometric semialgebraic conditions for two floors to be unequal [edited] EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for$\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$which is trigonometric ... 2answers 222 views ### Designing a tree to match a distribution I want to design a tree to approximate a given sequence of numbers, in the following sense. Let$X=(x_1,\ldots,x_n)$be$n$numbers, with$0 < x_i \le 1$and$\sum_i x_1 = 1$. For a rooted tree$T$,... 0answers 241 views ### Partial Recurrence Equation Hey people I have the following equation, which I don't manage to solve. The background of the problem is the clustergrowth of two chemical species, resulting in a final relation I'd like to solve: ... 0answers 126 views ### Are there existing resources on modular-esque recurrence relations? Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?$\begin{align*} f_{n,k}(x) & =a(x)f_{n-1,k}(x)+b(x)f_{n-2,k}(...
The problem is as follows. Given a set $S$ of natural numbers of size $n$ where each $x_i \in S$ is from the set $[n^2]$. Elements of $S$ are not necessarily pairwise different, i.e., there can be ...