**0**

votes

**0**answers

64 views

### Usage of multinomial theorem with infinite series

What are the conditions for using the multinomial theorem with infinite series? I have an expression but I don't know if I can use it. The expression is:
$$
\left[\sum_{m=0}^{\infty} \frac{\mu^m ...

**7**

votes

**2**answers

802 views

### Linear independence of the square roots over Q

Does there exist a real number $a$ such that the numbers $\sqrt{n^2 + a^2}$ (for all natural $n$) are linearly independent over the field of rational numbers? It is evident that $a$ cannot be ...

**0**

votes

**0**answers

102 views

### What is the number of connected subgraphs with $n$ vertices of a labelled connected simple graph with $n$ vertices?

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs ...

**3**

votes

**0**answers

105 views

### Kasteleyn, Gessel-Viennot and eigenvalues

The Kasteleyn matrix (for counting perfect matchings) and the Lindström-Gessel-Viennot matrix (for counting families of nonintersecting lattice paths) are tightly related, as observed many times by ...

**6**

votes

**0**answers

295 views

### On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots,
f_k(x) \in \mathbb F_q[x]$ be ...

**4**

votes

**5**answers

389 views

### Lattice points in dilated polytopes and sumsets

Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.
Let $p_1,\dots,p_m$ be all lattice points in $P$.
Question: What is the condition on $P$ that guarantees ...

**10**

votes

**0**answers

98 views

### Does a huge set of random points in the plane almost surely have a checkerboard-triangulation

A set of $n$ points in the plane in generic position (no alignement of three points) has at least $2.012^n$ different triangulations
of its convex hull involving only the set of given points.We call ...

**6**

votes

**1**answer

125 views

### Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
...

**1**

vote

**1**answer

205 views

### Sum of covariance matrix of products of dependent variables

Consider the sequences of random variables $\{X_i\}_{i=1}^n$ and $\{Y_i\}_{i=1}^n$, as well as the corresponding sequence of products, $\{X_i Y_i\}_{i=1}^n$. All $X_i$ share the same mean value, ...

**3**

votes

**0**answers

58 views

### Asymptotics of partitions in at most n parts, bounded by r

I posted this question on MathStackexchange (http://math.stackexchange.com/questions/639878/asymptotics-of-partitions-in-at-most-n-parts-bounded-by-r) some time ago, but it did not receive any answer, ...

**0**

votes

**0**answers

37 views

### Minimize $td-2\sum_{i=0}^{t-1} w_k(i)$ where $w_k(i)$ is the sum of the base-$k$ digits of $i$

Let $K_k^n$ denote the $n$-fold cartesian product of the complete graph on $k$ vertices, and let $[R,T]$ be the edge cut, consisting of the edges between complementary vertex sets $R$ and $T$.
I ...

**1**

vote

**0**answers

46 views

### Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size.
Here is a picture of $K_{6}$ with 5 ...

**3**

votes

**1**answer

50 views

### Are all (non-constant) symmetric submodular functions non-monotone?

I am trying to show (if possible) that symmetric submodular functions are non-monotone (excluding constant sub-modular functions).
Recall that a submodular function $f : 2^{\Omega} \rightarrow R$ is ...

**4**

votes

**2**answers

136 views

### class 1 vs class 2 in regular graphs

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph.
A graph with edge chromatic number equal to ...

**31**

votes

**1**answer

1k views

### Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar ...

**3**

votes

**1**answer

106 views

### Domino Shuffling and Warren's process

In this paper by Nordenstam, it is shown that a certain interlacing particle process that arises from uniformly random Aztec diamond tilings is amazingly similar to Warren's process. One of the ...

**4**

votes

**2**answers

183 views

### Union of Permutations

This is a problem I asked on http://math.stackexchange.com/questions/647382/union-of-permutations. Feel free to close it if you think it below research level.
Having $k$ different permutations, ...

**1**

vote

**0**answers

64 views

### Separating unit disks by circles

This is inspired by the recent question about separating unit disks by lines, which I will refer to as the "line case". Replacing "line" by "circle" adds one degree of freedom, and I'm wondering if ...

**34**

votes

**2**answers

898 views

### Is there an analog of Sperner's lemma for the Hopf invariant?

Recall that Sperner's lemma is essentially a combinatorial version of the topological statement "A map from $S^n$ to $S^n$ with degree one cannot be nullhomotopic."
My question is, does there exist ...

**5**

votes

**1**answer

236 views

### Homomesy in perfect matchings

Assume $n \geq 2$. Let $\mathcal{M}_n$ denote the set of perfect matchings on $[2n] := \{1,\ldots,2n\}$, i.e., the set of partitions of $[2n]$ into pairs. For $M \in \mathcal{M}_n$, and $p = ...

**7**

votes

**1**answer

215 views

### Separating unit disks by lines

Given $n\ge 2$. For a real $d>2$, consider a constellation $C$ of $2n$ disks of radius $1$ in the plane such that $h(C)$, the minimal distance between any two of their centers, is equal to $d$. Let ...

**5**

votes

**3**answers

569 views

### Binomial Identity

I recently noted that
$$\sum_{k=0}^{n/2} \left(-\frac{1}{3}\right)^k\binom{n+k}{k}\binom{2n+1-k}{n+1+k}=3^n$$
Is this a known binomial identity? Any proof or reference?

**4**

votes

**1**answer

175 views

### An intutive reason why a “distance” metric may be a poor one for a procedure where we attempt to modify a string (mutating 0 OR 1 bits)

If I'm attempting to mutate one arbitrarily chosen binary string $s_a$, to another arbitrarily chosen binary string $s_b$, in the smallest number of steps (i.e. with the smallest number of mutations) ...

**21**

votes

**3**answers

533 views

### Number of terms in certain polynomials over $\mathbb{F}_2$

I raised this question in my answer to On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$. Let $s_1,s_3,s_5,\dots$ be indeterminates over the field $\mathbb{F}_2$, and recursively set ...

**1**

vote

**1**answer

154 views

### Natural bijection between sets with coloured elements?

In Andreas Blass's famous paper `Seven Trees in One', the existence of a natural bijection between binary trees and 7-tuples of binary trees is related to the equation $T^7 = T$ being satisfied by a ...

**5**

votes

**0**answers

141 views

### Power sums and Jack symmetric functions

Let $\Lambda$ be the algebra of symmetric functions in infinitely many variables over $\mathbb{C}$.
The $n$-th power sum symmetric function $p_n$ is defined (formally) as
\begin{equation}
p_n=\sum_i ...

**2**

votes

**3**answers

204 views

### Regular graphs whose neighbourhoods induce matchings

Studying some problem I've arrived to the following notion.
Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a ...

**6**

votes

**1**answer

175 views

### The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...

**-9**

votes

**1**answer

173 views

### Combinatorics by complex number [closed]

Compute: $ \binom{n}{o} $- $\binom{n}{2}$+ $\binom{n}{4}$- $\binom{n}{6}$+ $\binom{n}{8}$-...-$\binom{n}{4k-2}$+$\binom{n}{4k}$.

**3**

votes

**1**answer

185 views

### Product of cycles of length $n$

Let $n = 2k$ and suppose that $\sigma$ is a permutation in $S_n$ which is equal to a product of k disjoint cycles of length $2$. In how many ways one can write $\sigma$ as a product of two cycles of ...

**1**

vote

**1**answer

116 views

### Upper-bound for maximal-cliques on perfect graphs

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison ...

**3**

votes

**2**answers

380 views

### summation of products of combinatorials

For any natural number $N$ and $0\le n\le N$ define
$$
f(n) = f(n,N) = \frac{1}{(N+1)!} \sum_{\substack{{S\subset \{1,\ldots,N\}} \\ {|S|=n}}} \prod_{s\in S} s.
$$
(The empty product is interpreted ...

**2**

votes

**0**answers

196 views

### Complete presentations for one-relator semigroups (100\$+100\$ question)

It is an open problem whether word problem for one-relator semigroups is decidable, but it is even unnknown if one-relator semigroups always admit finite complete presentations (i.e. a finite complete ...

**6**

votes

**1**answer

115 views

### Separating infinite words sharing factors by automata

Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...

**1**

vote

**0**answers

128 views

### Asymptotic behaviour of sequence

I am interested in the sequence
$$a(n)=\sum_{k=0}^n {p(n-k)-1 \choose k}$$
where $p(n)=(r-1)n^2+(2r-1)n+r$ for some $r \in \mathbb{N}$ or more generally any polynomial equation.
When $r=1$ this ...

**6**

votes

**0**answers

106 views

### What is the mobius function for the set of simplicial complexes on n vertices?

Consider the set of simplicial complexes on $n$ vertices, with partial ordering by containment. What is the Mobius function for this poset?
Are other combinatorial facts known about it (e.g. the ...

**2**

votes

**0**answers

105 views

### Is there a system of quasigroup equations implying non-associativity?

I have read that if 4 quasigroup operations, $\cdot,\circ,\star,\square$, on a set $S$ respect the following equation:
$$x\cdot (y\circ z) = (x \star y) \square z$$
for all $x,y,z\in S$, then all 4 ...

**4**

votes

**1**answer

143 views

### Can a partition free family in $2^{[n]}$ always be enlarged to one of size $2^{n-1}$?

Let $\left[ n \right]=\{{1,2,\cdots,n\}}$ and call a family $\mathcal{F} \subset 2^{\left[n\right]}$ partition-free if it does not contain any partition of $\left[n\right]$. A recent question asked ...

**1**

vote

**1**answer

112 views

### Partition-free subsets of $2^{[n]}$

Let $[n]$ denote the set of integers $\{1,2,\ldots,n\}$. A subset of $2^{[n]}$ is partition-free if it does not contain a partition of $[n]$.
What is the maximum size of a partition-free subset of ...

**0**

votes

**0**answers

65 views

### Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...

**8**

votes

**3**answers

339 views

### colorings of ${\mathbb Z}^d$ with constraints

For a lattice $\mathbb Z^d$, denote by lattice line any line that contains two (and thus infinitely many) lattice points.
For $2\le k<n$, define a $(n,k)$-coloring, or $C_d(n,k)$ for short, ...

**10**

votes

**2**answers

483 views

### A binomial determinant fomula

Is there an existing or elementary proof of the determinant identity
$
\det_{1\le i,j\le n}\left( \binom{i}{2j}+ \binom{-i}{2j}\right)=1
$?

**3**

votes

**1**answer

169 views

### Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs.
Conversion from a Hadamard Matrix into a Hadamard Graph
An $n$-Hadamard graph $G$ ...

**3**

votes

**0**answers

198 views

### How many combinations does Android pattern have? [closed]

Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.

**24**

votes

**2**answers

841 views

### A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture:
Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...

**1**

vote

**1**answer

187 views

### Groups with no small generating set

Is there a classification of groups having the property that any set of $d$ elements (say including the identity) is contained in a proper subgroup?
It is appealing to call the maximum such integer ...

**6**

votes

**1**answer

228 views

### Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...

**5**

votes

**1**answer

69 views

### Generalising the adherence operator and its closure properties with regard to regular (rational) languages

Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some ...

**1**

vote

**1**answer

228 views

### A problem on counting k-subsets of {-n,-n+1,…,n-1,n} satisfying that sum of elements equal to 0

I'll use another way to give the question besides the title.
Define
$$ A_k(n) = \frac{1}{2 \pi \mathrm{i}} \int_{|q|=1} \left( \frac{1}{2 \pi \mathrm{i}}\int_{|z|=1}\prod_{j=-n}^{n}(1+qz^j) ...

**1**

vote

**1**answer

147 views

### Associative binary operations defined on a finite set

We can easily test the commutativity of a binary operation on a set of $\ n\in\mathbb{N}\ $ elements by observing the symmetry of the $\ n\times n\ $ multiplication table.
I was looking for a ...