0
votes
0answers
19 views

Some theorem of Newton (discrete Taylor expansion)

Let $\Delta$ be the forward difference operator, $\Delta f(x)=f(x+1)-f(x)$. Is there an elegant way to prove that for every $f\in\mathbf{Q}[x]$ (of degree $n$, say) the equality $$f(x)=\sum_{k=0}^n ...
2
votes
2answers
36 views

Proof of Pascal' identity

The identity $$\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$$ is claimed to hold (using the binomial polynomials, considered as lying in $\mathbf{Q}[x]$) for $k$ at least $1$. Proof: by the usual ...
1
vote
1answer
33 views

A certain relation of a polynomial to its coefficients

I've got a certain problem: If $A(t) = a_0+a_1t+ ...+a_Nt^N$, show that: $a_k = \frac{1}{2\pi}\int_{-\pi}^{\pi} e^{-ikx}A(e^{ix})dx$ after some rearrangements I got: $a_k = ...
2
votes
0answers
37 views

the numer of monic irreducible polynomials of degree $3$ in $\mathbb{F}_q$

I want to know how hany monic irreducible polynomials of degree $3$ there are in a field $\mathbb{F}_q$. The whole number of monic polynomials of degree three is $q^3$. Now I want to find out how ...
4
votes
3answers
160 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...
1
vote
3answers
94 views

Evaluate $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at $t=1$

I need to find a "nice" formula for the evaluation of $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at t=1, where $d_j \in \mathbb{N}$. I have already proved ...
1
vote
1answer
35 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
1
vote
1answer
39 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
1
vote
1answer
64 views

Derivation and application of Newton's identity

How is the following identity derived? $$\sum_{\ell =0}^{n-1}(-1)^\ell e_\ell s_{n-\ell}+(-1)^nne_n=0$$ Is there an example demonstrating the context in which this might be applied?
0
votes
2answers
46 views

Coefficient of polynomials

Could someone explain to me why $$ [x^{24}](1-2x^6)^{-31} = 2^4 \binom{4 + 31 - 1}{31 - 1} \, ? $$ Reads: The coefficient of $x^{24}$ in $(1-2x^6)^{-31} =$ ...
0
votes
0answers
42 views

Gosper summable

I'd like to know why the following is NOT gosper summable: $$\sum_{k\in \Bbb{Z}} \frac{p(k)}{\prod_{j=0}^{m-1}(k+a+j)}$$ where $m>0, m\in\Bbb{Z}$ and $p(k)$ is a polynomial of degree $k=m-1$.
0
votes
0answers
11 views

Q th order polynomial transform to represent all the curves in $\mathbb{R^d} $

In space $ \mathcal{X} = \mathbb{R^2} $, to get all possible quadratic curves in $ \mathcal{X} $, we need feature transform $\mathbf{z} = \Phi_2(\mathbf{x})$, where $\mathbf{x} \in \mathbb{R^2}$, and ...
0
votes
0answers
20 views

number of single sink source orientations

Given a chromatic polynomial of a graph $\chi(G)$, the number of acyclic orientations $Acy(G)$ is $(-1)^p\chi(G,-1)$ where $p$ is the number of vertices in $G$. How many orientations of $Acy(G)$ ...
2
votes
1answer
63 views

Find the number of irreducible polynomials in any given degree

For any prime $p$ find the number of monic irreducible polynomials of degree $2$ over $\mathbb Z_p$. Do the same problem for degree $3$. Generalize the above statement to higher degree ...
0
votes
1answer
34 views

computing the chromatic polynomial for a graph resulted from merging $n$ forests

Let $G=(V,E)$ be a connected undirected graph such that $E$ is the union of $n$ forests $F_1\cup F_2 \cup \dots \cup F_n$. Each forest has $V$ as its nodes and containts $k$ disconnected components. ...
0
votes
0answers
23 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
0
votes
0answers
29 views

General Expansion Theorem for Rational Generating Functions.

I am reading concrete mathematics, and in chapter 7, there is one important theorem I want to prove it(page 341). General Expansion Theorem for Rational Generating Functions. $ If R(z) = P(z)/Q(z), ...
2
votes
1answer
39 views

Integer valued polynomials in two variables

The ring of integer valued polynomials, $\{ f \in \mathbb{Q}[x] : f(\mathbb{Z}) \subseteq \mathbb{Z} \}$ is fairly well-known to be generated as Abelian group by the binomial coefficients, $f_k(n) = ...
3
votes
2answers
83 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
1
vote
2answers
70 views

