All Questions
Tagged with co.combinatorics polynomials
69 questions
13
votes
2
answers
2k
views
Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus
I was exploring some raising and lowering operators related to an infinitesimal generator for fractional integro-derivatives and found an Appell sequence of polynomials, i.e., an infinite sequence of ...
- 10.5k
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
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
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
17
votes
1
answer
502
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,753
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
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
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
20
votes
1
answer
1k
views
Symmetric polynomial from graphs
Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.
Define
$$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$
where $(i,j)$ is the directed edge ...
- 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
9
votes
0
answers
359
views
Factorisation of a polynomial from the Boolean algebra
Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$.
Let $M_n:=C_n+C_n^T$ and $...
- 26.5k
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
18
votes
3
answers
860
views
$\prod_k(x\pm k)$ in binomial basis?
Let $x$ be an indeterminate and $n$ a non-negative integer.
Question. The following seems to be true. Is it?
$$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^...
- 43.2k
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
8
votes
2
answers
484
views
Inductive definition of Bernstein polynomials
For $n\in \mathbb{N}$ let $B_n$ be the linear operator taking a function $f$ on the unit interval $I=[0,1]$ to its $n$-th Bernstein polynomial $B_nf$,
$$ B_nf(x):=\sum_{k=0}^n\binom{n}{k} f\Big(\...
- 60.5k
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
7
votes
1
answer
303
views
Large gaps between consecutive irreducible polynomials with small heights
For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then $N+2,\...
- 13.4k
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
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
3
votes
2
answers
452
views
Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture
Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a ...
- 24.9k
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
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}$,...
38
votes
6
answers
4k
views
Number of real roots of 0,1 polynomial
$0,1$ polynomial has coefficients from $\{0,1\}$.
I investigate the number of roots in such polynomials.
We are talking about real roots, and multiples are counted only once.
It was found numerically ...
- 512
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
26
votes
4
answers
2k
views
$\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?
Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$.
Then can we prove $f(x)$ is a convex ...
- 271
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
25
votes
6
answers
2k
views
Relations between sums of powers
This question is so naive that it could have been asked before on this site. If so, I'll delete it.
Among beautiful formula, I like a lot this one:
$$\left(\sum_{n=1}^Nn\right)^2=\sum_{n=1}^Nn^3.$$
...
- 52.3k
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
21
votes
2
answers
2k
views
Real rootedness of a polynomial
Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by:
$$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$
I've found with Sage that for every $...
- 1,889
16
votes
3
answers
2k
views
Periodic orbits and polynomials
There are two simple and classic enumerations that still I'm puzzled about. Let's start with a simple counting problem from a well-known dynamical system.
fact 1 Consider the "tent map" f:[0,1]→[...
- 60.5k
14
votes
2
answers
1k
views
Number of nonzero terms in polynomial expansion (lower bounds)
Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the ...
- 165
13
votes
0
answers
385
views
Are the zeros of Tutte polynomials dense in $\mathbb C^2$?
For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of $\...
- 85.6k
13
votes
1
answer
228
views
Recognizing algebraic independence among Schur polynomials
Given a set of integer partitions $\{\lambda_1, \lambda_2,\dots \lambda_n\}$. Are there combinatorial criteria for deciding whether the associated Schur polynomials $s_{\lambda_1}, s_{\lambda_2},\dots ...
- 85.6k
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
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
11
votes
4
answers
1k
views
What is the correspondence between combinatorial problems and the location of the zeroes of polynomials called?
(From MSE)
In the wikipedia article on the Italian-born American mathematician and philosopher Gian-Carlo Rota, it is stated that the one combinatorial idea he would like to be remembered for
".....
- 4,829
11
votes
0
answers
676
views
Evaluating products of cyclotomic polynomials at roots of unity
Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...
- 19.7k
10
votes
2
answers
498
views
Explicit expression for recursive sums
Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum
$$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$
...
- 34.3k
9
votes
1
answer
1k
views
"Laurent phenomenon"?
Define the recurrence
\begin{align*}
n(2n+x-3)u_n(x)
&=2(2n+x-2)(4n^2+4nx-8n-3x+3)u_{n-1}(x) \\
&-4(n+x-2)(2n-3)(2n+2x-3)(2n+x-1)u_{n-2}(x)
\end{align*}
with initial conditions $u_0(x)=0$ and $...
- 43.2k
9
votes
2
answers
538
views
Counting monomials in product polynomials: Part I
This question is motivated by recent work of R P Stanley, Theorems and conjectures on some rational generating functions. Consider the polynomials
$$P_n(x)=\prod_{i=1}^{n-1}(1+x^{3^{i-1}}+x^{3^i}).$$
...
- 43.2k
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
7
votes
0
answers
229
views
Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?
The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
- 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
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
6
votes
1
answer
431
views
Maximum number of positive roots is $3$
Let $$f(x) = a+b(x+p)^t+c(x+p)^t(x+q)^t+d(x+p)^t(x+q)^t(x+r)^t,$$
where $t>1$ is any positive real number, $p>q>r>0$ or $p<q<r$ are positive integers and $a,b,c,d$ are any ...
- 233
6
votes
1
answer
300
views
Explicit expression for recursive sums - II
A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $t_1,t_2,\dots$ be defined by the recurrence:
\begin{split}
g_0 &= 1, \\
g_k(t_1,t_2,\dots,...
- 34.3k
6
votes
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 41.8k
6
votes
1
answer
588
views
A numerical matrix of power sum polynomials
Let $p_i=x_1^i+x_2^i+\cdots+x_m^i=\sum_{k=1}^mx_k^i$ be the power sum polynomials. Then, the determinant of the $m\times m$ Hankel matrix $M_m=(p_{i+j-2})$, for $1\leq i,j\leq m$, has a neat ...
- 43.2k
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