The discrete-mathematics tag has no wiki summary.

**-3**

votes

**0**answers

44 views

### How to approach this type of problem…? [on hold]

If 3(tan A/2 + tan C/2)=2 cot B/2 then prove that the sides a,b and c are in arithmatic progression in the triangle abc.

**-4**

votes

**0**answers

116 views

### If wolfram rule 110 is universal , does it mean it can solve mathematical equations? [closed]

Stephan wolfram states that Rule 110 in Elementary Cellular Automata is computational universal .
Does it mean that it can solve mathematical equations , like the quadritic equations ???
And if it ...

**9**

votes

**0**answers

175 views

### Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...

**0**

votes

**1**answer

106 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**2**

votes

**1**answer

126 views

### Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...

**5**

votes

**1**answer

145 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**2**

votes

**1**answer

104 views

### Recursive sequence of binomial random variables

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...

**3**

votes

**0**answers

100 views

### “Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane.
Here is the setup:
Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...

**3**

votes

**1**answer

112 views

### Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...

**3**

votes

**1**answer

57 views

### Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...

**-4**

votes

**1**answer

130 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**11**

votes

**2**answers

306 views

### The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...

**13**

votes

**2**answers

569 views

### Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n).
The restriction on the first type of bit string is that they must have the same ...

**1**

vote

**1**answer

151 views

### Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set
$$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$.
and
$$ Q_d := [-1,1]^d.$$
I am interest in ...

**1**

vote

**0**answers

58 views

### Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...

**5**

votes

**2**answers

280 views

### Minimum of squared sum minus sum of squares

I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...

**1**

vote

**0**answers

28 views

### Estimates for derivatives of a positive discrete harmonic function

There is the following estimation (Duffin, Discrete potential theory, Theorem 5):
Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...

**2**

votes

**0**answers

39 views

### A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements.
In a well celebrated paper Richard ...

**7**

votes

**1**answer

773 views

### A Question about Palindromic Numbers and System of Arithmetic Progression

Based from Harminc and Sotak's result, www.fq.math.ca/Scanned/36-3/harminc.pdf
We know that under certain condition, an arithmetic progression can contain an infinitely many palindromes.
My question ...

**1**

vote

**0**answers

31 views

### Simplifying closed form for Meta Operator

I was consider the set of linear operators:
$$O_{a,k} = \frac{f(ax^k) - f(x)}{ax^k - x} $$'
Particularly I am looking for the closed forms of the eigenfunctions of this operator, that is the ...

**8**

votes

**7**answers

572 views

### Finite-space dynamical systems

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...

**19**

votes

**5**answers

820 views

### Three-halves-free words (analogous to square-free)

A square-free word
is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any
consecutive sequence of symbols in the string.
For alphabets of two symbols, the longest square-free ...

**2**

votes

**1**answer

110 views

### On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let
$$
Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}.
$$
I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then
$$
...

**0**

votes

**0**answers

20 views

### On the stability analysis of a discrete difference system with multiplicative noise

If we assume that
\begin{equation*}
\rho \{\phi \otimes \phi+\psi \otimes \psi\}<1
\end{equation*}
where $\rho$ denotes the spectral radius, then can we verify the following inequality holds
...

**5**

votes

**1**answer

320 views

### A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set
$$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$
It seems not much is known about the set ...

**9**

votes

**1**answer

151 views

### Optimal shape for stabbing balls in $\mathbb{R}^3$

I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region,
say, within a unit-radius sphere $S$.
I shoot a ray/path through $S$, hoping to ...

**3**

votes

**1**answer

268 views

### Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...

**0**

votes

**1**answer

158 views

### Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.
$A(n):$ # of squares with vertices on the grid.
It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...

**2**

votes

**1**answer

91 views

### Complex lines arrangements from a given wiring diagram

I'm working on some presentation of the fundamental group of the complement of a complex lines arrangement in $\mathbb{C}^{2}.$ In particular, in Arvola's article
"The fundamental group of the ...

**3**

votes

**1**answer

142 views

### Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams.
I also found some relation with matroid theory. ...

**2**

votes

**1**answer

223 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**4**

votes

**1**answer

252 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**13**

votes

**1**answer

383 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**7**

votes

**1**answer

250 views

### Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...

**2**

votes

**1**answer

145 views

### A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$:
$$
(1,2,3,4,5,6,7,8,9,10,11,12) \;.
$$
Cut the deck into $k$ equal-sized pieces, where $k|n$;
e.g., for $k{=}4$, the $12$ cards are partitioned ...

**6**

votes

**0**answers

90 views

### Checking if a multiplication table represents a group [duplicate]

Given an $n \times n$ multiplication table,
can one check if it represents a group in $o(n^3)$ time?
All properties can be checked by mindless try-all possibilities loops:
Whether there is an ...

**7**

votes

**2**answers

431 views

### A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image

I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...

**6**

votes

**1**answer

274 views

### A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless
of the starting $n$.
For example, let $n=69$, and consider this partition:
$$
(8,8,7,7,5,5,5,5,5,4,3,3,2,2)
$$
In ...

**0**

votes

**1**answer

133 views

### Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to:
I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...

**1**

vote

**0**answers

73 views

### Cross-correlation of two functions which are not fixed

I am trying to cross-correlate two functions, but one of which is changing each 'step' of the cross-correlation.
I want to cross-correlate T(f) and ...

**0**

votes

**4**answers

180 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**17**

votes

**1**answer

500 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...

**34**

votes

**6**answers

3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**1**

vote

**0**answers

38 views

### Find a common expression (parameterized by y = 1/2, 1 and 2) uniting three (rational) polynomials in k [closed]

I am seeking a common "simple" expression (preferably/presumably a sum of products of linear factors, or sum of products of low-degree factors) uniting the three polynomials (parameterized by ...

**2**

votes

**1**answer

158 views

### Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...

**1**

vote

**1**answer

182 views

### A square-squareroot integer race sequence involving primes

I wonder what is the expected behavior of this process?
Let
$f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$.
$g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$.
Now iterate as ...

**19**

votes

**2**answers

639 views

### Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability ...

**2**

votes

**1**answer

576 views

### Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...

**8**

votes

**1**answer

358 views

### Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$

$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$
Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to ...

**2**

votes

**1**answer

113 views

### Family of sets with unique subsets

I am given a set $M\subseteq\{1,\dots,n\},\,|M|=m$ and a famliy of $k$-sets ($k<m$) $\mathcal{U}=\{U_1,\dots,U_p\},\,U_{i}\subset M$. For this family, I would like to check one of the following ...