How to find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / b(x)$?

Consider the sequence $c_0, c_1, c_2,\ldots$ satisfying $c_i =2\cdot 3^i − i^2\cdot(−1)^i$. Let $c(x) = c_0 + c_1x + c_2x^2 + \ldots$ Find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / ...
10
votes
1answer
162 views

Direct combinatorial proof of a sum identity on formal Lagrange polynomials

Let $k$ be a field and $K=k(x_0,x_1,\ldots, x_n)[x]$. Define $$\mathcal{L}_k(x)\triangleq \prod_{\substack{j=0\\ j\ne k}}^n\frac{x-x_j}{x_k-x_j}.$$ Is there a purely combinatorial way to show ...
0
votes
1answer
28 views

Find all divisors of an polynomial (simple combinatorics)

I want to implement the multivariate Kronecker factorization algorithm and at one stage I need to find out all divisors of a polynomial $u(y,\dots)$. I already know the irreducible factorization of ...
2
votes
5answers
64 views

stuck trying to solve nonhomogeneous recurrence relation

hello and happy new year! I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$. What I did: I ...
18
votes
1answer
182 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
2
votes
2answers
40 views

Expansion Coefficient needed

This is probably something very easy, but wth... my mind is totally stuck right now. I need to find the coefficient of $x^{11}$ of the expansion $(x^2 + 2\frac yx)^{10}$ Well I know that the answer ...
7
votes
2answers
116 views

Defining irreducible polynomials recursively: how far can we go?

Fix $n\in\mathbb N$ and a starting polynomial $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_n\ne0$. Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+a_rx^r$ such ...
2
votes
1answer
158 views

Sum of multinomial coefficients with constraints

The title doesn't reflect the question properly, since I don't know enough about combinatorics to get it right, here. Feel free to change the title. From the multinomial theorem, we can deduce, that ...
2
votes
1answer
51 views

A curious class of polynomials

In connection with some calculations involving generating functions I have encounetered the following family of polynomials $$ p_{k,N}(x) = \sum_{0<n_1<n_2<\ldots<n_k<N} ...
1
vote
0answers
60 views

Counting Polynomials Question

This is a problem on my midterm review and I'm not sure at all how to approach it. If anyone could provide me with a solution including steps, I would be truly grateful as my exam is tomorrow morning. ...
1
vote
1answer
90 views

an equality involving noncommutative variables

Suppose $x,y,z$ are three variables satisfying $yz=zy, zx=xz,xy=yzx$. Could anyone give me two (non-commutative) polynomials $f$ and $g$ in the above three variables such that the following equality ...
4
votes
4answers
391 views

Multiplying the roots of polynomials using only their integer coefficients

I am trying to write a function that takes the integer coefficients of two polynomials and returns the coefficients of a polynomial that has a root for each way you can multiply a root from the input ...
1
vote
1answer
62 views

Polynomial coefficients

How many coefficients does the n-th order polynomial in m variables have? For instance, 2nd order polynomial in 2 variables is: $p(x_1,x_2) = a_{00}x_1^0 x_2^0 + a_{01} x_1^0 x_2^1 + a_{10} ...
0
votes
1answer
125 views

A variant of the Schwartz–Zippel lemma

Let $f \in \mathbb{F}[x_1,\ldots,x_n]$ be a nonzero polynomial. Let $d_1$ be the maximum exponent of $x_1$ in $f$ and let $f_1$ be the coefficient of $x_1^{d_1}$ in $f.$ Let $d_2$ be the maximal ...
0
votes
1answer
54 views

How can I think of Multinomial Theorem's “urn” model by permutation language.

