All Questions
Tagged with co.combinatorics polynomials
302 questions
1
vote
0
answers
108
views
Generalized identity with Stirling numbers of the second kind and falling factorials
It is known that Striling numbers of the second kind satisfy the relation
$$
\sum\limits_{k=0}^{n}{n \brace k}(x)_k = x^n.
$$
where $(x)_n$ is the falling factorials such that
$$
(x)_n = x(x-1)(x-2)\...
- 4,928
0
votes
1
answer
168
views
Partial sums of binomial coefficients and related family of polynomials
Let $a(n)$ be A302117. Here
$$
a(n) = 4(n-1)a(n-1) - \frac{1}{3}\prod\limits_{k=0}^{n-1}(2k-3), \\
a(0) = 0.
$$
Let
$$
T(n,k) = \sum\limits_{i=0}^{k} \binom{n}{i}.
$$
Let $P_n(z)$ be the family of ...
- 4,928
3
votes
1
answer
192
views
Density of Pisot polynomials
Recall that a Pisot polynomial $P=x^n+ a_{n-1}x^{n-1}\ldots a_1$ has integer coefficients, a real root $x_1>1$ and all other roots $|x_i|<1$ for $1\leq i \leq n$. One key result is that $\{(...
- 680
0
votes
1
answer
98
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 15.8k
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,928
0
votes
0
answers
60
views
Algorithm for $q$-Bell numbers
Let $T(n,k)$ be A126347 (i.e., triangle, read by rows, with row polynomials $B(n, q)$). Here
$$
B(n, q) = \sum\limits_{k=0}^{n-1}\binom{n-1}{k}B(k, q)q^k, \\
B(0, q) = 1.
$$
Start with vector $\nu$ of ...
- 4,928
7
votes
0
answers
208
views
How biased is $(x_i x_j)_{i,j}$, $x_i\in \mathbb{F}_2$?
Let $N = \frac{n (n-1)}{2}$. Let $V$ be the $N$-dimensional vector space over $\mathbb{F}_2$ consisting of tuples $(x_{(i,j)})_{1\leq i <j \leq n}$, $x_{(i,j)}\in \mathbb{F}_2$. Let $S$ be the set ...
- 20.2k
3
votes
0
answers
213
views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$.
For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 15.6k
5
votes
0
answers
183
views
On the polynomials $\sum_{k=0}^n\binom{n+k}k^m q^k$
A sequence of polynomials
$$P_0(q),\ P_1(q),\ P_2(q),\ \ldots$$
with real coefficients is called $q$-log-convex if for each $n=1,2,3,\ldots$ every coefficient of the polynomial $P_{n+1}(q)P_{n-1}(q)-...
- 15.6k
0
votes
0
answers
121
views
Closed form of coefficients of a finite field polynomial
I want to find a valid polynomial for a finite field $\mathbb{Z}_p[x]_{f(x)}$ with $d=deg(f(x))$. For this definition to hold, it can be deduced that $p$ must be prime and the polynomial $f(x)$ ...
- 47
3
votes
1
answer
159
views
Proving that two sequences of polynomials defined over partitions are inverse to each other
For any fixed $c>0$ consider the polynomials
\begin{align*}
& p_n(X_1,X_2,\ldots) := \frac{n!}{c} \sum\limits_{b=1}^n \frac{c^b}{b!(n+1-b)!} \sum\limits_{\substack{l_1,\ldots,l_b \geq 1 \\ ...
- 1,295
2
votes
1
answer
310
views
Generating function for A300483 (related to Chebyshev polynomial of first kind)
Let $a(n)$ be A300483. Here
$$
a(n) = 2\int\limits_{t \geqslant 0}T_n\left(\frac{t+1}{2}\right)\exp(-t)\,dt.
$$
where $T_n(x)$ is $n$-th Chebyshev polynomial of first kind.
Let $b(n)$ be an integer ...
- 4,928
2
votes
0
answers
49
views
Skew Jack polynomial when the Jack parameter is zero
According to Macdonald's book, when the Jack parameter $\alpha$ is $0$,then the Jack $P$-polynomial $P_\lambda(\alpha)$ is the elementary symmetric polynomial $e_{\lambda'}$ where $\lambda'$ is the ...
- 2,560
0
votes
0
answers
96
views
"Degenerate" Schur polynomials
Let's say that a Schur polynomial is degenerate if its number of variables is less than the weight of the partition it is associated to. For example, according to Sage, the Schur polynomial of the ...
- 2,560
2
votes
0
answers
70
views
Property of a family of simple polynomials related to the A329369
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 4,928
1
vote
0
answers
164
views
Combinatorial question related to Hankel-type matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $n\geq 2, d$ be positive integers. I would like a lower bound on the largest integer $r$ for which the following property holds:
For any ...
- 980
0
votes
0
answers
36
views
Sufficient conditions for a polynomial function to have the same critical points as its symmetrized version
Are there any sufficient conditions known for a polynomial function (of many variables) to have the same critical points as its symmetrized version (with respect to all variables)?
This question has ...
- 765
3
votes
1
answer
169
views
Eigenvalues of the Jack polynomials for the Calogero-Sutherland operator
The Calogero-Sutherland operator on the space of homogeneous symmetric polynomials in $n$ variables is defined by
$$
\frac{\alpha}{2}\sum_{i=1}^n x_i^2\frac{\partial^2}{\partial x_i^2} + \frac{1}{2}\...
- 2,560
3
votes
2
answers
451
views
Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture
Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a ...
- 24.9k
0
votes
0
answers
37
views
Largest root of the Adjacency matrix of two graphs (comparison)
Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial:
$$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...
- 199
2
votes
1
answer
372
views
On properties of sums involving the floor function
During my research on properties of fractional part and integer part functions, I was led to consider the function of two variables $f(n,k)=\frac{2^{k}+1}{2^{ n}+1}\left\lfloor \frac{2^{n}+1}{2^{k}+1}\...
- 611
9
votes
2
answers
344
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
- 667
2
votes
0
answers
123
views
Alon Tarsi reaches its lower bound for complete multipartite graphs
Consider a complete multipartite graph $G$ with $k$ $(k\ge2)$ parts with equal number of vertices $n$, where $n$ is even. If $k=2$, it is a well known result that the Alon-Tarsi number (ATN)(The ...
- 2,089
4
votes
0
answers
82
views
Combinatorial interpretation of a pfaffian identity?
Let $n$ be a positive even integer. We introduce three types of skew-symmetric matrices, $A_{n+2}$, $B_n$ and $C_n$ (the subscript denotes the dimension of the matrices)
in terms of the variables $z_1,...
- 451
3
votes
0
answers
240
views
On thickness of binary polynomials
OEIS A169945 introduces the concept of thickness of a polynomial as the magnitude of the largest coefficient in the expansion of the square of the polynomial. Considering the $2^{n+1}$ polynomials $p(...
- 791
2
votes
0
answers
64
views
Eulerian polynomial from Bruhat interval - h* of something?
Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...
- 15.8k
2
votes
0
answers
69
views
Set partitions with big blocks - real-rooted polynomials?
The polynomials
$$
T_n(t) := \sum_{\pi \in \text{Set Partitions}(n)} t^{\text{blocks}(\pi)} = \sum_{k=1}^n S(n,k)t^k
$$
with $S(n,k)$ being the Stirling numbers of the second kind, are well-known to ...
- 15.8k
1
vote
0
answers
63
views
Factorization of the symmetric function identity $E(t)=1/H(t)$ with the refined Euler characteristic polynomials of associahedra / Lagrange inversion
I've come across two matrix identities, flagged with daggers below, relating the two sets of elementary and complete homogeneous symmetric polynomials/functions via the two sets of refined Lah and ...
- 10.5k
38
votes
6
answers
4k
views
Number of real roots of 0,1 polynomial
$0,1$ polynomial has coefficients from $\{0,1\}$.
I investigate the number of roots in such polynomials.
We are talking about real roots, and multiples are counted only once.
It was found numerically ...
- 512
17
votes
1
answer
687
views
Multiply an integer polynomial with another integer polynomial to get a "big" coefficient
I have copied this question from StackExchange, in the hope that some experts here can provide some relevant insight. Thanks to Greg Martin for improving the question.
Given $f(x) = a_0 + a_1 x + a_2 ...
- 823
2
votes
0
answers
140
views
Asymptotics of a "non-constant order" quadratic recurrence relation in two variables
Consider the following recurrence relation defined for two integer variables $H,n \geq 0$:
\begin{equation}
\gamma(H,n) = \sum_{K=0}^{\lfloor H/2 \rfloor} \gamma(K,n-1) \gamma(H-K,n-1)
\end{equation}
...
- 143
9
votes
1
answer
788
views
Sequence of real-rooted polynomials
I've been interested in proving a log-concavity result via proving that certain family of polynomials is real-rooted. By performing a sequence of transformations, I can reduce that problem to proving ...
- 1,889
2
votes
2
answers
210
views
An identity for the ratio of two partial Bell polynomials
Let $B_{\ell,m}(x_1,x_2,\dotsc,x_{\ell-m+1})$ denote the Bell polynomials of the second kind (or say, partial Bell polynomials, (exponential) partial Bell partition polynomials). I knew that
the ...
- 1,091
4
votes
1
answer
216
views
Any conjectures about Jack Littlewood-Richardson coefficients when Schur LR > 1?
Stanley famously conjectured ("Some combinatorial properties of Jack symmetric functions" Adv. in Math. (77) 1989, doi:10.1016/0001-8708(89)90015-7, MR1014073, Zbl 0743.05072) that the Jack ...
- 335
4
votes
0
answers
263
views
Cosine Modulo $p$?
Consider the integers modulo a prime $p$. I'm looking for a nice polynomial function that acts as a sort of "cosine" on the integers modulo $p$. Specifically, I'm looking for solutions to ...
- 591
0
votes
0
answers
116
views
Multivariate polynomial representations of the infinite dihedral group
The presentation given in Wikipedia for the infinite dihedral group is
$$\langle r,s\mid s^2 =1, srs = r^{-1}\rangle.$$
Let $[R]$ denote the infinite set of reciprocal partition polynomials $R_n(u_1,...
- 10.5k
1
vote
1
answer
133
views
Constant term of a power modulo a polynomial
I'm interested in the constant term of $$(x+k)^m \in F_p[x]$$
modulo a polynomial $q(x)$ over the field $F_p$. The polynomial $q(x)$ is relatively simple in practice, take $q(x) = x^6 -2x^3+3$, for an ...
- 591
5
votes
1
answer
369
views
Primitive recursive bounds for multidimensional polynomial vdW / HJ
In Shelah's paper 679, he proves primitive recursive bounds for the polynomial Hales-Jewett theorem and thus for the polynomial van der Waerden theorem.
How about for the multidimensional polynomial ...
- 383
1
vote
0
answers
69
views
Simplification of computing $f(n,z)$
Let
$$
s(n,z)=\sum\limits_{j=0}^{n}L(n,j,z)
$$
where
$$
L(n,j,z)=\sum\limits_{p=0}^{n-j-1}f(p,z)L(n-j-1,p,z), \\
L(n,n,z)=1
$$
Now let $s(n,z)$ be an arbitrary function such that $s(0, z)=1$. It means ...
- 4,928
2
votes
0
answers
73
views
An iterative formula for the Kreweras-Voiculescu polynomials (reference request)
Let
$$N(x) = 1 + \sum_{k \ge 1} N_k(h_1,h_2,...,h_k) \;x^k$$
$$ = 1 + h_1 x + (h_1^2 + h_2) x^2 + (h_1^3 + 3h_1h_2 + h_3)x^3 + (h_1^4 + 6 h_2 h_1^2 + 4 h_3 h_1 + 2 h_2^2 + h_4) x^4 + \cdots$$
be the ...
- 10.5k
5
votes
1
answer
268
views
Enumerating monomials in Schur polynomials
Let $s_{\lambda}(x_1,\dots,x_k)$ be the Schur polynomial associated to the partition $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_k>0)$.
Among the many things involved with these ...
- 43.2k
6
votes
1
answer
288
views
The combinatorics of the Nullstellensatz for the variety of nilpotent matrices
Let $H_n$ denote the set of $n \times n$ nilpotent matrices with complex entries. The set $H_n$ may be regarded as an algebraic variety. Indeed, consider the polynomial ring $\mathbb{C}[A_{i,j} : 1 \...
- 484
1
vote
0
answers
216
views
Classical and free cumulants, symmetric functions, and inverses (references), related to associahedra, parking functions, noncrossing partitions
Looking for references for one or more of the following four sets of partition polynomials 1a) through 4a), particularly those which present geometric / topological combinatorial interpretations.
...
- 10.5k
1
vote
0
answers
180
views
Applications of hyperbolic polynomials?
The recently posted MO-Q "Positivity of the coefficients of Taylor series associated to the Riemann hypothesis" (see also this MO-Q) has re-kindled my interest in hyperbolic polynomials--...
- 10.5k
1
vote
0
answers
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
2
votes
0
answers
68
views
Sampling theorems for partition polynomials (associahedra, noncrossing partitions / parking functions)
Define the associahedra partition polynomial
$$
\begin{split}
A(x) &= 1 + A_1(u_1) z + A_2(u_1,u_2) z^2 + A_3(u_1,u_2,u_3) z^3 + \cdots\\
& \qquad\qquad = 1 + \sum_{n \geq 1} A_n(u_1,...,u_n) ...
- 10.5k
3
votes
1
answer
190
views
Can the equation $1+z+z^q=z^n$ have multiple complex roots $z$?
It is proved here that the equation $1+z+z^2=z^n$ have no multiple complex roots.
Q. Let us consider the equation $1+z+z^q=z^n$ where $q$ and $n$ are natural numbers with $1<q<n$. Any ...
- 4,058
6
votes
1
answer
588
views
A numerical matrix of power sum polynomials
Let $p_i=x_1^i+x_2^i+\cdots+x_m^i=\sum_{k=1}^mx_k^i$ be the power sum polynomials. Then, the determinant of the $m\times m$ Hankel matrix $M_m=(p_{i+j-2})$, for $1\leq i,j\leq m$, has a neat ...
- 43.2k
0
votes
0
answers
109
views
Applications of Jack polynomials
I developed four libraries (Julia, R, Python, Haskell) for the computation of Jack polynomials. I developed them for fun because I found this was programmatically interesting. But now I'd like them to ...
- 2,560
2
votes
1
answer
205
views
Catalan and path pairs in polynomials
Define $\mathbf{K}_n$ to be the set of all $(2n+1)$-tuple sequences $\mathbf{a}=(a_0,a_1,\dots,a_{2n})\in\{-1,1\}^{n+1}$ satisfying: (a) there are $n$ occurrences of $-1$ and $n+1$ of $+1$; (b) all ...
- 43.2k