The tag has no wiki summary.

learn more… | top users | synonyms

21
votes
5answers
850 views

Sequences with integral means

Let $S(n)$ be the sequence whose first element is $n$, and from then onward, the next element is the smallest natural number ${\ge}1$ that ensures that the mean of all the numbers in the sequence is ...
19
votes
1answer
272 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 ...
1
vote
1answer
306 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$ ...
1
vote
1answer
72 views

the “compact good array” in a “good $N^+$-cycle”

We use $N^+$ to denote the set of positive integers.For any finite array $A:(a_1,b_1),...,(a_k,b_k)$,where every $(a_i,b_i)\in N^+\times N^+$,we call $A$ is good if for every $i\in ...
6
votes
3answers
395 views

Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
1
vote
1answer
295 views

Indexing combinations with repetition

Let $\Sigma$ be a finite set of symbols with total order. Let $C_k$ be the set of all $k$-multiset (unordered collection of $k$ elements from $S$, with repetition allowed). We can order all the ...
1
vote
1answer
107 views

Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$. I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...
3
votes
1answer
110 views

Obtaining each set (hyperedge) in a set system (hypergraph) as a union of sets in a smaller set sytem

Let $V$ be a set and $E$ a set of subsets of $V$. I'd like to know the proper terminology for the following concept. Let me call it "generator". A generator is a set $F$ of subsets of $V$ such that ...
3
votes
1answer
155 views

Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
0
votes
0answers
141 views

Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and ...
1
vote
1answer
715 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 ...
3
votes
2answers
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 ...
6
votes
1answer
691 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 ...
1
vote
1answer
164 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 ...
2
votes
1answer
229 views

On solution of a class of discrete-time Lyapunov equation

Hello members, let's consider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment ...
2
votes
1answer
131 views

On solution of a discrete-time equation

Hello, members. I have a problem for the following problem when I derive an optimization algorithm for stochastic singular systems $$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$ where ...
1
vote
1answer
318 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 ...
6
votes
3answers
730 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 ...
3
votes
0answers
123 views

Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...
13
votes
1answer
459 views

Does erosion mix faster than a riffle shuffle?

It is a famous result of Aldous and Diaconis1 that seven shuffles are necessary and suffice to approximately randomize 52 cards.2 Here the shuffles are the standard riffle shuffle, where the ...
0
votes
0answers
131 views

A good upper bound on the size of k-biclique in random bipartite graphs.

Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...
0
votes
1answer
125 views

expected size of unbalanced biclique in random bipartite graph

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine what's an upper bound on the size of the largest biclique in random ...
3
votes
1answer
146 views

what's an upper bound on the size of the largest biclique in random bipartite graph?

I am not an expert in random graph but I need the following result and I couldn't find any reference on this. Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ ...
4
votes
2answers
397 views

Looking for construction related to Erdos-Szekeres theorem

The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is $p(i_1) < ...
4
votes
1answer
264 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 ...
24
votes
5answers
2k 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 ...
1
vote
3answers
385 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 ...
5
votes
0answers
479 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 ...
3
votes
2answers
348 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 ...
15
votes
5answers
2k 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 ...
6
votes
1answer
538 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 ...
8
votes
2answers
481 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\}$ ...
6
votes
3answers
526 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 ...
5
votes
0answers
733 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" ...
10
votes
12answers
990 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 ...
9
votes
5answers
513 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 ...
5
votes
2answers
265 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 ...
7
votes
6answers
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 ...
5
votes
1answer
685 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 ...
-1
votes
1answer
312 views

Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$? The answer is: ...
1
vote
1answer
129 views

expanding the sqare of sum

If there any way to expand the following? $$\left(\sum_{i=1}^nx_i\right)^{\frac{1}{2}}$$ and more generally, a way to expand $$\left(\sum_{i=1}^nx_i\right)^{\frac{p}{q}}$$ where $gcd(p,q) = 1$ ...
3
votes
2answers
346 views

anyone help me with this inequality

I'm have some difficulties in bounding the following inequality: I want to find a c as small as possible s.t. $$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...
0
votes
0answers
85 views

An upperbound related to inductively reducing a set by adding the two least elements

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:) Let ...
1
vote
1answer
324 views

Simple and general relation between continuant polynomials

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 ) ...
12
votes
5answers
2k views

Special arithmetic progressions involving perfect squares

Some time ago the following rather easy problem appeared in an online publication called "Problems in Elementary NT" by Hojoo Lee: Prove that there are infinitely many positive integers $a$, $b$, $c$ ...
8
votes
1answer
369 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 ...
1
vote
0answers
210 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 ...
3
votes
2answers
216 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 ...
0
votes
0answers
204 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: ...
3
votes
0answers
116 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) & ...