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
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\...
Notamathematician's user avatar
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 ...
Alexander Chervov's user avatar
-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:- ...
user526506's user avatar
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. ...
atenao's user avatar
  • 323
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+...
T. Amdeberhan's user avatar
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....
Dominic van der Zypen's user avatar
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 ...
Notamathematician's user avatar
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, ...
Timothy Chow's user avatar
  • 78.7k
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 ...
Ethan's user avatar
  • 11
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?
Sowbarnika R's user avatar
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 ...
curiosity96's user avatar
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^...
User8976's user avatar
  • 199
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 $\...
user177523's user avatar
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 ...
Richard Stanley's user avatar
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 $$ \...
Notamathematician's user avatar
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 ...
Kevin Buzzard's user avatar
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 ...
Clay Thomas's user avatar
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 ...
Matt Samuel's user avatar
  • 2,038
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: ...
Vollbild553's user avatar
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 ...
yeetcode's user avatar
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 ...
Mare's user avatar
  • 26.2k
-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 ...
the_village_kid's user avatar
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 ...
joaopa's user avatar
  • 3,749
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 ...
Matt Samuel's user avatar
  • 2,038
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 ...
Cardstdani's user avatar
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 ...
Neophyte's user avatar
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{\...
e1c25ec7's user avatar
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, ...
Notamathematician's user avatar
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,...
TOM's user avatar
  • 2,248
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, ...
Yaakov Baruch's user avatar
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$,...
nevermind_15's user avatar
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\...
minhtoan's user avatar
  • 1,454
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 $...
ABB's user avatar
  • 3,992
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$. ...
J. Allen's user avatar
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}\...
 Babar's user avatar
  • 275
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 &...
James Propp's user avatar
  • 19.4k
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 ...
Notamathematician's user avatar
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 ...
Alexander Chervov's user avatar
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 $\...
ABIM's user avatar
  • 4,969
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 ...
CHUAKS's user avatar
  • 1,024
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 ...
Martin Rubey's user avatar
  • 5,563
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) ...
Dominic van der Zypen's user avatar
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 ...
Mathews Boban's user avatar
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 ...
Cacuete's user avatar
  • 31
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 ...
Makenzie's user avatar
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 ...
Notamathematician's user avatar
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 ...
Stéphane Laurent's user avatar
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 ...
Tri's user avatar
  • 1,388
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}...
the_village_kid's user avatar

1
2 3 4 5
209