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
2
votes
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
2answers
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
0answers
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
2answers
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
2answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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 ...