All Questions
Tagged with co.combinatorics polynomials
303 questions
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
7
votes
3
answers
735
views
Expanding in Fibonacci powers
Let $F_n$ denote the all-familiar Fibonacci numbers, with $F_0=0, F_1=1, F_2=1$, etc.
There is a plethora of properties for these numbers involving their sums, products, convolutions and so on. Here, ...
- 43.2k
5
votes
2
answers
205
views
Polynomial related to lognormal moments
Consider the polynomial:
$$p(x) = \sum_{k=0}^{r}(-1)^{r-k} {r \choose k} x^{k(k-1) / 2}$$
I want to show that
$$p(x) = (x - 1)^{\lceil r/2 \rceil} \, q(x)$$
That is, $(x - 1)^{\lceil r/2 \rceil}$ ...
- 153
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
2
votes
1
answer
431
views
Lagrange interpolation vs homogeneous symmetric polynomials?
This question is a follow-up on another MO query here.
Question. For $r\geq$ an integer, is it true that there exists homogeneous symmetric polynomial $P_r(x_1,\dots,x_n)$ with positive ...
- 43.2k
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
6
votes
1
answer
328
views
Expanding into monomials
Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$
Define the functions $f_n=...
- 43.2k
9
votes
1
answer
285
views
Multivariate quasipolynomials and where to find them
This question is inspired from thinking about David Speyer's question about complex variable Ehrhart theory.
In one variable, Ehrhart theory has been vastly generalized. For example it has been ...
- 85.6k
7
votes
1
answer
367
views
a new representation for Eulerian numbers?
The Eulerian numbers enjoy many different presentations among which I write the two-variable recursive definition: $A(n,0)=1$ and $A(n,k)=0$ for $k<0$ so that
$$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)....
- 43.2k
3
votes
3
answers
233
views
sequencial shift on families =flipped powers. How?
Consider the following family of functions
$$f_n(w):=\sum_{k=0}^{\infty}\frac{(-1)^{k-1}}{k!}(k+n)^{k-1}w^k.$$
QUESTION 1. Does the following hold?
$$f_n(w)=-\frac1{n(f_{-1}(w))^n}.$$
Deeper ...
- 43.2k
5
votes
1
answer
211
views
degree of a polynomial over set-partitions
Denote $(x)_t = x(x-1)(x-2)\cdots(x-t+1)$ and fix some $t_1,\dots,t_n\in\mathbb{N}$. Now consider the polynomials
$$f_n(x)=\sum_{\pi\in L[n]}(-1)^{\vert\pi\vert-1}(\vert\pi\vert-1)!\prod_{A\in\pi}(x)_{...
- 43.2k
7
votes
1
answer
232
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 43.2k
8
votes
3
answers
642
views
Combinatorial identity with connection coefficients and falling factorial $\langle i x\rangle_n$
Let $j, k ,n$ be nonnegative integers such that $0 \leq j, k \leq n \leq k +j $. Pick integer $m$ such that $0 \leq m \leq k + j - n$.
Let $\langle x \rangle_m$ denote the falling factorial $x(x-1)\...
- 1,187
16
votes
2
answers
1k
views
are these polynomials or rationals functions?
Let $x$ be a variable. Define the following family of sequences (reminiscent of Lucas polynomials) according to the rule: $P_0(x):=0, P_1(x):=1$ and for $n\geq2$ by
$$P_n(x)=xP_{n-1}(x)-P_{n-2}(x).$$
...
- 43.2k
1
vote
2
answers
190
views
Explicit Expansion for Certain Product of homogeneous Polynomials
Let $\mu \in \mathbb{N}_0^n$ be a multi index and set
$$P(X_1, \dots, X_n) = X_1^{\mu_1}(X_1 + X_2)^{\mu_2} \cdots (X_1 + \cdots +X_n)^{\mu_n} = \prod_{j=1}^n (X_1 + \cdots + X_j)^{\mu_j}.$$
Since $P$ ...
- 9,853
9
votes
2
answers
546
views
Can you tie up these Laurent sequences?
Fix an integer $k\geq3$. Define the two families of sequences $\{x_n\}$ and $\{y_n\}$ according to the rules:
$$x_n=\frac{x_{n-1}^2+x_{n-2}^2+\cdots+x_{n-k+1}^2}{x_{n-k}} \qquad n\geq k$$
and
$$y_n=\...
- 43.2k
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
2
answers
623
views
Transforming numbers of irreducible polynomials
Let $M(n)(q)$, where $q$ is a prime power and $n$ a natural number,
stand for the number of irreducible monic polynomials of degree $n$ in the
polynomial ring $\mathbf{F}_{q}[X]$ over the finite ...
- 481
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
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
4
votes
1
answer
215
views
On the number of repeated roots
Is there a number $c>0$ such that:
For any $n$ there is a polynomial $p(x) = a_nx^n +\cdots + a_0$ where the coefficients are $-1, 0$ or $1$ such that the number of repetition of the root $x=1$ ...
- 97
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
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
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
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
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
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
6
votes
2
answers
630
views
Generalized cycle index polynomial for the symmetric group
The answer to a particular calculation in quantum information theory gives me the following expression:
Given $M$ specific elements of the symmetric group $S_n$, define the polynomial
$$Z_n(\pi_1, \...
- 163
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
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
8
votes
1
answer
406
views
Determinant of symmetric Latin square
Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...
- 52.3k
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
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
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
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
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
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
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
5
votes
1
answer
631
views
Motzkin polynomials and enumeration of chord diagrams
On page 12 of the paper Enumeration of chord diagrams on many intervals and their non-orientable analogs" by Alexeev, Andersen, Penner, and Zograf is a list of polynomials which are a refinement ...
- 10.5k
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
47
votes
1
answer
4k
views
How to prove this polynomial always has integer values at all integers?
Let $m$ be any positive integer.
$$
P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}.
$$
Question: $P_m(x)$ always ...
- 2,183
14
votes
1
answer
803
views
Theorems proved using combinatorial nullstellensatz that have no other known proof
Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...
- 1,197
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
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
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
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
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
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
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
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