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

10,434
questions

1
vote

1
answer

85
views

### Sequence that sums up to A224071

Let $a(n)$ be A224071 (i.e., number of Schroeder paths of semilength $n$ in which there are no $(2,0)$-steps at level $1$). Here
$$
a(n) = \frac{1}{2(n+1)}\sum\limits_{k=0}^{n}(k+1)((-1)^{\left\...

1
vote

0
answers

53
views

### Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request

Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...

-3
votes

0
answers

49
views

### Question about permutationa and combination [closed]

This is the question:-In how many ways can an interview panel of 3 members be formed from 3 engineers, 2 psychologists and 3 managers if at least 1 engineer must be included?
and this is the answer:-
...

5
votes

2
answers

167
views

### Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,2,...,2k} into k pairs)

Let $k$ be a nonnegative integer. A configuration on $2k$ labeled points is simply a partition of the points into $k$ pairs, so for any set of $2k$ labeled points, there are $(2k-1)!!$ configurations.
...

1
vote

0
answers

83
views

### An interesting identity involving skew-Schur functions

Denote $\rho=(-\frac12,-\frac32,-\frac52,\dots)$. I was reading this interesting paper, where in particular, the authors claim that one can get the expression in (2.9)
\begin{align*}
\prod_{k\geq1}(1+...

2
votes

1
answer

113
views

### Refinement-minimal intersecting covers

Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....

2
votes

2
answers

211
views

### Negated Fibonacci and the floor function

Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here
$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, F_1 = 1, \\
F_{-n} = (-1)^{n-1}F_n
$$
I conjecture that
$$
F_{-n} = \left\lfloor\frac{n+1}{2}\right\rfloor ...

2
votes

1
answer

121
views

### How many cap sets are there?

Most research on cap sets that I'm aware of focuses on the size of a cap set. Are there any results about the number of maximum-cardinality cap sets?
For example, it is known that in the game of SET, ...

1
vote

0
answers

58
views

### Some ideas about parking functions and integer partitions

We know that a integer partition of $\lambda=(\lambda_1, ..., \lambda_m)$ of $n$ satisfying $\lambda_1\geq \cdots \geq \lambda_m$ and $\sum_{i=1}^m\lambda_i=n$. Let $\mathcal{P}(n)$ be the set of ...

0
votes

0
answers

48
views

### Reference for packing property and König property

Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?

2
votes

1
answer

586
views

### Separating Gamma in two independent functions

I've encountered a problem in my PhD. I would greatly appreciate any suggestions, tips, or comments you might have. The problem is
Let $\Gamma(s,x)$ be the incomplete gamma function. Given integers $n ...

0
votes

0
answers

32
views

### Largest root of the Adjacency matrix of two graphs (comparison)

Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial:
$$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...

0
votes

0
answers

70
views

### Shedding faces and decomposability in simplicial complexes

Definition:
A pure d-dimensional complex
$\Delta$ is $k$-decomposable if either $\Delta$ is a $d-$simplex or $\Delta$ contains a face $F$ such that
$\dim(F) \leq k$
both $\Delta \setminus F$ and $\...

16
votes

1
answer

457
views

### Simple proof that certain walks in the plane don't intersect

Suppose that $n$ hamsters are at the points $(1,n)$, $(2,n),\dots,
(n,n)$ in the plane. They walk independently one step east with
probability $p$ or one step south with probability $1-p$, until
...

0
votes

0
answers

174
views

### On a A057985 without recursion

Let $a(n)$ be A057985 (i.e., start with $0$ and repeatedly substitute: $0\to01, 1\to12, 2\to0$).
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here
$$
\...

20
votes

1
answer

578
views

### Low-level proof of identity related to Weierstrass P-function

A theorem which can be extracted from Theorem V.1.1 of Silverman's "advanced topics in the theory of elliptic curves" is the following. Here $\mathbb{Q}(u)$ denotes rational functions in a ...

2
votes

2
answers

177
views

### Is every finite lattice isomorphic to a union-closed family of sets containing $\emptyset$?

If a family of sets $\mathcal{F} \subseteq 2^E$ is union-closed and contains $\emptyset$, then $\mathcal{F}$ forms a lattice under the set-inclusion order. To see this, note that unions give the join ...

1
vote

0
answers

40
views

### Leibniz formula for Fulton's divided difference operators for quantum Schubert polynomials

Schubert polynomials are polynomials in the ring $\mathbb{Z}[x]$ where $x$ is an infinite set of variables indexed by the positive integers and they can be expressed in terms of "standard ...

0
votes

0
answers

83
views

### All possible variations of a n-characters long string that uses a given charset, but you can only change 2 characters at once [migrated]

So, let's say there's a string: "123" And there's a charset that you can use: {1, 2, 3}
In this scenario there would be 17 possible variations if you can only change 2 characters at once: ...

3
votes

0
answers

60
views

### Applications of q-Lagrange inversion

I was reading a text on q,t-Catalan numbers and Diagonal Harmonics by Haglund, where they mention the following $q$-analogue of Lagrange Inversion, taken from Page 53:
Let $e_n, h_n$ denote the ...

2
votes

0
answers

40
views

### $K_0$-basis modules with a unique extension related to parking functions

Let $B=B_n$ be the quiver algebra of type $A_n$ (with some orietnation) with $n$ points.
A $B$-module $M$ is a basis of the Grothendieck group $K_0$ if $M$ has $n$ indecomposable direct summands and ...

-3
votes

0
answers

44
views

### How to think about $\sum_{b=1}^m 2b{n\choose 2b}$ (A modified version of Chairman problem) [migrated]

I recently came across the following sum
$$
\sum_{b=1}^m 2b{n\choose 2b},
$$
where $n=2m$ or $n=2m+1$. I am aware of a similar sum where
$$
\sum_{k=1}^nk{n\choose k} = n2^{n-1},
$$
since the right ...

2
votes

1
answer

147
views

### Subset of $\mathbb N$ missing at least a class modulo each prime

One of my students asked me the following question. It seemed easy to answer but in fact, I am stucK.
The question: does there exist an infinite subset $S$ of $\mathbb N$ such there exists a positive ...

1
vote

0
answers

50
views

### Parabolic (double) quantum Schubert polynomials Pieri formula

I am writing calculation software for computing structure constants of equivariant quantum Schubert polynomials and I discovered that partial flag varieties corresponding to parabolic subgroups have ...

1
vote

0
answers

69
views

### Percolative process distribution not equivalent to coupon collector problem distribution

I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...

0
votes

0
answers

58
views

### VC dimension of full-dimensional closed polyhedral cone in $\mathbb R^d$

Consider a fixed set of vectors $\{x_i\}_{i\in[n]}$ in $\mathbb R^d$ and closed polyhedral cone $C = \{w \in \mathbb R^d : w^\top x_i \geq 0, \forall i \in [n]\}$ with full dimension i.e. $C$ contains ...

3
votes

2
answers

207
views

### Unique "clique" of differences in $\mathbb{Z}/m\mathbb{Z}$

Are there absolute constants $0 < \epsilon < 1$ and $N \in \mathbb{N}$ such that the following holds: For every $m \in \mathbb{N}$ and every $A \subseteq \mathbb{Z}/m\mathbb{Z}$ with $\frac{\...

7
votes

1
answer

493
views

### Suitable closed form for the A079501

Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).
The sequence begins with
$$
1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, ...

2
votes

0
answers

84
views

### Concentration inequalities for functions of random binary strings

Let $(X_1,\ldots,X_n)$ be a vector in $\{0,1\}^n$ drawn uniformly at random among all vectors with exactly $k$ $1'$s. I am interested in inequalities for tail probabilities for the random variables $X,...

17
votes

1
answer

1k
views

### Can the Pythagorean Graph be finitely colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...

0
votes

0
answers

27
views

### Hamiltonian Circuit Counting and Classification Problem

the Problem Description
background
Consider an undirected complete graph $G_n$ with $n$ vertices, where if the numerical labels of each vertex are consecutive, then the edge weight between them is $1$,...

4
votes

0
answers

86
views

### Symmetric functions and pattern avoidance

It is known that the number of $k$-regular simple graphs with vertices labeled by $1,2,\dots,n$ can be expressed as the coefficient of $x_1^k \dots x_n^k$ in a symmetric function, which is
$$
\prod_{1\...

1
vote

2
answers

176
views

### Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...

1
vote

0
answers

72
views

### Reconstructing a matroid by its minors

Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...

2
votes

1
answer

254
views

### On properties of sums involving the floor function

During my research on properties of fractional part and integer part functions, I was led to consider the function of two variables $f(n,k)=\frac{2^{k}+1}{2^{ n}+1}\left\lfloor \frac{2^{n}+1}{2^{k}+1}\...

1
vote

1
answer

102
views

### The signs of some mean-zero random variables

Let $X$ be a discrete random variable supported on $\{−5,\dots, 6\}$ in which the outcomes have the following respective probabilities: $$\begin{array}{rc}
n & p(n) \\ \hline −5 & 6/36 \\ −4 &...

2
votes

1
answer

103
views

### Recursion for the Chebyshev transform of $m^n$

Let
$$
R(n, q, m) = R(n-1, q+1, m) + \sum\limits_{j=0}^{q} (-1)^{q-j}R(n-1, j, m), \\
R(0, q, m) = (m-1)^q
$$
I conjecture that $R(n, 0, m)$ is a Chebyshev transform of $m^n$.
Examples of Chebyshev ...

5
votes

1
answer

180
views

### Does Manin's construction of non-commutative endomorphism algebra $\mathrm{End}(A)$ produce Koszul algebra, if $A$ is Koszul?

$\newcommand{\dual}{\mathrm{dual}}\DeclareMathOperator\End{End}\DeclareMathOperator\Fun{Fun}\DeclareMathOperator\Spec{Spec}\DeclareMathOperator\GL{GL}$Around 1986–7 Yu.Manin proposed natural and ...

1
vote

0
answers

73
views

### Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...

2
votes

0
answers

151
views

### A weight formula for subgraphs of $K_n$ and log-concavity of nested binomial coefficients

Nested binomials Let $t,d$ be positive integers and $n$ a parameter. The degree $td$ rational polynomial
$p_{t,d}(n)={{ n \choose t} \choose d}$ obviously takes integral values for integral $n$ (not ...

3
votes

0
answers

91
views

### Bijectivity of a linear map between symmetric polynomials of even degree

Let $\mathfrak S_n$ be the symmetric group of permutations of $n$
letters and let $S = \sum_{\sigma\in\mathfrak S_n} \sigma$ be the
symmetrization operator.
Let $\Lambda_n^r$ be the vector space of ...

18
votes

3
answers

2k
views

### Where do root systems arise in mathematics?

One often hears that root systems are ubiquitous in mathematics and physics. The most obvious occurrence of root systems is in the classification of complex simple Lie algebras. Where else do they ...

2
votes

1
answer

65
views

### Pseudo-partitions of $\mathbb{N}$

This question is loosely inspired by the exact cover / partition problem in computer science.
Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...

10
votes

5
answers

832
views

### Proving Poincaré's inequality for Boolean functions over the hypercube without Fourier analysis

$\DeclareMathOperator\Inf{Inf}\DeclareMathOperator\unif{unif}$I have been attempting to find a non-Fourier-analytic proof of Poincaré's inequality for Boolean functions over the hypercube. Let's call ...

3
votes

0
answers

111
views

### Explicit basis of symmetric harmonic polynomials

An orthonormal basis for the space of harmonic polynomials in $n$ variables is provided by the spherical harmonics on the $n-1$ sphere, see e.g. wiki.
From there, constructing an orthonormal basis for ...

2
votes

1
answer

127
views

### Weak compositions with no subcomposition adding to (more than) $j$

Here is a solution to a problem from Stanley's Enumerative Combinatorics (it's listed as a difficulty 2, so I imagine what I'm about to ask is likely a 2+ or 3-) about the number $\kappa(N,k,j)$ of ...

2
votes

0
answers

154
views

### Interesting conjecture by Sequence Machine

Let $a(n)$ be A344960 (i.e., position of binary complement of $n$-th word in A341258). By definition, in order to calculate $a(n)$, we need to know A341258. Below we will correspond this sequence with ...

5
votes

1
answer

250
views

### The coefficients of the Jack polynomials are polynomials in the Jack parameter

I implemented the Jack polynomials with a symbolic Jack parameter $\alpha$ in their coefficients ($\alpha=1$ for Schur polynomials, $\alpha=2$ for zonal polynomials). From my implementation (and also ...

2
votes

1
answer

119
views

### Find a finite semimodular poset such that

For definitions, see Section 1 of Chapter 3 of Richard Stanley, Enumerative Combinatorics, Volume I (second edition). Also see Section 8 of Chapter II of Garrett Birkhoff, Lattice Theory (third ...

1
vote

1
answer

71
views

### Closed form for a linear recurrence relation of varying order

In my research I have come across a recurrence relation that is of varying order. The relation is as follows:
$$
\begin{cases}
f_0=f_1=0,\\
f_2=1,\\
\bigg(f_{2\rho}=\displaystyle \sum_{i=0}^{\rho}...