All Questions
Tagged with co.combinatorics polynomials
302 questions
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
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
0
votes
1
answer
296
views
Showing equality of Eberlein polynomials
I have thought about the following question a long time and still got no progress.
Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...
3
votes
0
answers
264
views
Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)
The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
- 10.5k
7
votes
0
answers
579
views
Guises of the noncrossing partitions (NCPs)
From "Noncrossing partitions in surprising locations" by Jon McCammond:
Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
- 10.5k
8
votes
2
answers
2k
views
What generalizes symmetric polynomials to other finite groups?
Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are ...
- 781
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
9
votes
2
answers
679
views
Сlosed formula for $(g\partial)^n$
The objective is to obtain a closed formula for:
$$
\boxed{A(n)=\big(g(z)\,\partial_z\big)^n,\qquad n=1,2,\dots}
$$
where $g(z)$ is smooth in $z$ and $\partial_z$ is a derivative with respect to $z$.
...
- 277
2
votes
1
answer
304
views
Chromatic number and graph polynomial
If $\prod_{i=1}^t x_i^{e_i}$ is a monomial, define
$$rad\biggl(\prod_{i=1}^t x_i^{e_i}\biggr)$$
to be the number of distinct (nonzero) values of $e_i$.
Now let $G$ be a simple graph with vertices ...
- 2,089
5
votes
1
answer
453
views
Polynomial defined recursively by a resultant
Cross posting from MSE.
Definition:
For any natural number $n\ge 3$, define the polynomial $P_{n}\left(x_1,x_2,...,x_{n-1},x_{n} \right)$, with indeterminates $x_{i}$, where $i\in\{1,2,...,n-1,n\}$, ...
- 149
0
votes
1
answer
250
views
If the coefficient of the polynomial positive
I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...
- 685
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
3
votes
0
answers
243
views
Interlacing sequences by polynomials?
Given $t=2^\ell$ where $\ell\in\mathbb N_{>0}$ and $M\in\mathbb Z$ and two sets of integers $\{a_1,\dots,a_t\}$ and $\{b_1,\dots,b_t\}$ with $0<a_1\leq \dots\leq a_t<M$ and $0<b_1\leq \...
- 13.9k
17
votes
2
answers
1k
views
$P(x)=P(y)$ has infinitely many integer solutions
Determine all polynomials $P(x)$ with integer coefficients such that $P(x)=P(y)$ has infinitely many integer solutions in integer $x$ and $y$ with $x \neq y$.
Choose $P(x)=a_n(x-k)^{2n}+a_{n-1}(x-k)^{...
- 501
17
votes
1
answer
500
views
Irreducibility of root-height generating polynomial
The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
- 2,743
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
7
votes
1
answer
321
views
Taylor's polynomials and loss of real roots
Real-rootedness, log-concavity, and unimodality are intertwined properties. It's in this light that I was prompted to ask the question below.
Suppose the roots of a polynomial $p(x)$ are all real and ...
- 43.2k
2
votes
1
answer
142
views
Reading off top hook-lengths in partitions
Given an integer partition $\lambda$ and its Young diagram $Y_{\lambda}$, let $h_{\lambda}(i,j)$ stand for the corresponding hook length of the cell $(i,j)\in Y_{\lambda}$. Write $\lambda\vdash n$ for ...
- 43.2k
2
votes
1
answer
192
views
A Vandermonde-type system
For a prime $p$ and $a_1,\dotsc,a_n\in\mathbb F_p^\times$, consider the system of equations
$$ \begin{cases}
\begin{align}
a_1 + \dotsb + a_n &= 0 \\
a_1x_1 + \dotsb + a_nx_n &...
- 23k
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}$,...
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
4
votes
1
answer
295
views
A Conjecture about the integral related to Chebyshev polynomial
I am interested in the following integral related to the Chebyshev polynomials
$$I_{n,m}:= \int_0^\pi \left(\frac {\sin nx}{\sin x}\right)^{m} dx,$$
where $n,m\in \mathbb{Z}^+.$
It is easy to see ...
- 767
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
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
1
vote
1
answer
552
views
Coefficients $U_m(n,k)$ in the identity $n^{2m+1}=\sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k$
Review the main result of mathoverflow.net/questions/297900, that is the identity
\begin{equation}\label{f1}
n^{2m+1}=\sum\limits_{1\leq k \leq n}\sum\limits_{j\geq0}A_{m,j}k^j(n-k)^j,
\end{equation}
...
- 167
8
votes
1
answer
486
views
Prove that these are polynomials
Define the functions
$$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 $\frac{2k+1}{n+k+1}\binom{2n}{n-k}$ ...
- 43.2k
8
votes
1
answer
460
views
Real-rootedness of some polynomials
Denote the unsigned Stirling numbers of the first kind by $s(n,j)$.
Question. Is it true that the polynomials
$$P_n(x)=\sum_{j\geq0}s(n,j)\binom{x}j$$
have only real roots?
Note. Obviously, the ...
- 43.2k
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
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
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
7
votes
2
answers
268
views
How different can the constituents of an Ehrhart quasi-polynomial be?
Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
- 650
2
votes
2
answers
452
views
These polynomials are always either even or odd [duplicate]
The falling factorials are $(x)_n=x(x-1)\cdots(x-n+1)$ with $(x)_0:=1$. Define the forward shift $E$ and the discrete derivative $\delta=E-1$, respectively, by
$$Ef(x)=f(x+1) \qquad \text{and} \qquad \...
- 43.2k
8
votes
2
answers
386
views
Coefficients of shifted Bernoulli polynomials
I stumbled across the following curious empirical properties of the
Bernoulli polynomials $B_n(x)$. Can anyone provide a reference or
proof?
Let $k\in\mathbb{Z}$, $k\geq 2$. Then (empirically):
The ...
- 50.8k
10
votes
2
answers
820
views
Simple question about polynomials
Starting from a problem in combinatorics, I ended up with a very simple problem about polynomials, which, unfortunately, I am not able to solve.
Say we work over $\mathbb C$. Fix $d>1$.
Is it ...
- 153
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
13
votes
1
answer
602
views
Explicit forms for the roots of Eulerian polynomials
Let $E_n(z)$ be the Eulerian polynomial
$$E_n(z) = \sum_{\tau \in \mathfrak{S}_n} z^{\operatorname{des}(\tau)}$$
where $\mathfrak{S}_n$ denotes the set of all permutations of $\{1,\ldots,n\}$ and $\...
- 3,271
20
votes
6
answers
3k
views
What are the properties of this polynomial sequence?
Consider following polynomial sequence.
$$\begin{cases}a_{-1}=0,~a_0=1, \\a_{n+1}=x \cdot a_n \pm a_{n-1}\end{cases}$$
Here $+$ or $-$ is taken in such a way that all coefficients in $a_n$ do not ...
- 1,171
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
21
votes
2
answers
548
views
Do these polynomials have alternating coefficients?
In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...
- 44.4k
8
votes
3
answers
385
views
Self-reciprocal polynomials over finite fields
Let $SRMI_q(2n)$ denote the number of self-reciprocal
irreducible monic polynomials of even degree $2n$ over the finite
field $\mathbf{F}_q$ with $q$ elements. Recall that
a polynomial $p(x) \in \...
- 481
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
9
votes
3
answers
408
views
An explicit representation for polynomials generated by a power of $x/\sin(x)$
The coefficients $d_{k}(n)$ given by the power series
$$\left(\frac{x}{\sin x}\right)^{n}=\sum_{k=0}^{\infty}d_{k}(n)\frac{x^{2k}}{(2k)!}$$
are polynomials in $n$ of degree $k$. First few examples:
$$...
- 2,188
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
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
8
votes
2
answers
565
views
integral transform of Fibonacci polynomials is integral
The Fibonacci polynomials are defined recursively by $F_0(x)=0, F_1(x)=1$ and $F_n(x)=xF_{n-1}(x)+F_{n-2}(x)$, for $n\geq2$.
While computing certain integrals, I observe the following (numerically) ...
- 43.2k
11
votes
1
answer
722
views
A closed formula for $A_n(X)=\sum\limits_{i=0}^n X^{i^2}$
I want to know if there exists a closed formula for sum $A_n(X)=\sum \limits_{i=0}^n X^{i^2}$.
I have found if $n$ is odd then $(X^n+1)\text{ | } A_n(X)$, but I don't have found a closed formula.
- 4,074
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
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
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
11
votes
1
answer
339
views
Analogue of conic sections for the permutohedra, associahedra, and noncrossing partitions
Slicing cones in various ways with a plane generates conic sections identified geometrically as hyperbolas, parabolas, or ellipses and algebraically, when suitably rotated, as certain rescaled ...
- 10.5k