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

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)...
249 views

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 ...
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 ...
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 ...
278 views

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 ...
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 ...
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}$
92 views

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 ...
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 ...
669 views

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