[seqfan] Re: Number of hierarchical polynomial models on n factors

Max Alekseyev maxale at gmail.com
Thu Feb 9 05:56:48 CET 2012

I doubt there exist a simple formula.

In particular, if we bound not total degree but degree of each
variable in a monomial by k, then the monomials form a poset called
"chain product poset". Two monomials in this poset are comparable if
vector of degrees of one dominates vector of degrees of the other (as
Neil defined). Then polynomials containing with each monomial all
smaller ones are characterized by the antichain of its maximal

So the problem reduces to counting antichains in the chain product
poset. This is a subject of the paper:
which can give a taste of the problem complexity.


On Wed, Feb 8, 2012 at 3:20 PM, N. J. A. Sloane <njas at research.att.com> wrote:
> Paul, I think the question is the following:
> We are counting polynomials in n variables x_1 thru x_n
> The total degree is bounded by k (say)
> We don't care what the coeffients are
> All we care about is that if the
> polynomial contains a monomial
> x_1^e_1*x_2^e_2*...*x_n^e_n,
> then it also contains every monomial
> x_1^i_1*x_2^i_2*...*x_n^i_n
> for all 0 <= i_j <= e_j
> It should not be hard to work out a formula
> as a function of k and n
> Neil
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list