17
votes
3answers
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 ...
9
votes
1answer
478 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 ...
6
votes
1answer
95 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 ...
7
votes
0answers
211 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 = ...
5
votes
1answer
178 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 ...
2
votes
2answers
213 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= ...
6
votes
1answer
499 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 ...
30
votes
2answers
1k 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 ...
3
votes
2answers
318 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 ...
0
votes
0answers
85 views

Enumerating certain bounded polynomials with partition type property constraints

Let $p(x) = a_{0} + a_{1}x + a_{2}x^{2} + \dots + a_{d}x^{d} + \dots + a_{2d+\alpha}x^{2d+\alpha} \in \mathbb{Z}[x]$ where $\alpha \in \{0,1\}$ with the constraints $(1)$ $0 \leq ...
3
votes
0answers
154 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 ...
0
votes
0answers
63 views

When do the even part and odd part of a hypergeometric like function have common nonnegative real root?

I encountered the following problem in my research project: Let $$f(x)=\sum_{k=0}^{\infty} a_{k} x^{k}$$ We can separate the even part $p(x^2)$ from the odd part $x q(x^2)$ and write ...
6
votes
3answers
397 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 ...
26
votes
1answer
700 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 ...
1
vote
1answer
279 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 ...
5
votes
1answer
825 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 ...
6
votes
2answers
1k 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 ...
12
votes
0answers
232 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 ...
14
votes
1answer
654 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), ...
16
votes
4answers
901 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 ...
11
votes
4answers
641 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 ...
4
votes
2answers
285 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 ...
8
votes
2answers
754 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 ...
10
votes
1answer
550 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 ...
12
votes
0answers
360 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$ ...
3
votes
0answers
97 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) & ...
2
votes
0answers
266 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 ...
0
votes
1answer
379 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 ...
8
votes
2answers
653 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 ...
2
votes
0answers
203 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 ...
21
votes
6answers
1k 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.$$ ...
6
votes
5answers
2k 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 ...
3
votes
1answer
260 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 ...
13
votes
1answer
569 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 ...
8
votes
1answer
538 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$, ...
9
votes
0answers
226 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$ ...
6
votes
4answers
573 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}.$$ ...
1
vote
3answers
427 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 ...
8
votes
1answer
769 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 ...
7
votes
4answers
492 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 ...
12
votes
0answers
603 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 ...
16
votes
3answers
1k 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 ...
10
votes
1answer
624 views

Counting colored rook configurations in the cube - when is it even?

Informal Statement In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position ...
2
votes
3answers
497 views

Variant of binomial coefficients

I've recently come across a variant of the binomial polynomials, and I'm curious if anyone has seen these before. If so, I'd love a reference, a name, etc. First recall the following. If z is a ...
5
votes
1answer
627 views

Specializations of Schur functions at consecutive integers

Given a partition λ = (λ1, λ2, ..., λn) denote with sλ the associated Schur function. There exists a nice product formula for the principal specializations: ...