Home

Number of Coefficients

Introduction

Let  F(n,m)  =  the  number of terms in a polynomial in n variables of order m.

Then F(1, 2) = 3 since you have

A + Bx + Cx^2

(where x^2 means "x squared".)

and F(1,3) = 4:

A + Bx + Cx^2 + Dx^3.

Also, F(2, 1) = 3:

A + Bx + Cy

and F(3,1) = 4:

A + Bx + Cy + Dz.

Lemma 1

Some elementary reasoning will convince you that:
                                                                                                                                                      
F(n,  m)  =  F(n-1, m) + F(n-1, m-1) + F(n-1, m-2) + ... + F(n-1, 2) + F(n-1, 1) + 1

Lemma 2

and some basic thoughts will give you:
                                                                                                                                                      
F(n,0) = 1

F(n,1) = n+1

F(1,m) = m+1

and let's define:

F(0,m) = 1

Theorem 1

(Peter Balaam, 29/07/2003)

F(n,m) = F(n-1,m) + F(n, m-1)

Proof

Theorem 2

(Peter Balaam, 29/07/2003)

F(n,m) = F(m,n)

Proof

Theorem 3