All Questions
Tagged with co.combinatorics polynomials
113 questions with no upvoted or accepted answers
3
votes
0
answers
61
views
Biggest Cartesian Product Included in a Real Plane Curve
Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
- 351
3
votes
0
answers
111
views
When does the constant term in the following expansion is nonzero?
Dyson's Theorem
The constant term in the expansion of
$$\prod_{1\leq i\neq j\leq n}\left(1-\frac{x_i}{x_j}\right)^{a_i}$$
is the multinomial coefficient
$$\frac{(a_1+\cdots+a_n)!}{a_1!\cdots a_n!},$$
...
- 1,997
3
votes
0
answers
312
views
Enumerating a class of polynomials
How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...
user76479
3
votes
0
answers
186
views
identity for number of monomials
Fix a positive integer $d \geq 2$, and let $n,k$ be natural numbers with $k \leq n$.
Let $b(n,k)$ denote the number of monomials of degree $kd-(n+1)$ in $n+1$ variables $x_0,\ldots,x_n$ with all ...
- 31
3
votes
0
answers
147
views
Are there existing resources on modular-esque recurrence relations?
Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?
$\begin{align*}
f_{n,k}(x) & =a(x)f_{n-1,k}(x)+b(x)f_{n-2,k}(...
- 131
2
votes
0
answers
119
views
Generalized identity with Stirling numbers of the second kind and falling factorials
It is known that Striling numbers of the second kind satisfy the relation
$$
\sum\limits_{k=0}^{n}{n \brace k}(x)_k = x^n.
$$
where $(x)_n$ is the falling factorials such that
$$
(x)_n = x(x-1)(x-2)\...
- 4,938
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,938
2
votes
0
answers
49
views
Skew Jack polynomial when the Jack parameter is zero
According to Macdonald's book, when the Jack parameter $\alpha$ is $0$,then the Jack $P$-polynomial $P_\lambda(\alpha)$ is the elementary symmetric polynomial $e_{\lambda'}$ where $\lambda'$ is the ...
- 2,560
2
votes
0
answers
70
views
Property of a family of simple polynomials related to the A329369
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 4,938
2
votes
0
answers
123
views
Alon Tarsi reaches its lower bound for complete multipartite graphs
Consider a complete multipartite graph $G$ with $k$ $(k\ge2)$ parts with equal number of vertices $n$, where $n$ is even. If $k=2$, it is a well known result that the Alon-Tarsi number (ATN)(The ...
- 2,089
2
votes
0
answers
64
views
Eulerian polynomial from Bruhat interval - h* of something?
Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...
- 15.8k
2
votes
0
answers
69
views
Set partitions with big blocks - real-rooted polynomials?
The polynomials
$$
T_n(t) := \sum_{\pi \in \text{Set Partitions}(n)} t^{\text{blocks}(\pi)} = \sum_{k=1}^n S(n,k)t^k
$$
with $S(n,k)$ being the Stirling numbers of the second kind, are well-known to ...
- 15.8k
2
votes
0
answers
140
views
Asymptotics of a "non-constant order" quadratic recurrence relation in two variables
Consider the following recurrence relation defined for two integer variables $H,n \geq 0$:
\begin{equation}
\gamma(H,n) = \sum_{K=0}^{\lfloor H/2 \rfloor} \gamma(K,n-1) \gamma(H-K,n-1)
\end{equation}
...
- 143
2
votes
0
answers
73
views
An iterative formula for the Kreweras-Voiculescu polynomials (reference request)
Let
$$N(x) = 1 + \sum_{k \ge 1} N_k(h_1,h_2,...,h_k) \;x^k$$
$$ = 1 + h_1 x + (h_1^2 + h_2) x^2 + (h_1^3 + 3h_1h_2 + h_3)x^3 + (h_1^4 + 6 h_2 h_1^2 + 4 h_3 h_1 + 2 h_2^2 + h_4) x^4 + \cdots$$
be the ...
- 10.5k
2
votes
0
answers
68
views
Sampling theorems for partition polynomials (associahedra, noncrossing partitions / parking functions)
Define the associahedra partition polynomial
$$
\begin{split}
A(x) &= 1 + A_1(u_1) z + A_2(u_1,u_2) z^2 + A_3(u_1,u_2,u_3) z^3 + \cdots\\
& \qquad\qquad = 1 + \sum_{n \geq 1} A_n(u_1,...,u_n) ...
- 10.5k
2
votes
1
answer
358
views
q-polynomials in terms of a basis
Consider the polynomials
$$f_n(q)=\prod_{j=1}^n(1+q^j) \qquad \text{and} \qquad g_m(q)=1+q+q^2+\cdots+q^m.$$
I'll list a few examples to motivate my question. Direct calculations show that
$$f_1=g_1, \...
- 43.2k
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
2
votes
0
answers
80
views
Inequality on polynomials
Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...
- 43.2k
2
votes
0
answers
117
views
A multi-variable "Fibonacci polynomial"?
There is a tremendous literature on the Fibonacci sequence, including its polynomial analogue $F_{-1}=0, F_0=1$ and
$$F_n(x)=xF_{n-1}(x)+F_{n-2} \qquad \text{for $n\geq1$}.$$
What I have found is the ...
- 43.2k
2
votes
0
answers
345
views
Combinatorics of iterated composition of noncrossing partition polynomials
A combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin, Itzykson, Parisi, and Zuber ...
- 10.5k
2
votes
0
answers
63
views
Finding non-commutative finite-dimensional "hypersurface" algebras
Fix a field $K$.
Call a non-commutative polynomial $f(x_i)$ whose monomial terms are all of degree at least 2 in the variables $x_i$ magic if the finite dimensional $K$-algebra $A_{f,n}:=K<x_i>/(...
- 26.5k
2
votes
0
answers
193
views
Possibly new multivariate polynomials associated to finite graphs
Let $G = (V,E)$ be a finite graph, where $V$ is a finite set of vertices and $E$ is a finite set of unoriented edges. We assume that $G$ has no loops, i.e. that there is no edge joining a vertex to ...
- 5,215
2
votes
0
answers
112
views
Getzler's stable graphs for modular operads
In The semi-classical approximation for modular operads, Getzler displays a table at the bottom of page two enumerating certain stable graphs. (This is related to the MO-Q "Stable graphs: Feynman ...
- 10.5k
2
votes
0
answers
119
views
Monotonicity Theorem of inverse Kazhdan Lusztig polynomials
Let $P_{x,w}$ and $Q_{x,w}$ be the Kazhdan Lusztig polynomial and the inverse Kazhdan Lusztig polynomial of Coxeter group $W$, respectively. i.e., $\sum_{x\le y\le z}(-1)^{\ell(y)-\ell(x)}P_{x,y}(q)Q_{...
- 1,875
2
votes
0
answers
52
views
The graph polynomial of the Total Graph of a Graph
Consider the Total Graph ($T(G)$) of a graph $G$ with vertex set $V$ edge set $E=\{(u,v)\}$ with Line graph $L(G)$ and subdivision graph $S(G)$ (formed by putting a vertex in each edge of the original ...
- 2,089
2
votes
0
answers
185
views
Infinite products from the fake Laver tables-Now with no set theory
We say that a sequence of algebras $(\{1,\dots,2^{n}\},*_{n})_{n\in\omega}$ is an inverse system of fake Laver tables if for $x\in\{1,\dots,2^{n}\}$, we have
$2^{n}*_{n}x=x$,
$x*_{n}1=x+1\mod 2^{n}$,...
2
votes
0
answers
208
views
Real-rooted polynomials with coefficient constraints
My question is whether there exists $(a_0, a_1, \ldots, a_{2n-1}) \in \mathbb{R}_{+}^{2n}$ such that
(1). $a_{2k} + a_{2k+1} = \binom{3n-1}{3k} + \binom{3n-1}{3k+1} + \binom{3n-1}{3k+2}$ for all $0 \...
- 151
2
votes
0
answers
115
views
Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices
I'll give two equivalent statements of the setup, then give my questions.
Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in \{1,2,\...
- 21
2
votes
0
answers
337
views
Enumerating certain types of permutation polynomials
Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for all ...
- 1,197
2
votes
0
answers
277
views
Characteriszation of certain kinds of polynomials
My question:
Is there a known characterization for polynomials $P\in \mathbb{R}[x,y]$
with the property that
$$P(x,y) = 0 \wedge P(y,x) =0 \Rightarrow x = \overline{y}$$
and the number of the ...
- 15.8k
1
vote
0
answers
164
views
Combinatorial question related to Hankel-type matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $n\geq 2, d$ be positive integers. I would like a lower bound on the largest integer $r$ for which the following property holds:
For any ...
- 980
1
vote
0
answers
63
views
Factorization of the symmetric function identity $E(t)=1/H(t)$ with the refined Euler characteristic polynomials of associahedra / Lagrange inversion
I've come across two matrix identities, flagged with daggers below, relating the two sets of elementary and complete homogeneous symmetric polynomials/functions via the two sets of refined Lah and ...
- 10.5k
1
vote
0
answers
69
views
Simplification of computing $f(n,z)$
Let
$$
s(n,z)=\sum\limits_{j=0}^{n}L(n,j,z)
$$
where
$$
L(n,j,z)=\sum\limits_{p=0}^{n-j-1}f(p,z)L(n-j-1,p,z), \\
L(n,n,z)=1
$$
Now let $s(n,z)$ be an arbitrary function such that $s(0, z)=1$. It means ...
- 4,938
1
vote
0
answers
216
views
Classical and free cumulants, symmetric functions, and inverses (references), related to associahedra, parking functions, noncrossing partitions
Looking for references for one or more of the following four sets of partition polynomials 1a) through 4a), particularly those which present geometric / topological combinatorial interpretations.
...
- 10.5k
1
vote
0
answers
180
views
Applications of hyperbolic polynomials?
The recently posted MO-Q "Positivity of the coefficients of Taylor series associated to the Riemann hypothesis" (see also this MO-Q) has re-kindled my interest in hyperbolic polynomials--...
- 10.5k
1
vote
0
answers
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
1
vote
0
answers
147
views
Counting Hamiltonian cycles in graph and finding a coefficient of polynomial
Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[...
- 25.4k
1
vote
0
answers
329
views
Outlier absences of monomials in a group of inversion partition polynomials
Revamped and updated on Sep 12, 2022:
Given the complex coefficients $a_n$ of some generic formal power, Taylor, Laurent or other series, say the ordinary generating functions (o.g.f.) $f(z) = z +a_1 ...
- 10.5k
1
vote
0
answers
89
views
Combinatorial models of the refined inverse Eulerian numbers
If I evaluate substitution of an infinite set of indeterminates $(c_1,c_2,c_3,\cdots)$ into the infinite set of refined Eulerian polynomials $[E]$ of OEIS A145271, I obtain the Taylor series ...
- 10.5k
1
vote
0
answers
159
views
A follow up on Bergeron's conjecture and a question
We say two polynomials satisfy $P(x)\geq Q(x)$ iff $P(x)-Q(x)$ has non-negative coefficients. Recall $(n)_q!=\prod_{j=1}^n(1-q^j)$ and the Gaussian polynomials $\binom{n}k_q=\frac{(n)_q!}{(k)_q!(n-k)...
- 43.2k
1
vote
0
answers
370
views
Combinatorial proof of a matrix equation
I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
- 10.5k
1
vote
0
answers
143
views
Polynomial interpolation of binary vectors
Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$
pairwise distinct points in $\mathbb{F}$.
Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $...
- 61
1
vote
0
answers
96
views
Polynomial composition utilizing polynomials in two different finite fields
At every $n\in\mathbb N$ (all polynomials are of degree $O(1)$) is there $g_{3,1}^{(n)},\dots,g_{3,k}^{(n)}\in\mathbb F_3[x_1,\dots,x_n]$ at $k=\mathsf{poly}(n)$ and $g_2^{(n)}\in\mathbb F_2[x_1,\dots,...
- 13.9k
1
vote
0
answers
107
views
Palindromicity of $q$-polynomials related to Catalan triangles
The present problem comes from further consideration of my earlier questions, from here and here.
Start with the following variants of Catalan triangles
$\frac{2k+1}{n+k+1}\binom{2n}{n-k}$. Now, ...
- 43.2k
1
vote
0
answers
118
views
How many residue classes mod $p$ does the image of a polynomial with integer coefficients occupy? (Status of a question of Chowla)
In his 1952 AMS Bulletin article "The Riemann zeta and allied functions" Chowla asks the following:
Given a polynomial $f$ with integer coefficients, how many residue classes mod $p$ does its image ...
- 13k
1
vote
0
answers
101
views
Construct generating functions of series of palindromic polynomials
I have a problem that is generating a series ($d=2,4,\ldots,20,\ldots$) of pairs of $4 d$-degree palindromic (self-reciprocal) polynomials.
The first three members ($d=2,4,6$) of the first pair are:
\...
- 723
1
vote
1
answer
177
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
- 10.5k
1
vote
0
answers
102
views
Nonlinear recurrence sequence systems of order one
We wish to study integer recurrence systems of the form:
$$\left\{\begin{align}
f_1(n) & = P_1\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\
f_2(n) & = P_2\big(f_1(n-1), f_2(n-1), \ldots, ...
- 786
1
vote
0
answers
207
views
Polynomial existence over finite field
Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote $e_i=(0,\dots,0,\...
- 13.9k
1
vote
0
answers
121
views
Properties and name of some polynomials
I have encountered in a problem some polynomials given by $P_k(x) = \prod_{j=0}^{k-2} (kx-j)$. I need to understand if these polynomials are known, and if they have certain special properties, as ...
- 321