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

8,687
questions

**2**

votes

**1**answer

207 views

### Divisibility of (finite) power sum of integers

Consider the power sum
$$S_a(b)=1^{2b}+2^{2b}+\cdots+(3a-2)^{2b}.$$
Let $\nu_3(x)$ denote the $3$-adic valuation of $x$.
QUESTION 1. (milder) Is this true?
$$\nu_3\left(\frac{S_a(b)}{S_a(1)}\right)=0....

**6**

votes

**0**answers

140 views

### Eigenvalues of symmetric matrices associated to posets

For a finite connected poset $P$ define the Cartan matrix $C$ as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in P$.
Define the Frobenius-Cartan matrix of $P$ as $...

**3**

votes

**1**answer

120 views

### Relationship between spectral gaps of adjacency and Laplacian matrices of graphs

Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...

**4**

votes

**1**answer

158 views

### Discriminants of some $q$-analogs of $(1+x)^n$

Let $[n]_q=1+q+\dots +q^{n-1}$, $ {[n]_q}! =[1]_q [2]_q \dots [n]_q$ and $\binom{n}{j}_q = \frac{[n]_q!}{[j]_q![n-j]_q!}$ be the usual $q$-notation.
Consider the polynomials $p_n(q,r,x)= \sum_{j=0}^n ...

**3**

votes

**1**answer

110 views

### Using singularity analysis for probability at a threshold?

In some urn model with parameter $p$, the generating function
$$
f_p(z) \;=\; \frac{1+p\,z}{1-(1-p)\,z\,(1+p\,z)}
$$
is such that $[z^n]f_p(z)$ is the probability that an $n$-urn configuration has a ...

**6**

votes

**1**answer

212 views

### Existence of a somewhat-smooth number in the interval $[x, x+ \log(x)]$