Can you explain me a little how to think of the relation with (1) and the permutaion language $$\begin{align*}\left(\begin{array}{c} n\\ k_1,k_2,\text{...},k_n ...
-2
votes
2answers
113 views

$x_1+x_2+\cdots+x_n\leq M$: Cardinality of Solution Set is $C(M+n, n)$

Show that the number of solutions in nonnegative integers of the inequality $$x_1+x_2+\cdots+x_n\leq M,$$ where $M$ is a nonnegative integer, is $C(M+n, n)$.
3
votes
1answer
441 views

Throw a die three times, and get maximum number of different sums.

The IBM Ponder This problem for July 2013 throws an 8 sided die 3 times, and can get 120 possible different positive integer sums. If all the faces have positive integer sides, what is the lowest ...
3
votes
3answers
91 views

dimension of space of polynomials

Let $\mathcal P_k^n$ be the space of all polynomials of degree $\leq k$ in $n$ variables. Prove $\dim\mathcal P_k^n = {n+k\choose k}$. I tried showing this by taking $n\in\mathbb N$ an arbitrary ...
0
votes
3answers
92 views

Newton's binomial problem

It is known that in the development of $(x+y)^n$ there is a term of the form $1330x^{n-3}y^3$ and a term of the form $5985x^{n-4}y^4$. Calculate $n$. So, I know that the binomial formula of Newton ...
1
vote
1answer
57 views

Writing a sum as a fraction

Express $$\sum^{20}_{i=2}f(x)^i$$where $$f(x)=\sum_{i\geq 1}2^{i-1}x^{3i}$$ as a fraction of polynomials $p(x)/q(x)$ and simplify as much as possible. Hmm. How to do it? Wolfram is really stupid on ...
1
vote
2answers
75 views

express Pochhammer symbol $(x)_n$ as a polynomial of order $n$ in $x$

Define $$(x)_{n}=x(x-1)(x-2)...(x-n+1)=\prod_{k=1}^{n} (x-k+1)=\sum_{k=0}^n a_k x^k$$ Q: what is the closed-form expression for $a_k$ ?
1
vote
2answers
424 views

Number of coefficients of multivariable polynomial

Let $g \in \mathbb{F}[x_1, \dots, x_n]$ be a polynomial of degree $d$ with $n$ variables. Number of its coefficients is ${n+d \choose d}$ Is there an easy proof? It clearly holds for univariate ...
2
votes
0answers
194 views

Can a linear combination of even Legendre polynomials have common real root(s) with a linear combination of odd Legendre polynomials?

I am using the following definition of Legendre Polynomials: $P_0(x)=1$, $P_1(x)=x$ and $$P_{k+1}(x)=\left(\frac{2k+1}{k+1}\right)xP_k(x)−\left(\frac{k}{k+1}\right)P_{k−1}(x)$$ Let ...
6
votes
1answer
148 views

What is the correspondence between combinatorial problems and the location of the zeroes of polynomials called?

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 "... is the ...
3
votes
2answers
142 views

Generating Function Example from class

Example: Consider the sequence $(h_n)$ where $h_n$ is the number of nonnegative integer solutions to $$a_1+a_2+a_3+a_4+a_5=n.,$$ where $a_1$ is even, $a_2$ is odd, $a_3$ is a multiple of $5$, $a_4$ is ...
13
votes
2answers
445 views

Signed Multinomial Expansion Coefficients?

I've been spending probably an undue amount of time trying to compute the coefficients of polynomials of the form $p_n(x_1, ..., x_n) = \displaystyle\prod_{\sigma \in \{ -1 , 1 \}^{n-1} } (x_1 + ...
3
votes
3answers
120 views

Find the coefficient for a term in an expression

We have the expression: $$( 1 + x^1 + x^2 + x^3 + \dots + x^{27})(1 + x^1 + x^2 + \dots + x^{14})^2$$ For this expression how do you calculate the coefficient of $x^{28}$? I know the answer is ...
2
votes
1answer
912 views

Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$

Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$ where $p$ is a prime. I'd like to start off by acknowledging that I know there are many posts relating to similar ...
2
votes
1answer
76 views

Evaluate a certain derivative

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $\{l_1,\dots,l_n\}$ a vector of natural numbers such that $l_1+l_2+\dots+l_n=N$. Let $$ h_j(x)=\prod_{i\neq j,i=1,\dots, n} ...
3
votes
0answers
210 views

Closed-form expression for sum of Vandermonde matrix elements

Given the Vandermonde matrix: $$\begin{pmatrix}1^0 & 1^1 & 1^2 & ... & 1^n \\ 2^0 & 2^1 & 2^2 & ... & 2^n \\ \vdots & \vdots & \vdots & \ddots & ...
1
vote
1answer
77 views

Polynomial Formula like Infinite Sum with non-natural index

By polynomial formula $$(\sum_{i\in m} x_i)^n=\sum_{\substack{j_i \in \mathbb{Z}^+ \\ \sum j_i=n}}\left(\begin{array}{c} n\\ j_{0},\ldots , j_{m-1} \end{array}\right)\prod_{i \in m} x_i^{j_i}$$ where ...