All Questions
Tagged with co.combinatorics polynomials
303 questions
18
votes
2
answers
2k
views
Can Schwartz-Zippel be formulated for commutative rings instead of fields?
The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for $(1+x^n)=1+x^n(\operatorname{...
- 2,464
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
5
votes
0
answers
220
views
Operator connected with Hermite polynomials
For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients.
$$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$
Monomials $x^k$ are mapped to $n ...
- 617
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
1
vote
0
answers
55
views
Find a common expression (parameterized by y = 1/2, 1 and 2) uniting three (rational) polynomials in k [closed]
I am seeking a common "simple" expression (preferably/presumably a sum of products of linear factors, or sum of products of low-degree factors) uniting the three polynomials (parameterized by $y=\...
- 723
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
6
votes
0
answers
257
views
Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?
Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then $$\...
- 1,327
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
12
votes
1
answer
933
views
Real-rootedness, interlacing, root-bounds of a sequence of polynomials
Problem: the number $a(n,k)$ is defined by the following recurrence
\begin{equation}
a(n,k)=(k+1)(k+2)\, a(n-1, k)+\frac{(k+1)(k+2)(k+3)}{k} \,a(n-1, k-1),
\end{equation}
with $a(1,1)=1$ and $a(n,k)=0$...
- 459
7
votes
1
answer
271
views
How "accidental" are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?
Background
What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...
- 2,372
17
votes
0
answers
420
views
Do the coefficients of these irreducible polynomials always become periodic?
Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+...
- 13.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
3
votes
2
answers
405
views
Irreducible Polynomials from a Reccurence
This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So
$$\begin{align*}
a_2 &= c
\\ a_3 &={c}^{2}-1= \...
- 30.1k
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
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
3
votes
2
answers
402
views
Counting polynomials with same coefficient sum and a given value at a point
Call an univariate polynomial $f(x) = \sum_{i=0}^{n}a_{i}x^{i} \in \Bbb{Z}[x]$ symmetric if $a_{i} = a_{n-i}$ and $a_{0} = a_{n} > 0$.
For a given $\sum_{i=0}^{n}a_{i}$ and $a_{i} \geq 0$, how ...
- 13.9k
8
votes
0
answers
407
views
When does the Lloyd polynomial have only integral roots?
For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by
$$
L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}.
$$
A well-...
- 12.1k
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
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
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
1
vote
1
answer
316
views
Combinatorics: Product Rules.
I couldn't find a way to figure this out, though it is a somewhat basic question that came up when studying the stationary phase expansion of an integral. The abstract version is the following:
I ...
- 9,853
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
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
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
15
votes
1
answer
777
views
Reconstructing a word
Let $w(a,b)$ be a word in two letter alphabet. Let $$A=\left(\begin{array}{lll}x_1 & x_2 & x_3\\\ x_4 &x_5 & x_6\\\ x_7 & x_8 & x_9\end{array}\right), B=\left(\begin{array}{lll}...
user6976
17
votes
4
answers
1k
views
A mixing property for finite fields of characteristic $2$
In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.
Let ${\mathbb F}$ be a finite field, and suppose ...
- 23k
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
5
votes
2
answers
739
views
A combinatorial formula involving the necklace polynomial
This question is motivated by the answers given to my previous one. In combinatorics, the necklace polynomials are given by
$$M(X,n)=\frac1n\sum_{d|n}\mu\left(\frac{n}{d}\right)X^d,$$
where $\mu$ is ...
- 52.3k
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
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
16
votes
0
answers
558
views
Catalan objects associated to a univariate polynomial
Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data:
a noncrossing matching on $2n$ ...
- 6,282
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
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
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
8
votes
2
answers
1k
views
What is known about zero-sets of Schur polynomials?
Consider a set S of partitions not containing the empty partition (I would be happy with, say, all the partitions of size less than k, except for the empty one).
Let $U_\lambda^{(r)}$ be the zero-...
- 81
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
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
13
votes
5
answers
6k
views
Number of spanning forests in a graph
Hello,
I have two questions that have been bugging me recently. The first is about the number of spanning forests in a graph and the second is about enumerating these with edge labels.
Q1: I am ...
- 333
3
votes
1
answer
347
views
Counting some polynomials that have a zero in $\mathbb{Z}_n[X]$
This is a question I asked on Math.SE and got only a partial answer. I hope I will have better chances here.
Given the ring of polynomials $\mathbb{Z}_n[X]$, consider $$\mathbb{P}_n = \lbrace a_0 +...
- 789
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
14
votes
3
answers
2k
views
When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)
As a natural (and expectable) extension of my earlier question:
How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, vanishing ...
- 23k
11
votes
0
answers
361
views
Positivity of polynomial sequences via generating series
In this question I address
the problem of proving the nonnegativity of a numerical sequence
$a_0,a_1,a_2,\dots$ via generating series technique. In the notation
$A(x)=\sum_{n=0}^\infty a_nx^n\ge0$ ...
- 13.5k
6
votes
4
answers
977
views
Can this nested sum be expressed in terms of generalized harmonic numbers and the cycle index polynomials of the symmetric groups?
For a paper I was working on recently I needed to find the value of the following sum:
$$S(n,k) = \sum_{i_1 = 1}^n \sum_{i_2 = i_1+1}^n \cdots \sum_{i_k=i_{k-1}+1}^n \frac{1}{i_1 i_2 \cdots i_k}.$$
...
- 3,283
1
vote
3
answers
801
views
Characteristic polynomials for $K$-Bonacci numbers: what's their name?
Fibonacci numbers are defined by the recurrence relation
$f_{n+2}=f_{n+1}+f_{n}$ and
Tribonacci numbers by
$f_{n+3}=f_{n+2}+f_{n+1}+f_{n}$
One can define, in general, K-Bonacci numbers as
$f_{n+K}=f_{...
- 373
9
votes
1
answer
1k
views
Is this sequence of polynomials well-known?
While working on a problem in p-adic Hodge theory, and needing to write down a solution to a certain equation involving p-adic power series, I stumbled across a certain sequence of polynomials. Define ...
- 37k
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
7
votes
4
answers
526
views
If the series Σ pᵃ⁽ʷ⁾·xᴵʷᴵ is rational, is Σ a(w)·xᴵʷᴵ also rational (summation over words w in a regular language)?
Let $p$ be a prime number and let $a_i$ be a sequence of natural numbers such that the series $\sum_{i=1}^\infty p^{a_i} x^i$ is rational. A warm-up question:
Question 1. Does it follow that the ...
- 3,897
16
votes
0
answers
910
views
Polynomials with presumably positive coefficients
After seeing that some positivity problems get their solutions on MO,
I am quite enthusiastic of posing my (and not only) problem of positive flavour.
In order to state it, I have to introduce the ...
- 13.5k
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
17
votes
3
answers
2k
views
Recursions which define polynomials
There are many examples (Somos sequences, special polynomials related to rational solutions of the Painleve equations) when a recurrence relation, which a priori produces a sequence of rational ...
- 13.5k