Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
9,275
questions
1
vote
0
answers
119
views
Number of solutions to a diophantine equation
Given a positive integer $n$, consider the diophantine equation $4x^2+y^2+4x+y=2n$ with solutions in non-negative integers $x$ and $y$.
Define the proportion
$$\delta_n=\frac{\#\{(x,y)\in\mathbb{Z}^2_{...
- 38.3k
3
votes
1
answer
68
views
Property of the spanning tree with minimal leaves
Let $G$ be a connected simple graph. For any spanning tree $T$ of $G$, let $l(T)$ be the number of leaves of the graph $T$. Consider $\ell=\min_Tl(T)$, can I find a spanning tree $T$ with $l(T)=\ell$, ...
- 376
1
vote
1
answer
34
views
Generate all strongly connected tournament
I want to generate all strongly connected tournament of size $n \in \{4, 11\}$.
As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n ...
- 147
5
votes
4
answers
675
views
Limit of a sum with binomial coefficients
Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$
$$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$
$$C_k = \frac{\sum_{i=1}^k(...
- 115
3
votes
1
answer
127
views
Limit associated with two Beatty sequences that are not a Beatty pair
Suppose that $r>1$ and $s>1$ are irrational numbers, and let $a_n=\lfloor nr \rfloor$ and $b_n=\lfloor ns \rfloor$. Assume that $r$ and $s$ are numbers for which $\{a_n\}\cap\{b_n\}$ is ...
- 469
9
votes
2
answers
270
views
Asymptotics of a quadratic recursion
Consider the sequence defined by
\begin{align}
c_0 &{}= 1 \\
c_n &{}= 2\,n\,c_{n-1}-\frac{1}{2}\sum_{m=1}^{n-1}c_m\,c_{n-m}.
\end{align}
How can you prove that it has the following asymptotics ...
0
votes
1
answer
39
views
How sparse can a matrix mapping between sparse vectors be?
Let $s$ and $d$ be non-negative integers with $0\leq s<d$ and let $v,u\in \mathbb{R}^d$ be vectors satisfying the sparsity estimate
$$
\max\{\|u\|_0,\|v\|_0\}\leq d-s,
$$
where, as usual, for any ...
- 5,008
5
votes
0
answers
97
views
What is the rank sequence when you taking the smallest number that is no less than the average repeatedly?
This is the same problem at MSE. Since there is no answer (except one wrong deleted answer) there, I decided to post it here.
This is a problem created by me, although it may appear/looks like a ...
- 511
2
votes
0
answers
44
views
Maximize connectivity probability with a number of edges
We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
- 503
0
votes
0
answers
52
views
Graph reduction and combinatorial optimization
Crossposted at Theoretical Computer Science SE
We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
- 503
4
votes
0
answers
142
views
Number of {0,1}-matrices with an even number of 1’s in each row vs in each column
I am working on an equation that would be solved if I show the following.
Let $k \geq l$, and consider the set of $\{0,1\}$-matrices of size $k \times l$ with exactly $i$ 1’s. Consider the subset $\...
- 725
0
votes
1
answer
94
views
Matching bins up to shuffling II
Suppose a school purchases a set $\mathcal{S}$ of balls, say
$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$
with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct ...
- 21.4k
3
votes
0
answers
123
views
Expansion in Schur function of negative binomial exponent
I want to know if there exist a known expansion or can be derived of the polynomial
$$ \prod_{i=1}^{m}\prod_{j= 1}^{n}(1-z(x_i + y_i))^{-w} \tag{*}$$
in terms of Schur function. That is asking for (*) ...
- 641
0
votes
0
answers
45
views
Impact of reducing the number of distinct elements in the Count distinct problem
I am dealing with the Count distinct problem and Space saving algorithm. The problem goes like that:
I have a stream of $N$ elements. The number of distinct elements is $D$. Space saving algorithm is ...
- 11
1
vote
0
answers
37
views
Certificate that a laminar family from a crossing family is maximal
A laminar family $\mathcal{L}$ is a family of sets such that for all $A, B \in \mathcal{L}$, $A \subseteq B$, or $B \subseteq A$ or $A \cap B = \emptyset$. A crossing family $\mathcal{C}$ is such that ...
- 11
4
votes
1
answer
200
views
Why does the CHSH game need complicated bases to show advantage?
The CHSH game is the standard example of a game where two cooperating players Alice and Bob who cannot communicate, but who nevertheless can get an advantage by measuring an entangled quantum state in ...
0
votes
1
answer
114
views
Finite Hindman theorem
Consider the following finite version Hindman theorem:
For every sufficiently large $N\in\omega$ and 2-partition of $N=N_0\cup N_1$, there are $i<2,a,b,c\in N_i$ such that $a+b=c$.
The only proof I ...
- 909
6
votes
0
answers
151
views
Lindström-Gessel-Viennot from properties of the $Alt^k$ functor?
Let $A$ be the directed adjacency matrix of an acyclic directed graph, with variables as its nonzero entries (one for each edge). The $(a,b)$ entry of the matrix $(I-A)^{-1}$ is the sum over all paths ...
- 26.8k
4
votes
1
answer
235
views
For which "permutation groups" is the sign homomorphism well-defined constructively?
Let $X$ be a finite set. I now have a favorite construction of the sign homomorphism $Sym(X) \to C_2$. But perhaps it shouldn't be my favorite construction.
After discussion with the experts, I've ...
- 49.6k
1
vote
0
answers
90
views
Matching bins up to shuffling
Suppose a school purchased three bins of $n$ balls each, with each bin (labelled $1,2,3$ say) consisting of a different colour of balls, say red (1), green (2), and blue (3). On the first day the ...
- 21.4k
17
votes
3
answers
638
views
Matrices of combinatorial sequences that are inverse in two ways
I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which:
They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ ...
- 18.9k
0
votes
0
answers
65
views
Minimum average intersection size for couples of sets in an union closed family
The average size of the intersection between any two sets of the power set family without the empty set, $\mathcal{P}([n]) \setminus \emptyset$, is:
$$\frac{n2^{n-2}}{2^n-1}$$
Is it possible to find ...
- 348
0
votes
1
answer
140
views
Restrictions on exponents in multinomial formula
From the multinomial formula we have
$$(x_1 + x_2 + \dotsb + x_m)^n
= \sum_{k_1+k_2+\dotsb+k_m=n, \ k_1, k_2, \dotsc, k_m \geq 0} {n \choose k_1, k_2, \dotsc, k_m}
\prod_{t=1}^m x_t^{k_t}\,.$$
I ...
- 1
65
votes
2
answers
3k
views
Function that produces primes
For any $n\geq 2$ consider the recursion
\begin{align*}
a(0,n)&=n;\\
a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1.
\end{align*}
I conjecture that $a(n-1,n)$ is always ...
- 1,607
0
votes
0
answers
39
views
How many lists of tuples that are invariant (as sets) under a full cyclic permutation of one index?
Consider two finite index sets $A=\{1,\ldots,a\}$ and $B=\{1,\ldots,b\}$ and lists $((i_{k},j_k))_{1\leq k\leq n}$ with $i_k\in A$ and $j_k\in B$. Now we pick any $n$-cyclic permutation $\pi$. For ...
- 417
1
vote
1
answer
156
views
Inequalities between sums of products of certain binomial coefficients
I am a PhD student. During my researches, I often have to deal with inequalities involving sums of binomial coefficients, where the sums are indexed by some set of integer compositions. For example, ...
- 725
12
votes
3
answers
901
views
How to generate all triangulations of an orientable surface?
$\newcommand{\comb}{\mathrm{comb}}$Consider an orientable surface $S$ with punctures and boundaries (each boundary having at least a marked point).
A triangulation, up to orientation preserving ...
- 1,223
0
votes
0
answers
96
views
Conjecture on a sieve of Flavius Josephus
Flavius Josephus's sieve: Start with the natural numbers; at the $k$-th sieving step, remove every $(k+1)$-st term of the sequence remaining after the $(k-1)$-st sieving step; iterate.
Some examples:
...
- 1,607
1
vote
2
answers
282
views
Counting permutations defined by a simple process
Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it ...
- 115
4
votes
0
answers
97
views
When is a Schreier coset graph vertex transitive
When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...
- 1,723
1
vote
1
answer
56
views
Stern-Brocot tree and subtree
Let $a(n)$ be A007306, denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range $[0,1]$).
Let $b(n)$ be A002487, Stern's diatomic series (or Stern-Brocot sequence): $b(0) = 0, ...
- 1,607
5
votes
0
answers
132
views
Reference request: maximal determinant of matrices with pairwise orthogonal rows and entries in $\{1, 0, -1\}$
We know that "Hadamard maximal determinant problem" concerns the largest determinant of a matrix of oder $n$ with entries in $\{-1,1\}$ or $\{0, 1\}$. For $n=4k$, it is the Hadamard ...
- 665
3
votes
1
answer
117
views
Recurrence formula for boxed plane partitions
I'm looking for a nice recurrence formula for the number $[r,s,t]$ of $(r,s,t)$-boxed plane partitions in analogy to the recurrence formula
$$ [r,s]=[r-1,s]+[r,s-1]$$
for the binomial coefficient $[r,...
- 1,473
2
votes
1
answer
68
views
Efficient algorithm for edge-coloring complete graphs
Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
- 1,002
0
votes
0
answers
84
views
Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?
Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
- 343
4
votes
1
answer
241
views
A refinment of Beck's conjecture
Let $\mathcal{O}(n)$ and $\mathcal{D}(n)$ denote the set of all integer partitions of $n$ into odd parts and distinct parts, respectively. Let $o(n)=\#\mathcal{O}(n)$ and $d(n)=\#\mathcal{D}(n)$. ...
- 38.3k
5
votes
1
answer
282
views
Identity involving Jack polynomials at $x^{-1}$
Let $J_\lambda^{(\alpha)}(x)$ be the Jack polynomials in $N$ variables, with a normalization such that the coefficient of the monomial polynomial $m_\lambda$ is equal to 1.
They satisfy the identity
$$...
- 2,400
6
votes
1
answer
149
views
Writing upper triangular 0-1 matrices as a product of a permutation matrix and an upper triangular matrix
Let $C$ be an upper triangular matrix with entries 0 or 1 such that every diagonal entry is equal to one.
Let $M_C:=-C^{-1}C^T$.
Question: Is there a nice direct criterion (or even classification) on ...
- 22.2k
2
votes
1
answer
155
views
Another combinatorial identity
Is it true that
$$\sum_{r=0}^p \sum_{i=0}^r a_{n,p,r,i}=0$$
for all natural $n$ and all natural $p\ge2n$, where
$$a_{n,p,r,i}:=\frac{(-1)^r (n+p-r-1)! (n p-i (r-i))}{i!(r-i)! (n-i)!
(p-r+i)! (n-r+i)! ...
- 78.3k
4
votes
1
answer
223
views
Why do these polynomials split almost in the middle?
Start with a palindromic sequence of integers $(a_0, a_1, \ldots, a_{n+1})$, i.e. $a_j=a_{n+1-j}$, and put $a_j:=0$ for $j<0$ and $j>n+1$. You may readily guess that the choice of the binomial ...
- 12.6k
1
vote
2
answers
104
views
Difference in chromatic number between Schreier coset graphs and Cayley graphs
Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the ...
- 1,723
4
votes
1
answer
161
views
Order of a rational function on $\mathbb{F}_p$
Let $a$ be an element of $\mathbb{F}_p$, which is not a quadratic residue.
Define $$f(x) = \frac{x + a}{x+1},$$ which is a rational function on $\mathbb{F}_p$. In fact, if we set $f(-1)=\infty$ and $f(...
137
votes
32
answers
11k
views
Conceptual reason why the sign of a permutation is well-defined?
Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...
- 49.6k
1
vote
1
answer
100
views
How to distribute least number of $D$ card decks amongst $n$ people so that any $k$ people have a full deck and no $k-1$ people have a full deck
Decks are composed of 1 copy of each of $D$ unique cards. The set of cards is $C$ ($|C|=D$), the set of people is $P$ ($|P|=n\geq k$).
Starting with a simpler case (dropping the $k-1$ restriction)
One ...
- 19
8
votes
1
answer
225
views
Cardinality of the maximum points of the determinant on matrices with entries in [-1, 1]
By multilinearity, the maximum of the determinant on matrices with entries in the interval [-1, 1] is attained at a {-1, 1}-matrix. By the following example, the maximum is attained at infinitely many ...
- 665
10
votes
2
answers
675
views
The maximal subset of a finite field where the sum of any subset is non-zero
Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic.
For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty ...
- 347
2
votes
1
answer
196
views
Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
This question is a follow-up of this question.
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.
Question: Can we compute the exact minimum $$A:=
\min_{u:\mathbb{...
- 6,356
6
votes
1
answer
196
views
Vanishing linear combinations of minors
Let $V$ be the set of $k$ by $n$ matrices ($k<n$) with entries in $\mathbb{C}$, and let $\mathbb{C}[V]$ denote the set of polynomial functions on $V$. For any subset $I \subseteq [n] = \{1,2,\dotsc,...
- 135
2
votes
1
answer
111
views
Number of endofunctions in [n] without fixed points with exactly k two-cycles
I need a (numerically) evaluable function for the number $N_{n,k}$ of endofunctions $f: [n] \rightarrow [n]$ without fixed points that have exactly $k$ two-cycles, where $[n] := \{1,\dotsc,n\}$. In ...
- 380
0
votes
0
answers
29
views
Spectra of line graphs
What are the latest known results about spectra of finite line graphs? I just saw this paper on spectra of laplacians of infinite line graphs. Whether this is also valid for finite graphs.
Note that I ...
- 1,723