All Questions
Tagged with enumerative-combinatorics polynomials
19 questions
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
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.1k
11
votes
1
answer
884
views
And, yet, another evaluation to Catalan numbers
Construct the $n$-tuple Cartesian product of the ternary set $X_n=\{0,1,2\}\times\cdots\times\{0,1,2\}=\{0,1,2\}^n$. Define its subset $W_n$ according to the rule (here $y=(y_1,\dots,y_n)$ is made use ...
- 43.1k
7
votes
2
answers
424
views
A sequence of polynomials related to Catalan numbers
The sequence of polynomials
$$P_n=\sum_{k=0}^{\lfloor(2n-1)/3\rfloor}
\frac{(2n-2k-1)!(2n-2k-2)!}{k!(n-k)!(n-k-1)!(2n-3k-1)!}x^k$$
satisfies apparently the identities
$$0=\sum_{j=0}^nP_{n-j}(P_j-(-x)^...
- 17.9k
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.1k
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.1k
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.1k
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.1k
3
votes
3
answers
396
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
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.1k
1
vote
0
answers
139
views
Polynomial systems and algebraic functions
An algebraic function $y(x)$ is defined as the solution of a polynomial equation of the form $p(x,y)=0$, that is one making the identity $p(x,y(x))=0$ true --- in either analytical or formal power ...
- 333
2
votes
1
answer
196
views
Guess (or upper bound) the general formula for a double sequence
Let $t,s \geq 0$ be integers. We have the following recursive formula:
$$f(t+1,s) = f(t,s) + f(t,s-1) + \sum_{0\leq a,b,c \leq h(t):\\a+b+c = s-1}f(t,a)f(t,b)f(t,c),$$ where
$$h(t) = \frac{1}{2}3^t -\...
- 515
3
votes
1
answer
233
views
What does this permutation polynomial look like?
What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...
- 13.9k
2
votes
2
answers
524
views
Questions about interlacing polynomials
If we have a finite set of real-rooted polynomials of the same degree such that any two of them have a common interlacing then does it imply that this set has a common interlacer?
Lemma $4.2$ (top of ...
- 2,246
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.1k
7
votes
1
answer
366
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.1k
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.1k
1
vote
1
answer
304
views
Truncated sums of symmetric polynomials; reference request for an algebraic derivation
EDIT: This is a case of being too wrapped up in a formulation
($e_j,p_i,$ and the like) to try something simple. It did not
occur to me to pull exp to the outside in the weeks I have
stared at this. ...
- 13k
3
votes
2
answers
402
views
Counting polynomials with same coefficient sum and a given value at a point
Call an univariate polynomial $f(x) = \sum_{i=0}^{n}a_{i}x^{i} \in \Bbb{Z}[x]$ symmetric if $a_{i} = a_{n-i}$ and $a_{0} = a_{n} > 0$.
For a given $\sum_{i=0}^{n}a_{i}$ and $a_{i} \geq 0$, how ...
- 13.9k