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.

Filter by
Sorted by
Tagged with
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_{...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
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 (*) ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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)$. ...
user avatar
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 $$...
user avatar
  • 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 ...
user avatar
  • 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)! ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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{...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 1,723

1
3 4
5
6 7
186