# 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.

6,444 questions

**0**

votes

**0**answers

105 views

### Question regarding contiguous forms

I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...

**0**

votes

**1**answer

1k views

### How to find out the sum involving floor function [closed]

I came up with an equation while solving a question. The question is - suppose we have n numbers, from 1 up to n. How many groups of 3 numbers (repetition allowed) can be formed whose sum will be n.
...

**0**

votes

**0**answers

253 views

### 5 player round-robin tournaments

Is there any literature on the order structure coming from round-robin tournaments? I play games on littlegolem and the tournaments are mostly 5x5 round-robins. I noticed at the end, after sorting ...

**0**

votes

**0**answers

554 views

### Decomposing max-convolution of sum of functions ?

Hello.
$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100.
$R$ is a linear combination of $F_1, F_2, F_3$.
Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$
where $w_1,...

**0**

votes

**0**answers

114 views

### A search for optimal order ideals

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in
name for a partial order.
Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$...

**0**

votes

**0**answers

295 views

### Showing that Paley Graphs are Edge-Transitive

I would like to show that Paley graph are rank $3$ graphs (i.e. Vertex-Transitive, Edge-Transitive and Non-Edge-Transitive).
Showing that they are vertex transitive is easy - every $x \mapsto x+k$ is ...

**0**

votes

**0**answers

181 views

### Generate combinations with repeated symbols?

I would like to generate fixed size sequences contained a fixed number of repeated symbols.
For example how to generate sequences of size N containing exactly p symbols of one type q symbols of ...

**0**

votes

**0**answers

236 views

### Fast removal of weighted edges in a graph in a way such that all shortest paths are preserved

This problem is analogous to fast removal of the minimum number of edges in a weighted graph such that if the graph were to be drawn on paper with edge lengths linear in proportion to their weights, ...

**0**

votes

**0**answers

513 views

### Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...

**0**

votes

**0**answers

251 views

### 12 and 13-bit balanced Gray codes

I am trying to find a transition sequence for both 12 and 13 bit balanced Gray codes. I know there are some excellent papers on the topic of deriving these sequences available on the internet, but I ...

**0**

votes

**0**answers

302 views

### Estimating a multinomial sum

I have the following sum
\begin{equation}
\sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda}
\...

**0**

votes

**0**answers

150 views

### Finding the bottleneck in a chain of functions

I have a problem that involves finding a bottleneck. It appears to me to be a linear bottleneck assignment problem, but recognizing (and solving) such problems is far outside my area of expertise. If ...

**0**

votes

**0**answers

184 views

### Packing Icons Onto A screen

You are trying to pack icons onto a screen that is divided into n horizontal rows of uniformly varying size. The rows narrow by a fixed ratio as one goes up the screen from the bottom. Since the icons ...

**0**

votes

**3**answers

321 views

### boolean functions and averaging / counting

Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...

**0**

votes

**0**answers

1k views

### Ignore this question [closed]

This question is a hacky way to create some tags for you to use. Move along.

**0**

votes

**1**answer

385 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**0**

votes

**2**answers

605 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**-1**

votes

**1**answer

330 views

### Limit involving the totient function and combination

Hi,
Do you think the following limits are correct?
$\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\phi(N) \choose k} {d-1 \choose k-1}}{\phi(N)^d}=0$
$\displaystyle\lim_{N\to\infty}\...

**-1**

votes

**1**answer

445 views

### cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]

Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...

**-1**

votes

**2**answers

249 views

### Selection problem in a collection of non-empty sets

Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties?
$a\in {\cal F} \implies |a|\geq 2$,
$...

**-1**

votes

**1**answer

113 views

### Version of Hall's marriage theorem in arbitrary finite graphs [closed]

Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge).
For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...

**-1**

votes

**2**answers

157 views

### Expected number of balls left out when choosing $n$ times from $n$ balls

I am given $n$ balls. For $n$ times, I pick one of them with uniform probability and put it back after picking it.
Let $U$ be the number of balls I have never picked, so $U\in \{0,\ldots,n-1\}$. We ...

**-1**

votes

**1**answer

138 views

### Chromatic number of transposition graph of permutations

For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let ...

**-1**

votes

**1**answer

291 views

### Incidences of Lines / Circles in the Plane

During linear algebra class, I was explaining that given 2 equations + 2 unknowns where we expect there to be a unique solution but sometimes there can be 0 solutions or a line's worth.
At some ...

**-1**

votes

**1**answer

278 views

### Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$
Reccurence formula is
$a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose \...

**-1**

votes

**1**answer

102 views

### Multiset to set operator [closed]

Is there an operator that transform a Multiset into a set by choosing all the distinct elements? Is there a better/more accurate way to write it than this:
We denote the set $S$ by choosing the ...

**-1**

votes

**1**answer

322 views

### Infinite sum and product associated with the Weierstrass elliptic function [closed]

