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

**0**

votes

**0**answers

10 views

### Making a not-multi graph from a multigraph

Given $k$ girls, they are given $kn$ balls so that each girls has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each color. Two girls may exchange the balls (1 ball for ...

**2**

votes

**0**answers

43 views

### Can one enumerate the set partitions of the faces of a regular dodecahedron mathematically?

If we partition the faces of a regular dodecahedron into one nonempty subset, there is only one partition; for twelve nonempty subsets, there is also just one partition; for eleven nonempty subsets ...

**2**

votes

**0**answers

75 views

### On covers of groups by cosets

Suppose that ${\cal A}=\{a_sG_s\}_{s=1}^k$ is a cover of a group $G$ by (finitely many) left cosets with $a_tG_t$ irredundant (where $1\le t\le k$). Then the index $[G:G_t]$ is known to be finite. In ...

**0**

votes

**0**answers

71 views

### Arithmetic that corresponds to combinatorial rectangles and cylinder intersections?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets.
In communication complexity the interpretation is more on intersection and union of ...

**3**

votes

**1**answer

121 views

### Generating function for lattice paths making aribitrary (i,j)-up-right move in one step and fitting rectangular (m,n)?

There is the following beautiful formula (see Qiaochu Yuan excellent blog):
$$ \sum_{\lambda \in Young~diagrams~fitting~rectangle~m~n} q^{Box~count(="area~under~the~curve")~of~\lambda} = \binom{n+m}{...

**0**

votes

**0**answers

51 views

### Find large “induced” bipartite graph in a dense graph?

Do there exist constants $d>0$, $0<c<1$, $\delta>0$ so that for all large $n$, there exists a graph $H$ satisfying $$e_H\ge dn^2,$$ and then no matter how we remove some edges from $H$ to ...

**7**

votes

**1**answer

103 views

### Formula for number of permutations less than a given permutation in weak order

Let $w\in S_n$ be a permutation. Is there a reasonable "formula" for the number of elements of the initial interval $[e,w]$ of weak (Bruhat) order from the identity to $w$?
In terms of what such a "...

**1**

vote

**1**answer

72 views

### Matrix of powers of pairwise differences

Let $\underline{c}:=\left(c_1,\dots,c_n\right)$ be pairwise distinct complex numbers, and let $k$ be a non-negative integer. Define the matrix $A_{n,k}(\underline{c})$ to contain the $k$-th powers of ...

**2**

votes

**0**answers

86 views

### Proving that $\lambda\mapsto \chi^\lambda(C)/f^\lambda$ is a polynomial

Let $\lambda$ be a partition of $n$ and $\chi^\lambda$ be the character of $S_n$ associated to it. Given any conjugacy class $C$, I want to prove that
$$\lambda\mapsto \frac{\chi^\lambda(C)}{f^\lambda}...

**-2**

votes

**0**answers

40 views

### Combinatorics - Maximum No. of ways to visit all the cities in list starting from 1st city [on hold]

You are given a list consisting of only 1's and 0's,
if the value of given element is 1 then you can travel to any city such that
1<= |i-j|<=2 , where i is the position of current city and j is ...

**0**

votes

**0**answers

16 views

### How to infer the number of subsequences of array equal with the number all combination of array? [on hold]

If I have an array of size n. I want the number of all subsequences of it (contains empty).
For example: [1, 2, 3] 's all ...

**0**

votes

**0**answers

105 views

### A binomial coefficient identity

i'm unable to prove the following : $\forall n$ integer $\geq 3$,
$ \displaystyle \displaystyle \sum_{s=1}^n \sum_{j=n-s+1}^n \displaystyle \frac{ (\binom n j )^2 \binom {n+j} n }{s-n+j} ( \...

**4**

votes

**0**answers

48 views

### Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...

**2**

votes

**1**answer

81 views

### Maximum number of $0$-$1$ vectors with a given rank

Let $k\ge2$. The maximum number of $0$-$1$ (column) vectors of length $2k-1$ which make a rank $k$ matrix with no zero row nor two identical rows is $2^{k-1}+1$. (The rank is over the rationals.)
I ...

**2**

votes

**1**answer

109 views

### “Oddity” of $q$-Catalan polynomials: Part II

This question extends my earlier MO post for which I'm grateful for answers and useful comments.
The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ satisfy:
$\text{$C_{1,n}$ is odd iff $n=2^j-1$ for ...