All Questions
Tagged with co.combinatorics polynomials
303 questions
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
3
votes
2
answers
302
views
Narayana polynomials as numerators of Ehrhart series rational functions?
The Narayana polynomials (OEIS A001263) are the h-polynomials of the associahedra (the Stasheff polytopes) and their dual simplicial polytopes (cf. the Fomin and Reading ref in the OEIS entry).
Are ...
- 10.5k
4
votes
1
answer
139
views
Polynomial expansions via prime-base digits
Fix a prime number $p$. If $n$ is a positive integer, then denote
$$\text{$\omega_{p,k}(n):=\#$ of $k$'s in the $p$-ary expansion of $n$}$$
and the total sum of all its $p$-ary digits by
$$\Omega_p(...
- 43.2k
3
votes
0
answers
144
views
Noncrossing partitions in Hopf algebras/monoids via compositional inversion
Partition polynomials constructed from the face structures of the associahedra (OEIS A133437) and permutahedra (A133314) comprise the antipodes/compositional inverses in a Faa-di-Bruno-type Hopf ...
- 10.5k
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
9
votes
2
answers
12k
views
The number of irreducible polynomials over ${\mathbb F}_p$
Let $p$ be a prime number. The number of monic irreducible polynomial $P\in{\mathbb F}_p[X]$, in terms of the degree $d$, begins with
$${\rm irr}(1)=p,\qquad{\rm irr}(2)=\frac{p(p-1)}2,\qquad{\rm irr}(...
- 52.3k
4
votes
2
answers
623
views
Transforming numbers of irreducible polynomials
Let $M(n)(q)$, where $q$ is a prime power and $n$ a natural number,
stand for the number of irreducible monic polynomials of degree $n$ in the
polynomial ring $\mathbf{F}_{q}[X]$ over the finite ...
- 481
12
votes
2
answers
660
views
On shifted symmetric power sums
The functions $p^*_k(x)=\sum_{i=1}^N ((x_i-i)^k-(-i)^k)$ are analogues of power sum symmetric functions, called shifted symmetric by Okounkov and Olshanski. Define $p^*_{(k_1,k_2,...)}=p^*_{k_1}p^*_{...
- 2,552
28
votes
1
answer
2k
views
How many polynomial Morse functions on the sphere?
Let $f$ be a homogeneous polynomial of degree $d$ in $n$ variables. Restricted to the unit sphere $S^{n-1}$, it might or might not be a Morse function.
If $f$ is a Morse function of degree $1$, you ...
- 148k
3
votes
1
answer
233
views
What does this permutation polynomial look like?
What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...
- 13.9k
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
6
votes
1
answer
328
views
Expanding into monomials
Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$
Define the functions $f_n=...
- 43.2k
5
votes
0
answers
115
views
Progress on the result about montonicity of Kazhdan Lustzig polynomials
I am reading the paper Masato Kobayashi---Combinatorics on Bruhat Graphs and
Kazhdan-Lusztig Polynomials.
Let $P_{x,w}$ be the Kazhdan Lusztig polynomial of $W$.
There is a result about ...
- 1,875
14
votes
1
answer
803
views
Theorems proved using combinatorial nullstellensatz that have no other known proof
Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...
- 1,197
13
votes
4
answers
1k
views
Showing that a family of polynomials has positive and real roots.
Hi everybody, for my research I am dealing with the following function:
$$\alpha_n(x):=\left.\frac{\partial^{2n+1}}{\partial z^{2n+1}}\frac{\sinh(z)}{\cosh(z)-1+x}\right|_{z=0},\quad n\in \mathbb{N},...
- 131
3
votes
1
answer
138
views
Intersection of quadratic equations with planted solutions?
Suppose we have two quadratic equations in $\mathbb R[x_1,\dots, x_n]$. What is the expected dimension of their intersection?
In general what can we say about intersection of $k$ quadratics? How many ...
- 13.9k
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}$,...
17
votes
3
answers
2k
views
Where in mathematics do these polynomials appear?
Does anyone recognize the following sequence of polynomials?
$f_0(x) = x-1$
$f_1(x) = x^2-x$
$f_2(x) = x^4-2x^2+x$
$f_3(x) = x^8-3x^4+3x^2-x$
$f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$
$\vdots$
The ...
- 413
11
votes
1
answer
2k
views
Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants
Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
- 10.5k
2
votes
1
answer
196
views
Guess (or upper bound) the general formula for a double sequence
Let $t,s \geq 0$ be integers. We have the following recursive formula:
$$f(t+1,s) = f(t,s) + f(t,s-1) + \sum_{0\leq a,b,c \leq h(t):\\a+b+c = s-1}f(t,a)f(t,b)f(t,c),$$ where
$$h(t) = \frac{1}{2}3^t -\...
- 515
9
votes
1
answer
285
views
Multivariate quasipolynomials and where to find them
This question is inspired from thinking about David Speyer's question about complex variable Ehrhart theory.
In one variable, Ehrhart theory has been vastly generalized. For example it has been ...
- 85.6k
4
votes
1
answer
215
views
On the number of repeated roots
Is there a number $c>0$ such that:
For any $n$ there is a polynomial $p(x) = a_nx^n +\cdots + a_0$ where the coefficients are $-1, 0$ or $1$ such that the number of repetition of the root $x=1$ ...
- 97
5
votes
2
answers
293
views
Positivity of coefficients of a polynomial derived from Schubert polynomials
Let $W=\bigcup_{n=1}^\infty S_n$ be the union of all symmetric groups $S_n$. For an element $w\in W$, denote by $\mathfrak{S}_w$ the Schubert polynomial associated to $w$, and by $\partial_w$ the ...
- 1,066
8
votes
1
answer
406
views
Determinant of symmetric Latin square
Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...
- 52.3k
8
votes
1
answer
498
views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 x^2 + ...
- 10.5k
0
votes
0
answers
82
views
Proving Vizing's and Brooks' theorem using the polynomial approach
It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper ...
- 2,089
2
votes
1
answer
431
views
Lagrange interpolation vs homogeneous symmetric polynomials?
This question is a follow-up on another MO query here.
Question. For $r\geq$ an integer, is it true that there exists homogeneous symmetric polynomial $P_r(x_1,\dots,x_n)$ with positive ...
- 43.2k
3
votes
3
answers
233
views
sequencial shift on families =flipped powers. How?
Consider the following family of functions
$$f_n(w):=\sum_{k=0}^{\infty}\frac{(-1)^{k-1}}{k!}(k+n)^{k-1}w^k.$$
QUESTION 1. Does the following hold?
$$f_n(w)=-\frac1{n(f_{-1}(w))^n}.$$
Deeper ...
- 43.2k
7
votes
1
answer
368
views
a new representation for Eulerian numbers?
The Eulerian numbers enjoy many different presentations among which I write the two-variable recursive definition: $A(n,0)=1$ and $A(n,k)=0$ for $k<0$ so that
$$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)....
- 43.2k
5
votes
1
answer
211
views
degree of a polynomial over set-partitions
Denote $(x)_t = x(x-1)(x-2)\cdots(x-t+1)$ and fix some $t_1,\dots,t_n\in\mathbb{N}$. Now consider the polynomials
$$f_n(x)=\sum_{\pi\in L[n]}(-1)^{\vert\pi\vert-1}(\vert\pi\vert-1)!\prod_{A\in\pi}(x)_{...
- 43.2k
26
votes
0
answers
910
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
- 1,513
11
votes
0
answers
450
views
A congruence involving roots of unity
Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity.
Computational evidence ...
- 305
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
4
votes
1
answer
239
views
A discrete operator begets even/odd polynomials
Given a function $f(x)$ define the forward shift operator by $Ef(x)=f(x+1)$ and the discrete derivative $\delta f(x)=(E-1)f(x)=f(x+1)-f(x)$.
Given a partition $\lambda=(\lambda_1,\lambda_2,\dots,\...
- 43.2k
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
7
votes
0
answers
182
views
Positivity of certain polynomial coefficients
Consider the rational functions (in fact, polynomials)
$$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k}
\prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$
The numbers $\...
- 43.2k
7
votes
2
answers
789
views
"MultiCatalan numbers"
Could anyone provide a reference for the following (sort of) generalization of Catalan numbers: the multinomial coefficient
$$
\binom{2k_1+3k_2+4k_3+...}{k_1+2k_2+3k_3+...,k_1,k_2,k_3,...}
$$
is ...
- 18.4k
8
votes
0
answers
176
views
Nonzero subdeterminants conjecture: has anybody seen this anywhere?
I already posted this question on Mathematics StackExchange. A user there suggested that I rather post it on mathoverflow, since it is a research question. So here it is.
Let $m\geq2$, $n\geq1$ be ...
- 291
1
vote
2
answers
190
views
Explicit Expansion for Certain Product of homogeneous Polynomials
Let $\mu \in \mathbb{N}_0^n$ be a multi index and set
$$P(X_1, \dots, X_n) = X_1^{\mu_1}(X_1 + X_2)^{\mu_2} \cdots (X_1 + \cdots +X_n)^{\mu_n} = \prod_{j=1}^n (X_1 + \cdots + X_j)^{\mu_j}.$$
Since $P$ ...
- 9,853
6
votes
1
answer
521
views
Is every polynomial a factor of a trinomial?
We say that $T(X) \in \mathbb{Q}[X]$ is a trinomial if there exist $A,B,C \in \mathbb{Q}$ such that $T(X) = AX^n + BX^m + C$ for some $n \geq m \in \mathbb{N}$.
Is it true that for each irreducible ...
- 11.3k
7
votes
1
answer
232
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 43.2k
6
votes
2
answers
630
views
Generalized cycle index polynomial for the symmetric group
The answer to a particular calculation in quantum information theory gives me the following expression:
Given $M$ specific elements of the symmetric group $S_n$, define the polynomial
$$Z_n(\pi_1, \...
- 163
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
2
votes
1
answer
404
views
Relating face polytopes of permutohedra to integer partitions
The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
- 10.5k
7
votes
1
answer
195
views
Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?
Suppose we have a symmetric polynomial $P$ in $n$ variables.
We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}.
We can thus see $P$ as an element in $Q[x_1]...
- 15.8k
3
votes
1
answer
480
views
Find recurrence in Pascal-like triangle of polynomials
Consider an infinite, upper-triangular Toepliz-matrix, with first row $x_1,x_2,\dots,x_n.$
Then there is a sequence of determinants obtained from the $m \times m-$ sub-matrices
with upper left corner ...
- 15.8k
13
votes
1
answer
1k
views
Irreducibility of Schur polynomials
A natural question covering both this and this question would be
Let $n>2$. Describe Young diagrams $\lambda$ with at most $n$ nonempty rows (or equivalently non-increasing sequences $\lambda=(\...
- 16.9k
4
votes
2
answers
437
views
Unimodular triangulation and Ehrhart polynomials
Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function.
I am interested in what can be said about the Ehrhart polynomial when
$P$ has any of the properties
is integrally ...
- 15.8k
3
votes
1
answer
337
views
Matrices preserving interlacing/stable polynomials
Let $v_1 = (p_1,\dots,p_k)$ be a vector of interlacing polynomials, and non-negative coefficients,
i.e. $p_1,\dots,p_k$ are real-rooted, and the roots of $p_i$, $p_{i+1}$ interlace.
Let $M$ be a $k \...
- 15.8k
3
votes
1
answer
447
views
A number array related to colored necklaces and the primes
I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau ...
- 10.5k