All Questions
Tagged with co.combinatorics polynomials
303 questions
10
votes
2
answers
498
views
Explicit expression for recursive sums
Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum
$$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$
...
- 34.3k
5
votes
1
answer
289
views
Cataland: Facets and partition polynomials of cluster complexes
Figure 25 on pg. 101 of "Cataland: Why the Fuss?" by Christian Stump, Hugh Thomas, and Nathan Williams depicts cluster complexes (CCs) associated with generalized $(m)$-Narayana / ...
- 10.5k
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
5
votes
1
answer
502
views
A polynomial identity related to Catalan numbers
Let $F_n^{(k)}(x)= \sum_j {\binom{n+(k-1)j}{kj} x^j}$ and $G_n^{(k)}(x)= \sum_j {\binom{n+j}{kj} x^j}.$
I am interested in the coefficients ${a_{n,k,j}}$ such that
$$G_n^{(k)}(x)=\sum_{j\geq0 }{a_{n,...
- 5,622
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
9
votes
1
answer
687
views
Number of Laurent monomials of n variables with degree at most d
Introduction: We have a question of how to calculate the number of $n$-variables Laurent monomials of degree at most $d$.
For example: If $n=2$, $d=2$ then we have 19 monomials, which are:
$x^{-2}$, $...
- 93
5
votes
1
answer
358
views
The number of polynomials on a finite group, II
This question is follow up of this MO-post.
First let us recall the necessary definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N$ and elements $a_0,...
- 41.9k
20
votes
6
answers
3k
views
What are the properties of this polynomial sequence?
Consider following polynomial sequence.
$$\begin{cases}a_{-1}=0,~a_0=1, \\a_{n+1}=x \cdot a_n \pm a_{n-1}\end{cases}$$
Here $+$ or $-$ is taken in such a way that all coefficients in $a_n$ do not ...
- 1,171
3
votes
1
answer
210
views
Powers of $2$ up to $2^{m-1}$ from a polynomial of degree $m-1$
Let $T(n,k)$ be a triangle of coefficients such that $T(n,k)\geqslant0$ for $n>0$, $0<k\leqslant n$, $0$ otherwise. Also
$$T(2n+1,1)=\frac{1}{2n+1}, T(2n,1)=0$$
$$T(n,k)=\frac{1}{n}(T(n-1,k-1)+(...
- 4,938
4
votes
0
answers
146
views
Validating a result on evaluating Jack polynomials
I am currently working through the following paper:
Lapointe L., Lascoux A., Morse J.
Determinantal Expression and Recursion for Jack Polynomials
Electron. J. Combin. 7 (2000), Notes 1.
DOI: 10.37236/...
4
votes
0
answers
134
views
Irreducibility of polynomials associated to binomial coefficients
Let $n \geq 2$.
Let $M_n$ be the $(n+1) \times (n+1)$ matrix with entries $\binom{l}{k}$ for $0 \leq l,k \leq n$ and $U_n=M_n + M_n^T$ and let $f_n(x)$ denote the characteristic polynomial of $U_n$.
...
- 26.5k
3
votes
0
answers
151
views
Extension of work by Novelli and Thibon on noncommutative symmetric functions and Lagrange inversion
(Edit May 12, 2023: I just put up a brief summary of some of my notes on the partition polynomials described below in my WordPress mini-arXiv at "As Above, So Below". It contains multinomial ...
- 10.5k
3
votes
2
answers
255
views
Inequality for Gaussian polynomials III
Recall the constructions $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ with $[0]!_q:=1$ and the $q$-binomials (Gaussian polynomials)
$$\binom{n}k_q=\frac{[n]!_q}{[k]!_q[n-k]!_q}.$$
Given two ...
- 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
15
votes
2
answers
834
views
Are there exotic polynomial bijections from $\mathbb N^d$ onto $\mathbb N$?
The Cantor bijection given by
$$(x,y)\longmapsto {x+y\choose 2}-{x\choose 1}+1$$
is a bijection from $\{1,2,3,\dotsc\}^2$ onto $\{1,2,3,\dotsc\}$.
It can be generalized to bijections $\varphi_d:\{1,2,...
- 17.9k
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
1
vote
1
answer
196
views
Largest part and length of a partition in play
If $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k)\vdash n$ is an integer partition of $n$ then $\lambda_1$ is its largest part and $k$ is its length, $\ell(\lambda)$.
Define the statistic $...
- 43.2k
8
votes
1
answer
269
views
MacMahon Master Theorem for non-matching coefficients
Let $ A$ be a complex $ n$ by $ n$ matrix and $ x_1, \dots, x_n$ be a set of commuting variables. Let $ X_i = \sum_i a_{ij}x_j$. MacMahon's Master Theorem (MMT) states that
\begin{align}
[x_1^{...
- 1,608
4
votes
4
answers
305
views
Subgraph avoiding colorings
Let $P_{H}(G, t)$ be the number of vertex colorings of a graph $G$ in $t$ colors that avoid having a monochromatic subgraph $H$. In particular, for $H$ given by a single edge we recover the usual ...
- 645
0
votes
1
answer
142
views
Vandermonde matrix with polynomials
Let us consider the simple Vandermonde matrix $V_n$ with $V_{ij} = \omega^{(i - 1)(j - 1)}$ where $\omega = e^{2i\pi/n}$. Its well known that for a column vector $A$, $VA$ is equivalent to evaluating ...
5
votes
1
answer
347
views
Counting monomials and the Catalan numbers
Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...
- 43.2k
3
votes
0
answers
203
views
Combinatorial characterizations of complex weight supports
This question is related to my last question and is originally motivated by recent advances in quantum physics.
I am looking for combinatorial characterizations of some algebraically defined families ...
- 5,409
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
9
votes
2
answers
259
views
Alon-Füredi for homogeneous polynomials
A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the ...
- 23k
3
votes
0
answers
107
views
Non-tree models of Lagrange inversion polynomials
The specific Lagrange inversion / series reversion polynomials (LIPs) I'm addressing are illustrated in OEIS A134685 with a general linear term and in Lang's pdf for A176740 with the coefficient of ...
- 10.5k
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
2
votes
1
answer
173
views
Matching polynomial, but $K_2$ is replaced by $K_3$. Have these been studied?
Given a simple graph $G=(V,E)$, we can consider matchings, $M\subseteq E$,
where $M$ is a matching iff no vertex is shared between different edges.
The number of edges in $M$ is denoted $|M|$.
The ...
- 15.8k
21
votes
2
answers
2k
views
Real rootedness of a polynomial
Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by:
$$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$
I've found with Sage that for every $...
- 1,889
4
votes
3
answers
728
views
Given the set of integers modulo $n$, can all functions from this set to itself be expressed as polynomials?
For a given $n$ is there a guaranteed way to construct any possible function from $\mathbb{Z}/n\mathbb{Z}$ to itself in terms of polynomials? Specifically, for $T = \mathbb{Z}/n\mathbb{Z}$ I'd like to ...
- 43
8
votes
2
answers
2k
views
What generalizes symmetric polynomials to other finite groups?
Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are ...
- 781
9
votes
2
answers
538
views
Counting monomials in product polynomials: Part I
This question is motivated by recent work of R P Stanley, Theorems and conjectures on some rational generating functions. Consider the polynomials
$$P_n(x)=\prod_{i=1}^{n-1}(1+x^{3^{i-1}}+x^{3^i}).$$
...
- 43.2k
4
votes
1
answer
539
views
A (mild?) question on the number of monomials
Let $[n]_q=\frac{1-q^n}{1-q}$ with $[0]_q=0$. Recall the $q$-factorials $[n]_q!=[1]_q[2]_q\cdots[n]_q$ (with $[0]_q!=1$) and the $q$-binomials
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\,[n-k]_q!}.$$
Now, ...
- 43.2k
3
votes
3
answers
397
views
Chebyshev polynomials and ballot numbers
I have asked this question a short time ago on mathstackexchange, but it has already fallen into the abyss of answered and uncommented questions. So I take the risk to ask it on mathoverflow.
Playing ...
- 7,300
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,938
21
votes
3
answers
706
views
Smallest $S\subset \mathbb C$ on which no degree $k$ polynomial always vanishes?
Say $p$ is a polynomial of degree $k$ in $\mathbb C[x]$. Then $p$ can have at most $k$ distinct roots. A somewhat obtuse way to state that is to say that among any set of $k+1$ distinct complex ...
- 1,513
1
vote
0
answers
329
views
Outlier absences of monomials in a group of inversion partition polynomials
Revamped and updated on Sep 12, 2022:
Given the complex coefficients $a_n$ of some generic formal power, Taylor, Laurent or other series, say the ordinary generating functions (o.g.f.) $f(z) = z +a_1 ...
- 10.5k
6
votes
1
answer
300
views
Explicit expression for recursive sums - II
A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $t_1,t_2,\dots$ be defined by the recurrence:
\begin{split}
g_0 &= 1, \\
g_k(t_1,t_2,\dots,...
- 34.3k
3
votes
1
answer
194
views
Checking presence of a specific term in product polynomial
I have a multivariate polynomial $P$ which is a product of $M$ low degree polynomials $p_i$
$$P(x_1, x_2, \dotsc, x_n) = \prod_{i=1}^M p_i(x_1, x_2, \dotsc, x_n)$$
where the maximum degree of each $...
- 103
2
votes
1
answer
141
views
Counting monomials and $q$-Catalan polynomials
Define $N(F)$ to be the number of monomials of a multi-variable polynomial $F$. For example $N(x^2y+3xy-y^5)=3$.
If $\mathbf{x}=(x_1,\dots,x_n)$ and $F_n(\mathbf{x})=\prod_{k=1}^n(x_1+\cdots+x_k)$ ...
- 43.2k
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
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
6
votes
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 41.9k
6
votes
0
answers
184
views
3-term recurrence relation including integral or differential operator for polynomials
Sequences of polynomials with a 3-term recurrence relations are well known for orthogonal polynomials. Do recurrence relations using differential or integral operators also appear in some theories?
I ...
3
votes
1
answer
372
views
How many ways can $N$ be written as a sum of terms in the form $2^i3^j$?
Given a positive integer $N$, let $f(N)$ be the number of ways $N$ can be decomposed as a sum of terms of the form $2^i3^j$, where each such term appears at most once in the sum. For example, $f(10) = ...
- 1,703
4
votes
2
answers
417
views
What are some bases of the polynomial ring that expand positively in the basis of binomial coefficients?
Some friends and I have a family of polynomials (in one variable) with rational coefficients and we would very much like a formula for them. Grasping at straws, we computed many examples and wrote ...
- 1,846
4
votes
0
answers
128
views
Inequality for $q$-binomials
Recall the constructions $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ with $[0]!_q:=1$ and the $q$-binomials (Gaussian polynomials)
$$\binom{n}k_q=\frac{[n]!_q}{[k]!_q[n-k]!_q}.$$
Given two ...
- 43.2k
2
votes
0
answers
345
views
Combinatorics of iterated composition of noncrossing partition polynomials
A combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin, Itzykson, Parisi, and Zuber ...
- 10.5k
9
votes
1
answer
1k
views
"Laurent phenomenon"?
Define the recurrence
\begin{align*}
n(2n+x-3)u_n(x)
&=2(2n+x-2)(4n^2+4nx-8n-3x+3)u_{n-1}(x) \\
&-4(n+x-2)(2n-3)(2n+2x-3)(2n+x-1)u_{n-2}(x)
\end{align*}
with initial conditions $u_0(x)=0$ and $...
- 43.2k
3
votes
0
answers
188
views
Reshuffling power series (aka Melvin–Morton expansion in knot theory)
I am struggling to understand a statement which follows from some change of variables in a power series. I think that the context does not really matter here, so I will put it at the end of the ...
- 601