Can anyone help me figure out how the identity below was obtained?
$ \frac{1}{\sqrt{(e_1-e_3)(e_2-e_3)}} = R \prod \limits_{n=1}^{\infty} \left(1 - \frac{1}{R^{4n}} \right)^{-4}\left(1 + \frac{1}{R^{...

**-1**

votes

**1**answer

91 views

### Lower bound on the distance set using incidences of points and circles

Suppose that $P$ is a set of $N$ points in the plane. Can we get a lower bound for the cardinality of the distance set $d(P)$ from the Szemerédi–Trotter theorem?
Here is my try.
The Szemerédi–Trotter ...

**-1**

votes

**1**answer

78 views

### Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...

**-1**

votes

**1**answer

126 views

### How compute combinatorial expression [closed]

How compute
$\sum_{j=1}^k \binom{x}{j}\binom{k-1}{j-1}\alpha^j, \quad x, \alpha\in\mathbb{R}$

**-1**

votes

**1**answer

92 views

### Discrepancy in non-homogeneous arithmetic progressions

I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies
$ \left | \...

**-1**

votes

**1**answer

209 views

### Does the divergence of the sum of reciprocals of a set of integers imply this density statement about the set?

Suppose $A \subseteq \mathbb{N}$ is such that $\displaystyle{\sum_{n \in A} n^{-1}} = \infty$. Suppose $B \subseteq \mathbb{N}$ is infinite.
Is there a set $X \subseteq [1,\infty)$ and a increasing ...

**-1**

votes

**1**answer

355 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**

votes

**3**answers

564 views

### A binomial sum expression

Does anyone know how to show the following combinatorial equality, $\sum_{i=0}^{n}\left(n-i\right)^{2}\binom{2n}{i}=n\cdot4^{n-1}$?
By the way, this is not a homework problem, otherwise one would be ...

**-1**

votes

**1**answer

484 views

### Name for probabilistic version of Pascal's identity and differentiation formula for binomial distribution

I'm trying to find a standard name or standard reference for two simple-to-prove relations involving binomial distributions.
Define:
$b(n,r,p) := \binom{n}{r}p^r(1 - p)^{n-r}$
i.e., it is the ...

**-1**

votes

**1**answer

669 views

### Conjugate vertices and distinguishing properties

Motivation (added)
A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$.
A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by $2^...

**-1**

votes

**1**answer

98 views

### Subgroup of the semidirect product of two subgroups with coprime orders [closed]

It is well known that if $\gcd (|H|,|K|)=1$ then all subgroups
of $H\times K$ are of the form $H^{\prime }\times K^{\prime }$ such that $H^{\prime}$ is a subgroup of $H$ and $K^{\prime}$ is a subgroup ...

**-1**

votes

**1**answer

90 views

### Chromatic Number of graph of a set of squares [closed]

We are given a set of squares in the plane with sides parallel to the x-y axes.
We know that intersection of every three of them is empty.
Show that we can color these squares with red, blue and ...

**-1**

votes

**1**answer

50 views

### Size of smallest set in critical covering of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ...

**-1**

votes

**1**answer

232 views

### Order-Perserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...

**-1**

votes

**2**answers

83 views

### Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves.
Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...

**-1**

votes

**1**answer

338 views

### Basketball shots and stopping rule [closed]

Moved over from StackExchange.
You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...

**-1**

votes

**1**answer

143 views

### Algorithm to find symmetric function given specialization

I have a symmetric function f(c1,c2,c3,c4,c5) which, when c1 < c2 < c3 < c4 < c5, has the form p1(c1)+p2(c2)+p3(c3)+p4(c4)+p5(c5), where the p_i's happen to be polynomials of degree <=5....

**-1**

votes

**1**answer

360 views

### partition of a set

First, we see this example.
Suppose we have a set of 6 elements, we can get 3 subsets of it, each of which has 2 elements, but no two sets overlap.
But if our set has 5 elements, we want to get 3 ...

**-1**

votes

**0**answers

62 views

### how to compute the number of possible trees in a tree graph? [on hold]

Let's suppose that I have a tree with n nodes. The root of my tree does not change in time. It is the same. However, the rest of nodes change their positions (...

**-1**

votes

**0**answers

60 views

### Find bound on my tail distribution

hope you have a nice day.
I try to find an (exponentially) decreasing bound on a tail distribution. Reason: I want to create and find the expected cumulative regret (and confidence bounds) for a ...

**-1**

votes

**1**answer

265 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...

**-1**

votes

**1**answer

63 views

### Transforming random variables for having good property?

For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...

**-1**

votes

**0**answers

44 views

### Multiplicities of ordered pairs in pairing of two multisets

This is a repost from a question on math.stackexchange.
Problem: I have two multisets, $X$ and $Y$. Each is a $k$-combination with repetition of a set $N=\{1,2,3,\dots,n\}$, where $n$ can be greater, ...

**-1**

votes

**0**answers

53 views

### Is there any relationship between the Hungarian Algorithm and the Hesse Diagram method for ranking and sorting?

The Hungarian algorithm is used for the assignment problem. I would like to know whether the Hesse diagram method can be used to rank and sort as the Hungarian algorithm can.