Smooth numbers in short intervals have been studied deeply in recent years with results of the form that $\psi(x, x^a)-\psi(x-x^b, x^a) \gg x^{b-\epsilon}$ for all $b>1-a-a(1-a)^3$ when $a \in (\...

**3**

votes

**0**answers

77 views

### Frobenius algebras associated to posets and coalgebra structures

Let $P$ be a finite poset that we assume for simplicity to be bounded (that is it has a global maximum M and minimum m).
Let k be a field, then the classical incidence algebra $kP$ has $k$-vector ...

**4**

votes

**0**answers

104 views

### Integral face ring of the triangulation of a sphere

The integral face ring of a (finite) simplicial complex $K$ on $m$ vertices is the quotient ring
$$\mathbb{Z}[K]=\mathbb{Z}[v_1,...,v_m]/\mathcal{I}_K$$
where $\mathcal{I}_K$ is the ideal generated by ...

**4**

votes

**1**answer

287 views

### Non-associative commutative "group"

When dealing with some hash functions that I was trying to speed up, I toyed with a binary operation with the goal to "approximate" the addition on $\{0,1\}^*$ when seen as binary ...

**3**

votes

**1**answer

215 views

### Probability that k randomly drawn permutations can be arranged to compose to the identity

Consider the symmetric group $S_n$ under the uniform distribution. For integer $k > 1$, suppose we draw $k$ elements $s_1, \dots, s_k$ independently at random. What is the probability that there ...

**-1**

votes

**1**answer

121 views

### A generalization of Vajda's identity [closed]

I discovered the identity below which generalizes Vajda's identity concerning Fibonacci Numbers. The identity states that:
if $F_r$ is the rth Fibonacci number, then
$$F_{n+i+x-z}F_{n+j+y+z}-F_{n+x+y-...

**2**

votes

**1**answer

57 views

### Maximum size of vertex set with no induced connected component on more than k vertices

An independent set of a graph is a collection of vertices such that the induced subgraph consists of disconnected vertices. The maximum possible cardinality of an independent set is then called the ...

**5**

votes

**1**answer

187 views

### Continued fraction associated to KdV solitons

Background (may be skipped by those interested only in the basic question and not important associations):
“An essay on continued fractions” by Euler (translated by Myra and Bostwick Wyman) contains ...

**1**

vote

**1**answer

148 views

### Coloring infinite graph made out of copies of a finite graph

I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically:
Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(...

**10**

votes

**1**answer

356 views

### A definition in poset theory

I am working on a article in poset theory. In that article, I am defining a subposet of a poset. The definition is following:
Let $P$ be a finite poset. A subposet $P'$ of $P$ is called closed under ...

**2**

votes

**1**answer

82 views

### What is the complexity of a special multigraph edge coloring problem

Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at ...

**0**

votes

**0**answers

26 views

### Approximabilty of submodular over modular maximization

Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...

**2**

votes

**1**answer

251 views

### Prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $

For all $k,R \in \mathbb{N}$ fixed, prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $. I'm quite sure this is true but ...

**15**

votes

**2**answers

715 views

### Combinatorial inequality involving alternating signs

I would like to prove the following inequality. It arises from my study of random matrices.
I have verified the inequality for $q\in \{0.01,0.02, \ldots, 0.99\}$ and $1\le n\le 100$.
Let $n$ be any ...

**1**

vote

**1**answer

185 views

### Inequality for $3$-adic valuation

This should probably be not that hard, but I would like to see a nifty way of proving it.
Consider the double-indexed sequence given by
$$f(n,k)=\binom{2n + 2k}{n + k}\binom{n + k}{n - k}3^k.$$
...

**2**

votes

**0**answers

174 views

### Does this question have anything to do with Catalan numbers?

I think this question has something to do with Catalan numbers but I'm not really sure. I want to find out the number of strings that consist of $n$ $L$'s and $n$ $R$'s, under the constraint that for ...

**0**

votes

**1**answer

131 views

### Dyck words and Catalan numbers

One of the many applications of the $n$th Catalan number is to calculate the number of strings consisting of $n$ $X$'s and $n$ $Y$'s, such that any prefix of the string will contain at least as many $...

**2**

votes

**1**answer

90 views

### Counting families of subsets of a fixed finite set closed under taking subsets

Let's fix a finite set $E, \#E = n$. I am interested in families $\cal S$ of subsets of $E$ with the property that if $A \in {\cal S}$ and $B \subset A$ then $B \in {\cal S}$. My question is: How many ...

**6**

votes

**0**answers

171 views

### Gaussian coefficients identity

I am having difficulty showing the equivalence between (11) and (15) of Delsarte - Association schemes and $t$-designs in regular semilattices. It is somehow an application of Möbius inversion, but I ...

**7**

votes

**1**answer

528 views

### When is a triangulation of sphere two-colorable?

Let $T$ be a triangulation of sphere. We say that $T$ is $k$-colorable if the triangles of $T$ can be assigned with $k$ colors such that any two triangles with a common edge have different colors.
I ...

**3**

votes

**0**answers

135 views

### A 3rd formula for the central Delannoy numbers?

There are several in the literature proving the two alternative formulas for the (diagonal) Delannoy numbers; namely that
$$d_n=\sum_{k=0}^n\binom{n}k\binom{n+k}k=\sum_{k=0}^n\binom{n}k^22^k.$$
Each ...

**5**

votes

**2**answers

280 views

### Modulo $3$ calculations for a binomial-sum sequence

Introduce the sequence (this is A047781 on OEIS)
$$t_n=\sum_{k=0}^{n-1}\binom{n-1}k\binom{n+k}k$$
and denote the set $T(ij)=\{n\in\mathbb{N}: \text{the ternary digits of $n$ contain $i$ or $j$ only}\}$...

**9**

votes

**2**answers

361 views

### Are there more paths exiting a box in $\mathbb{Z}^2$ to the right if I remove some edges to the left

Suppose that I am given the graph $G = (V,E)$ where $V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $ and there is an edge between two vertice $(n,m)$ and $(n',m')$ if and only if $\vert n-n'...

**3**

votes

**1**answer

188 views

### Is anything written about winning the "Dollar Game" in the minimal number of moves?

I run some Master's projects on Chip-Firing games, using the Holly Krieger's Numberphile video on the topic as an initial motivation, and going on to prove the main theorem stated there (that you can ...

**2**

votes

**0**answers

139 views

### On hypergeometric functions over finite fields

Let $\mathbb{F}_q$ be a finite field of $q$ elements. Let $A,B,C,\cdots$ denote the multiplicative characters over $\mathbb{F}_q$, and let $\overline{A}$ denote the inverse of $A$, i.e., $A(x)\...

**1**

vote

**1**answer

143 views

### Graph $G=(V,E)$ with $\chi(G)$ finite and $\text{Col}(G)$ infinite

Let $G = (V,E)$ be a simple, undirected graph. For $v\in V$ we let $N(v) = \{w \in V: \{v,w\} \in E\}$.
We define the coloring number $\text{Col}(G)$ of the graph $G$ to be the smallest cardinal $\...

**2**

votes

**1**answer

99 views

### Decoding the Reed–Muller $RM(m, m)$ code, and a matrix related to Pascal's triangle

The Reed–Muller $RM(m, m)$ code sends the message $p(X_0, \ldots , X_{m - 1}) = \sum_{S \subset \{0, \ldots , m - 1\}} \alpha_S \cdot X_S$ to its set of evaluations $\left\{ p(x_0, \ldots , x_{m - 1}) ...

**2**

votes

**1**answer

204 views

### Show that $\sum_{i=0}^{2k} [ {n\choose i+1} + (-1)^{i+1}{n+i+1\choose i+1} ] \sum_{j=0}^i {i\choose j}(-1)^j (i+1-j)^{2k} =0.$

Let $u(k,j) = 1$ if $j=0$, $0$ if $j > k$, or else it is $j*u(k-1,j-1) +(j+1)*u(k-1,j) $. Prove that $ \sum_{i=0}^{2k} {n \choose i+1} u(2k,i) +\sum_{i=0}^{2k} {-n-1 \choose i+1} u(2k,i)=0. $ ...

**4**

votes

**1**answer

216 views

### An acyclic simplicial complex where all links are generalised homology spheres

We say that a simplicial complex $K$ is acyclic if it's integral reduced simplicial homology groups are trivial in all dimensions.
For a vertex ${v} \in K$, we define the link
$$lk(v) :=\{\sigma \in K ...

**2**

votes

**1**answer

77 views

### What property of ranked poset ensures that it is determined by its vertex-facet incidences?

For a convex polytope, its face poset is combinatorially determined by vertex-facet incidences. Now suppose we have an arbitrary finite poset that is ranked, so I can still speak of vertices and ...

**5**

votes

**1**answer

128 views

### Relationship between Lambert $W$ function and Hypergeometric function

The Lambert $W$ Function is defined in this Wikipedia entry, while the Hypergeometric Function is defined in this other Wikipedia entry. There exists also a multivariate generalization which solves ...

**3**

votes

**2**answers

147 views

### Number of ways of distributing indistinguishable balls into distinguishable boxes with extra givens

What is the number of ways to distribute $m$ indistinguishable balls to $k$ distinguishable boxes given no box can be a unique number of balls?
for example: ($m=19$ and $k=5$)
$$x_1 + x_2 + \dots + ...

**0**

votes

**0**answers

79 views

### $0/1$ permanent symmetries

Assume matrix $A\in\{0,1\}^{n\times n}$ satisfies condition either $per(A)=0$ or $per(A)=1$.
Under what conditions is the value of $per(A+A')>per(A)$ where $'$ is transpose?
Under what conditions ...

**6**

votes

**2**answers

470 views

### 2-adic valuation of a certain binomial sum

Consider the sequence (of rational numbers) given by
$$a_n=\sum_{k=1}^n\binom{n}k\frac{k}{n+k}.$$
Let $s(n)$ be the sum of binary digits of $n$, i.e. the total number of $1$'s.
QUESTION. Is it true ...

**1**

vote

**0**answers

65 views

### LGV scheme: Any situations where the weights shift differently for each path?

In Cylindric partitions, Proposition 1, Gessel and Krattenthaler prove a formula for lattice paths on a cylinder
In our particular problem, we again have paths $((P_{1},k_{1}),...,(P_{r},k_{r}))$ but ...

**1**

vote

**2**answers

145 views

### Closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$

For all natural numbers $a$, is there a known closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$, where $k$ is fixed?
For example, letting $k=1$ gives the ...

**1**

vote

**2**answers

198 views

### The Diophantine equation $d^2 + (k-1)e^2 = k(k^2 + 2)/3$

I am interested in all solutions in odd positive integers $d$, $e$, $k$, with $d\leq k$ and $e\leq k$ of the equation $d^2 + (k-1)e^2 = k(k^2 + 2)/3$. (I had posted this earlier but left out the ...

**11**

votes

**2**answers

801 views

### Heuristic lower bounds on small sums of roots of unity

Let $f(k,n)$ be the smallest non-zero absolute value of a sum of $k$ complex $n$th roots of unity. Asking for bounds in either direction, Tao suggested that a polynomial lower bound seemed plausible ...

**3**

votes

**1**answer

473 views

### Are there only two solutions for $1+3+9+...+3^m=2^n$

Are there only two solutions for $$\sum_{k=0}^m3^k=2^n$$
Such as $3^0=2^0$ and $3^0+3^1=2^2$
Note
• If $m$ is even then $\sum_{k=0}^m3^k$ will be odd.
• $$\sum_{k=0}^m3^k=\sum_{k=0}^m\binom{m+1}{k+1}2^...

**2**

votes

**1**answer

163 views

### At most one perfect matching of a bipartite graph

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has
$0$ perfect matchings
$1$ perfect matchings
is it ...

**2**

votes

**0**answers

68 views

### Why is Schröder numbers equivalent to the number of perfect matchings for triangular grid of n squares and how the graph look like? [duplicate]

In the OEIS entry for the Schröder numbers is A006318. There is a comment which related the sequence to perfect matchings:
The number of perfect matchings in a triangular grid of n squares (n = 1, 4, ...

**10**

votes

**1**answer

405 views

### Real rootedness of a polynomial with binomial coefficients

It is possible to show using diverse techniques that the following polynomial:
$$P_n(x)=1 + \binom{n}{2} x + \binom{n}{4} x^2 + \binom{n}{6} x^3 + \binom{n}{8} x^4 +\ldots + \binom{n}{2\lfloor\tfrac{n}...

**1**

vote

**0**answers

57 views

### Subgraph isomorphism problem with linear map

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...

**3**

votes

**0**answers

104 views

### Counting lattice polytopes by volume

For any $n \in \mathbb{N}$ and $B \in \mathbb{R}_{\geq 0}$, let $\mathcal{P}(n,B)$ be the set of $n$-dimensional convex polytopes $\Delta \subseteq \mathbb{R}^n$, taken up to integral, unimodular ...

**0**

votes

**0**answers

87 views

### I am interested in all solutions in odd positive integers d, e, k, with d<=k and e<=k of the equation d^2 + (k-1)e^2 = k(k^2 + 2)

I am interested in all solutions in odd positive integers d, e, k, with d<=k and e<=k of the equation d^2 + (k-1)e^2 = k(k^2 + 2).
This came up during work on dominating sets of the queen's ...