All Questions
Tagged with co.combinatorics polynomials
303 questions
1
vote
0
answers
147
views
Counting Hamiltonian cycles in graph and finding a coefficient of polynomial
Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[...
- 25.4k
4
votes
1
answer
259
views
Why do these polynomials split almost in the middle?
Start with a palindromic sequence of integers $(a_0, a_1, \ldots, a_{n+1})$, i.e. $a_j=a_{n+1-j}$, and put $a_j:=0$ for $j<0$ and $j>n+1$. You may readily guess that the choice of the binomial ...
- 13.4k
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
3
votes
1
answer
281
views
Analytic expression for the coefficient of a multivariate polynomial
Does there exist some method for finding an analytic expression for the coefficient of $z_1^kz_2^kz_3^k$ in:
$$[(1+z_1)(1+z_2)(1+z_3)(1+z_1z_2)(1+z_1z_3)(1+z_2z_3)(1+z_1z_2z_3)]^{k}$$
or is it ...
- 1,000
1
vote
1
answer
243
views
Combinatorics and geometry underlying a refined Pascal matrix/Newton identities
The partition polynomials of OEIS A263633 give the coefficients of the power series/o.g.f of the multiplicative inverse (reciprocal) of a power series/o.g.f. and so give the Newton identities for ...
- 10.5k
2
votes
0
answers
80
views
Inequality on polynomials
Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...
- 43.2k
17
votes
2
answers
1k
views
$P(x)=P(y)$ has infinitely many integer solutions
Determine all polynomials $P(x)$ with integer coefficients such that $P(x)=P(y)$ has infinitely many integer solutions in integer $x$ and $y$ with $x \neq y$.
Choose $P(x)=a_n(x-k)^{2n}+a_{n-1}(x-k)^{...
- 501
26
votes
1
answer
2k
views
Is the derivative of $x^n + x^{n-1} + \dots + x + 1$ irreducible?
I am working on some combinatorics problems. One of my problems leads to the following question:
Is it true that the derivative of $x^n + x^{n-1} + \dots + x + 1,$ namely $nx^{n-1} + (n-1)x^{n-2} + \...
- 431
4
votes
1
answer
264
views
A question on a possible cyclic sieving phenomenon?
(This is an old MSE question from me, which did not get any answer, and when looking back seems interesting to post it here:)
Let $G$ be a finite group. Consider the set $X_G:=\cup_{H\le G} G/H$, ...
- 3,064
11
votes
1
answer
329
views
Are there three non-commutative polynomials in three variables with finite dimensional quotient?
$\newcommand\la{\langle}\newcommand\ra{\rangle}$Let $K$ be a field and $K\la x,y,z\ra$ the non-commutative polynomial ring in 3 variables.
Question 1: Are there three (fewer is probably not possible?!...
- 26.5k
3
votes
1
answer
165
views
The inverse of a symbolic matrix (with reciprocal binomials) has Laurent entries
Recalling the $q$-binomials (Gaussian polynomials). Let $[n]_q!=\prod_{j=1}^n\frac{1-q^j}{1-q}$ and
$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}$.
Now, consider the $n\times n$ matrix $\mathbf{M}...
- 43.2k
1
vote
1
answer
204
views
Interpret this matrix and its determinant
Let $n\geq1$ be an integer. Take the matrix $M(n)$, with entries, $M_{i,j}(n)=\sin\left(\frac{(i+j)\pi}2\right)$ if $i\neq j$ and $M_{i,i}(n)=x_i$.
I wish to ask (this question has been modified from ...
- 43.2k
2
votes
0
answers
117
views
A multi-variable "Fibonacci polynomial"?
There is a tremendous literature on the Fibonacci sequence, including its polynomial analogue $F_{-1}=0, F_0=1$ and
$$F_n(x)=xF_{n-1}(x)+F_{n-2} \qquad \text{for $n\geq1$}.$$
What I have found is the ...
- 43.2k
2
votes
1
answer
385
views
Determinants of striped Hankel matrices
This question is related to the matrices described in Deyi Chen's recent MO post (look at some examples there). The main difference: we are asking for a determinant evaluation instead of a permanent, ...
- 43.2k
0
votes
0
answers
84
views
Arithmetic triangles and unimodality of its rows
Let's consider the sequence of coefficients of $\prod_{i}\frac {1-x^{d_i}} {1-x}$, where $d_i$ is a monotonically increasing nonnegative integer sequence.
How to prove that the coefficients form an ...
2
votes
1
answer
213
views
Coefficient of a term in a several variable polynomial multipled with Vandermonde determinant
Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying
$$c_1 + ...
- 167
1
vote
0
answers
370
views
Combinatorial proof of a matrix equation
I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
- 10.5k
4
votes
0
answers
186
views
A problem in the spirit of P. Borwein's polynomials
A well-known conjecture (now a theorem) of P. Borwein (see Wang and Krattenthaler - An asymptotic approach to Borwein-type sign pattern theorems) states:
For all positive integers $n$, the sign ...
- 43.2k
6
votes
1
answer
242
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 43.2k
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
3
votes
0
answers
207
views
On a variation of the Vandermonde matrix
The ubiquitous Vandermonde matrix, of entries $(x_i^{j-1})_{i,j}^{1,n}$, and its determinant
$$\prod_{i<j}^{1,n}(x_j-x_i)$$
have found many utilities in Combinatorics and Physics, among other ...
- 43.2k
6
votes
1
answer
240
views
Bézout matrices and interlacing roots
Suppose that $f(t)$ is a polynomial of degree d with real roots $a_1 \leq a_2 \leq \dotsb \leq a_d$,
and $g(t)$ is a polynomial of degree $d-1$ with real roots $b_1 \leq b_2 \leq \dotsb \leq b_{d-1}$.
...
- 2,537
3
votes
0
answers
144
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
- 13.4k
0
votes
1
answer
167
views
Restrictions on exponents in multinomial formula
From the multinomial formula we have
$$(x_1 + x_2 + \dotsb + x_m)^n
= \sum_{k_1+k_2+\dotsb+k_m=n, \ k_1, k_2, \dotsc, k_m \geq 0} {n \choose k_1, k_2, \dotsc, k_m}
\prod_{t=1}^m x_t^{k_t}\,.$$
I ...
- 1
6
votes
1
answer
431
views
Maximum number of positive roots is $3$
Let $$f(x) = a+b(x+p)^t+c(x+p)^t(x+q)^t+d(x+p)^t(x+q)^t(x+r)^t,$$
where $t>1$ is any positive real number, $p>q>r>0$ or $p<q<r$ are positive integers and $a,b,c,d$ are any ...
- 233
1
vote
0
answers
159
views
A follow up on Bergeron's conjecture and a question
We say two polynomials satisfy $P(x)\geq Q(x)$ iff $P(x)-Q(x)$ has non-negative coefficients. Recall $(n)_q!=\prod_{j=1}^n(1-q^j)$ and the Gaussian polynomials $\binom{n}k_q=\frac{(n)_q!}{(k)_q!(n-k)...
- 43.2k
11
votes
1
answer
332
views
Counting monomials in product polynomials: Part II
Encouraged by the responses to my earlier MO question, here is a follow up and upgraded quest.
Let $e\geq2$ be an integer. Define the polynomials
$$P_{n,e}(x)=\prod_{i=1}^{n-1}\left(1+x^{e^{i-1}}+x^{e^...
- 43.2k
9
votes
2
answers
679
views
Сlosed formula for $(g\partial)^n$
The objective is to obtain a closed formula for:
$$
\boxed{A(n)=\big(g(z)\,\partial_z\big)^n,\qquad n=1,2,\dots}
$$
where $g(z)$ is smooth in $z$ and $\partial_z$ is a derivative with respect to $z$.
...
- 277
7
votes
0
answers
579
views
Guises of the noncrossing partitions (NCPs)
From "Noncrossing partitions in surprising locations" by Jon McCammond:
Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
- 10.5k
4
votes
1
answer
237
views
A polynomial implicitization
This is a cross-post from MSE where it did not receive a response.
For integer $n\geq 2$, consider a parameterization of the coordinates $(x_1, x_2, ..., x_{n})$ in terms of the parameters $(s_{1},s_{...
- 1,538
3
votes
1
answer
272
views
Generating function for parity in hooks
Let $\lambda\vdash n$ denote an integer partition of $n$ and $\frak{H}_{\lambda}$ be the multiset of hook lengths of $\lambda$. Further, let $o(\lambda)=\#$ of odd entries and $e(\lambda)=\#$ of even ...
- 43.2k
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
2
votes
1
answer
162
views
Maximally independent polynomial families with row symmetry
Introduction:
In the 1-dimensional case, given $m$-variables
$$\mathbf{x} = (x_1,x_2,\dots,x_m)^T,$$
the elementary symmetric polynomials $(e_k(\mathbf{x}))_{k=1}^m$ give a "symmetric basis",...
- 473
8
votes
2
answers
484
views
Inductive definition of Bernstein polynomials
For $n\in \mathbb{N}$ let $B_n$ be the linear operator taking a function $f$ on the unit interval $I=[0,1]$ to its $n$-th Bernstein polynomial $B_nf$,
$$ B_nf(x):=\sum_{k=0}^n\binom{n}{k} f\Big(\...
- 60.5k
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
5
votes
1
answer
345
views
Why does this "factorial sequence" appear in the OEIS?
For a reciprocal of a polynomial, $f = \frac{1}{p}$, we (presumably) may construct a sequence $(c_n)_{n=0}^\infty$ such that for all $N\ge 0$
$$f(k)k! = \sum_{n=0}^{N-1} c_n(k-n)! + O((k-N)!). $$
I ...
- 3,499
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
1
vote
0
answers
143
views
Polynomial interpolation of binary vectors
Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$
pairwise distinct points in $\mathbb{F}$.
Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $...
- 61
13
votes
1
answer
228
views
Recognizing algebraic independence among Schur polynomials
Given a set of integer partitions $\{\lambda_1, \lambda_2,\dots \lambda_n\}$. Are there combinatorial criteria for deciding whether the associated Schur polynomials $s_{\lambda_1}, s_{\lambda_2},\dots ...
- 85.6k
17
votes
1
answer
502
views
Irreducibility of root-height generating polynomial
The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
- 2,753
11
votes
1
answer
722
views
A closed formula for $A_n(X)=\sum\limits_{i=0}^n X^{i^2}$
I want to know if there exists a closed formula for sum $A_n(X)=\sum \limits_{i=0}^n X^{i^2}$.
I have found if $n$ is odd then $(X^n+1)\text{ | } A_n(X)$, but I don't have found a closed formula.
- 4,074
5
votes
1
answer
163
views
Polynomials vanishing on prescribed layers
Given a prime $p$ and an integer $n\ge p$, what is the smallest possible degree of a polynomial $Q\in\mathbb F_p[x_1,\dotsc, x_n]$ such that $Q$ vanishes on every vector $x\in\{0,1\}^n$ of weight $w(x)...
- 23k
6
votes
1
answer
186
views
Hook lengths, contents and recurrence
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
Define the functions
$$f_n(t):=\...
- 43.2k
0
votes
1
answer
250
views
If the coefficient of the polynomial positive
I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...
- 685
9
votes
0
answers
359
views
Factorisation of a polynomial from the Boolean algebra
Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$.
Let $M_n:=C_n+C_n^T$ and $...
- 26.5k
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
6
votes
0
answers
207
views
Parameter independence of Stanley's "content formula". Why?
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...
- 43.2k
8
votes
2
answers
565
views
integral transform of Fibonacci polynomials is integral
The Fibonacci polynomials are defined recursively by $F_0(x)=0, F_1(x)=1$ and $F_n(x)=xF_{n-1}(x)+F_{n-2}(x)$, for $n\geq2$.
While computing certain integrals, I observe the following (numerically) ...
- 43.2k
1
vote
1
answer
177
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
- 10.5k
3
votes
0
answers
195
views
Congruence for the polynomials $(t+1)^n$
An interesting polynomial congruence is given by
$$A_n(t^m)\equiv \left(\frac{1+t+\cdots+t^{m-1}}m\right)^{n+1}A_n(t) \qquad \mod (t-1)^{n+1}, \tag1$$
where $A_n(t)$ are the Eulerian polynomials with ...
- 43.2k