All Questions
Tagged with co.combinatorics polynomials
303 questions
1
vote
1
answer
233
views
Closed-form formula for a multivariate polynomial
Counting certain walks in threshold graphs, I came to the following independent problem. Assume that $x_1,\dots,x_a$ are independent variables and for $k\geq 2$ let
$$
P_k(x_1,\dots,x_a)=\sum_{(i_1,\...
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
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
1
vote
0
answers
89
views
Combinatorial models of the refined inverse Eulerian numbers
If I evaluate substitution of an infinite set of indeterminates $(c_1,c_2,c_3,\cdots)$ into the infinite set of refined Eulerian polynomials $[E]$ of OEIS A145271, I obtain the Taylor series ...
- 10.5k
7
votes
0
answers
344
views
Irreducibility of a palindromic polynomial
I have strong reasons to believe that the palindromic polynomial $p_n(x)$ defined by
$$p_n(x) = x^{2n}+2x^{2n-1}+3x^{2n-2}+ \cdots+ nx^{n+1}+(n+3)x^{n}+nx^{n-1}+\cdots+2x+1$$
is irreducible in $\...
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
5
votes
1
answer
351
views
"Non-associative" standard polynomials
I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if $A$ is a finite dimensional associative algebra such that $\textrm{dim}(A)<n$, then $A$ satisfies the ...
- 353
1
vote
0
answers
107
views
Palindromicity of $q$-polynomials related to Catalan triangles
The present problem comes from further consideration of my earlier questions, from here and here.
Start with the following variants of Catalan triangles
$\frac{2k+1}{n+k+1}\binom{2n}{n-k}$. Now, ...
- 43.2k
1
vote
1
answer
246
views
Coefficients of $(2+x+x^2)^n$ from trinomial coefficients
I would like to be able to express the coefficients of $(2+x+x^2)^n$ in terms of the trinomial coefficients studied by Euler, ${n \choose \ell}_2 = [x^\ell](1+x+x^2)^n$ where $[x^\ell]$ denotes the ...
- 4,589
1
vote
1
answer
235
views
How to do a multinomial theorem sum faster
For example we have this question :
Find the coefficient of $x^6$ in the following
$\frac{\left(x^{2}+x+2\right)^{9}}{20}$
So using multinomial Theorem which is this :
$\left(x_{1}+x_{2}+\cdots+x_{...
- 11
2
votes
0
answers
63
views
Finding non-commutative finite-dimensional "hypersurface" algebras
Fix a field $K$.
Call a non-commutative polynomial $f(x_i)$ whose monomial terms are all of degree at least 2 in the variables $x_i$ magic if the finite dimensional $K$-algebra $A_{f,n}:=K<x_i>/(...
- 26.5k
5
votes
1
answer
213
views
Matrix-valued periodic Fibonacci polynomials
Consider the Fibonacci polynomials $f_n(x)$, defined by the recursion $f_n(x)=xf_{n-1}(x)-f_{n-2}(x)$ with initial values $f_0(x)=0$ and $f_1(x)=1$. It is well known that the values of these ...
- 5,622
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
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
3
votes
0
answers
170
views
Stirling number bounds and polynomials and the Lambert $W$ function
Let $s(n,k)$ be the (signed) Stirling numbers of the first kind. The polynomials
$$L_n(x)=\sum_{j=1}^ns(n,n+1-j)\dfrac{x^j}{j!}$$
enter in the asymptotic expansion of the Lambert $W$ function, see for ...
- 13.1k
1
vote
0
answers
96
views
Polynomial composition utilizing polynomials in two different finite fields
At every $n\in\mathbb N$ (all polynomials are of degree $O(1)$) is there $g_{3,1}^{(n)},\dots,g_{3,k}^{(n)}\in\mathbb F_3[x_1,\dots,x_n]$ at $k=\mathsf{poly}(n)$ and $g_2^{(n)}\in\mathbb F_2[x_1,\dots,...
- 13.9k
7
votes
1
answer
321
views
Taylor's polynomials and loss of real roots
Real-rootedness, log-concavity, and unimodality are intertwined properties. It's in this light that I was prompted to ask the question below.
Suppose the roots of a polynomial $p(x)$ are all real and ...
- 43.2k
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
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
10
votes
2
answers
820
views
Simple question about polynomials
Starting from a problem in combinatorics, I ended up with a very simple problem about polynomials, which, unfortunately, I am not able to solve.
Say we work over $\mathbb C$. Fix $d>1$.
Is it ...
- 153
2
votes
1
answer
304
views
Chromatic number and graph polynomial
If $\prod_{i=1}^t x_i^{e_i}$ is a monomial, define
$$rad\biggl(\prod_{i=1}^t x_i^{e_i}\biggr)$$
to be the number of distinct (nonzero) values of $e_i$.
Now let $G$ be a simple graph with vertices ...
- 2,089
-1
votes
1
answer
65
views
A follow-up question in a proof in a paper on complete multipartite graphs
A follow-up question from the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
6
votes
0
answers
179
views
Characteristic polynomials of Cartan matrices of Lie algebras
Let $L$ be a simple Lie algebra over $\mathbb{C}$ with Cartan matrix $C_L$ (as in https://de.wikipedia.org/wiki/Cartan-Matrix )
Question 1: Is is true that the characteristic polynomial $f$ of $C_L$ ...
- 26.5k
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
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
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
1
answer
460
views
Real-rootedness of some polynomials
Denote the unsigned Stirling numbers of the first kind by $s(n,j)$.
Question. Is it true that the polynomials
$$P_n(x)=\sum_{j\geq0}s(n,j)\binom{x}j$$
have only real roots?
Note. Obviously, the ...
- 43.2k
8
votes
2
answers
386
views
Coefficients of shifted Bernoulli polynomials
I stumbled across the following curious empirical properties of the
Bernoulli polynomials $B_n(x)$. Can anyone provide a reference or
proof?
Let $k\in\mathbb{Z}$, $k\geq 2$. Then (empirically):
The ...
- 50.8k
9
votes
3
answers
408
views
An explicit representation for polynomials generated by a power of $x/\sin(x)$
The coefficients $d_{k}(n)$ given by the power series
$$\left(\frac{x}{\sin x}\right)^{n}=\sum_{k=0}^{\infty}d_{k}(n)\frac{x^{2k}}{(2k)!}$$
are polynomials in $n$ of degree $k$. First few examples:
$$...
- 2,188
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
7
votes
2
answers
268
views
How different can the constituents of an Ehrhart quasi-polynomial be?
Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
- 650
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
241
views
Integral zeros of a multivariate polynomial
Consider the multivariate polynomial
$$f(x_1,\ldots,x_m)=mk\sum_{i=1}^mx_i^2-mk(k-1)\sum_{i=1}^mx_i-\left(\sum_{i=1}^mx_i\right)^2,$$
for integers $m,k\ge2$. We are looking for integral zeros of $f$ ...
- 33
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
1
answer
142
views
Reading off top hook-lengths in partitions
Given an integer partition $\lambda$ and its Young diagram $Y_{\lambda}$, let $h_{\lambda}(i,j)$ stand for the corresponding hook length of the cell $(i,j)\in Y_{\lambda}$. Write $\lambda\vdash n$ for ...
- 43.2k
4
votes
1
answer
295
views
A Conjecture about the integral related to Chebyshev polynomial
I am interested in the following integral related to the Chebyshev polynomials
$$I_{n,m}:= \int_0^\pi \left(\frac {\sin nx}{\sin x}\right)^{m} dx,$$
where $n,m\in \mathbb{Z}^+.$
It is easy to see ...
- 767
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
0
votes
1
answer
296
views
Showing equality of Eberlein polynomials
I have thought about the following question a long time and still got no progress.
Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...
2
votes
2
answers
452
views
These polynomials are always either even or odd [duplicate]
The falling factorials are $(x)_n=x(x-1)\cdots(x-n+1)$ with $(x)_0:=1$. Define the forward shift $E$ and the discrete derivative $\delta=E-1$, respectively, by
$$Ef(x)=f(x+1) \qquad \text{and} \qquad \...
- 43.2k
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
13
votes
1
answer
602
views
Explicit forms for the roots of Eulerian polynomials
Let $E_n(z)$ be the Eulerian polynomial
$$E_n(z) = \sum_{\tau \in \mathfrak{S}_n} z^{\operatorname{des}(\tau)}$$
where $\mathfrak{S}_n$ denotes the set of all permutations of $\{1,\ldots,n\}$ and $\...
- 3,271
8
votes
3
answers
385
views
Self-reciprocal polynomials over finite fields
Let $SRMI_q(2n)$ denote the number of self-reciprocal
irreducible monic polynomials of even degree $2n$ over the finite
field $\mathbf{F}_q$ with $q$ elements. Recall that
a polynomial $p(x) \in \...
- 481
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
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
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
3
votes
0
answers
243
views
Interlacing sequences by polynomials?
Given $t=2^\ell$ where $\ell\in\mathbb N_{>0}$ and $M\in\mathbb Z$ and two sets of integers $\{a_1,\dots,a_t\}$ and $\{b_1,\dots,b_t\}$ with $0<a_1\leq \dots\leq a_t<M$ and $0<b_1\leq \...
- 13.9k
2
votes
1
answer
192
views
A Vandermonde-type system
For a prime $p$ and $a_1,\dotsc,a_n\in\mathbb F_p^\times$, consider the system of equations
$$ \begin{cases}
\begin{align}
a_1 + \dotsb + a_n &= 0 \\
a_1x_1 + \dotsb + a_nx_n &...
- 23k
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
2
votes
0
answers
112
views
Getzler's stable graphs for modular operads
In The semi-classical approximation for modular operads, Getzler displays a table at the bottom of page two enumerating certain stable graphs. (This is related to the MO-Q "Stable graphs: Feynman ...
- 10.5k
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