All Questions
Tagged with co.combinatorics polynomials
303 questions
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
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
22
votes
0
answers
550
views
Zero curves of Tutte Polynomials?
There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
- 12.7k
3
votes
0
answers
312
views
Enumerating a class of polynomials
How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...
user76479
2
votes
1
answer
147
views
Relation to Ehrhart polynomial with Uniqueness
A set of relative prime, positive integers $A = [a_1, \dots, a_d]$ describe the restricted partition function
$$
p_A(n) = \# \{(m_1,\dots,m_d)\in\mathbb{Z}^d: \textrm{ all }m_j \geq 0, \sum_{j=1}^d ...
- 909
12
votes
1
answer
934
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
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
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
5
votes
2
answers
306
views
Dickson/determinant type polynomial (updated)
For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation}
...
- 157
1
vote
1
answer
82
views
question about sets of polynomials with a special agreement guarantee
Let $\mathbb{F}$ be a finite field and $S\subset\mathbb{F}_{\leq d}[x,y]$, a set of bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$. Assume the linear span of $S$ is all ...
- 125
4
votes
1
answer
109
views
How to realize any non-crossing matching as $\mathrm{Re}[p(z)]=0$
Asymptotically any polynomial is $p(z) = z^n + O(z^{n-1})$. Therefore $\mathrm{Re}[p(z)]= r^n \cos(2\pi i \theta)$ which vanishes at $\theta = \frac{(k+ \frac{1}{2})\pi}{n}$. Those $2n$ line ...
- 22.8k
3
votes
0
answers
111
views
When does the constant term in the following expansion is nonzero?
Dyson's Theorem
The constant term in the expansion of
$$\prod_{1\leq i\neq j\leq n}\left(1-\frac{x_i}{x_j}\right)^{a_i}$$
is the multinomial coefficient
$$\frac{(a_1+\cdots+a_n)!}{a_1!\cdots a_n!},$$
...
- 1,997
9
votes
0
answers
209
views
Generating functions of real-rooted polynomials
Suppose $f_n(t)$ is a degree $n$ polynomial. Let $F(t,u) = \sum_n f_n(t)u^n$.
What conditions on $F(t,u)$ tell us that the $f_n(t)$ are real-rooted? Similarly, are there any conditions on $F(t,u)$ ...
- 91
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
4
votes
1
answer
382
views
Counting couples of square-free polynomials over finite fields
I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$:
$$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\
y_2^2=h_2(t) &...
- 41
1
vote
1
answer
172
views
Proving equivalence of two sums involving Krawtchuk polynomials and binomial co-efficients
I seem to have chanced upon a new characterization for Kravchuk polynomials.
[http://en.wikipedia.org/wiki/Kravchuk_polynomials].
To begin with, let us define the function $\omega(n,p)$ as [Assuming $...
- 11
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
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
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
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
5
votes
0
answers
205
views
Polynomials representing locally constant functions
Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...
- 20.2k
1
vote
0
answers
102
views
Nonlinear recurrence sequence systems of order one
We wish to study integer recurrence systems of the form:
$$\left\{\begin{align}
f_1(n) & = P_1\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\
f_2(n) & = P_2\big(f_1(n-1), f_2(n-1), \ldots, ...
- 786
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
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
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
11
votes
1
answer
860
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 $(i,j,...
- 1,088
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
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
0
votes
2
answers
254
views
A specific polynomial triplet question
Notation
$P_k[n]=\{$multilinear polynomials in $\Bbb R[x_1,x_2,\dots,x_{n-1},x_n]$ of total degree exactly $k\}$.
$k=1$ is just linear polynomials.
QUESTION
Is there a triplet $(p,f,g)\in (P_{k}[4]...
- 13.9k
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
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
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
1
vote
0
answers
207
views
Polynomial existence over finite field
Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote $e_i=(0,\dots,0,\...
- 13.9k
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
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
6
votes
0
answers
115
views
Recursions which define polynomials?
Let $k$ be a positive integer and let
$$h(n,k,q)=\frac{1-(1+q^{k})q^{2k(n-1)+1}+q^{2}}{1-q^{2n-1}}h(n-1,k,q)-\frac{(1-q^{k(2n-3)})(1-q^{2k(n-1)})q^2}{(1-q^{2n-1})(1-q^{2n-3})}h(n-2,k,q)$$
with ...
- 5,622
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
2
votes
0
answers
115
views
Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices
I'll give two equivalent statements of the setup, then give my questions.
Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in \{1,2,\...
- 21
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
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
1
vote
0
answers
121
views
Properties and name of some polynomials
I have encountered in a problem some polynomials given by $P_k(x) = \prod_{j=0}^{k-2} (kx-j)$. I need to understand if these polynomials are known, and if they have certain special properties, as ...
- 321
6
votes
1
answer
1k
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:
sλ...
- 1,412
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
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,292
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
0
votes
0
answers
74
views
Upper bound on number of cells created by varieties of co-dimension 1
Say I have polynomials $p_1,p_2,\dots,p_m$ in $\mathbb{R}^n$ (ie. over $n$ variables), each of degree $d$. Is there an upper bound on the number of "regions" created by the surfaces $p_i = 0$? Let's ...
- 143
2
votes
3
answers
634
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 ...
- 2,955
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
1
vote
0
answers
53
views
Distributing partially known data between n parties
Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ elements....
- 323
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