

A100344


Gives the ith coefficient M(k,i) of the decomposition of the polynomials B(k,X^2) in the basis of all B(i,X), where B(i,X) is the ith binomial polynomial: B(i,X) = X(X1)...(Xi+1)/i! for any i > 0 and B(0,X) = 1 by definition.


0



1, 0, 1, 2, 0, 0, 6, 18, 12, 0, 0, 4, 72, 248, 300, 120, 0, 0, 1, 123, 1322, 4800, 7800, 5880, 1680, 0, 0, 0, 126, 3864, 32550, 121212, 235200, 248640, 136080, 30240
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

The binomial polynomials are a basis of the space of all polynomials and the decomposition of a polynomial in this basis is called its Mahler's expansion. So the sequence gives the Mahler's expansion of the binomial polynomials composed with "squaring".
For example:
B(0,X^2) = 1*B(0,X)
B(1,X^2) = 0*B(0,X)+1*B(1,X)+2*B(2,X)
B(2,X^2) = 0*B(0,X)+0*B(1,X)+6*B(2,X)+18*B(3,X)+12*B(4,X)
The coefficients may be written in a "Pascal's triangle" arrangement:
1
0 1 2
0 0 6 18 12
0 0 4 72 248 300 120
0 0 1 1 123 1322 4800 7800 5880 1680
They are always < binom(i^2, k) or equal to it when i^2+1 > k > (i1)^2. They are 0 if i > 2k or k > i^2.
They have a combinatorial interpretation if i > 0. Let the set I={1,...,i} and IxI the set of couples, M(k,i) is the number of subsets with k couples in IxI such that any element of I appears as a coordinate in at least one couple of the subset.
Example : M(2,2) = 6 because all subsets with 2 elements in IxI = {(1,1),(1,2),(2,1),(2,2)} satisfy the property and there are 6 such subsets.
The M(k,i) sequence allows the enumeration of quasireduced ordered binary decision diagram (QROBDD) canonically associated to boolean functions (see references).


REFERENCES

J. F. Michon, J.B. Yunes and P. Valarcher, On maximal QROBDD's of Boolean functions, Theor. Inform. Appl. 39 (2005), no. 4, 677686.


LINKS

Table of n, a(n) for n=0..35.
J. F. Michon (to be updated soon)


FORMULA

M(0, 0) = 1 and, for all i > 0, M(0, i) = 0. Let M(k, i) = 0 if all i < 0 and all k for ease. Then, for all k > 0, i > 0: M(k, i)= [(i^2k+1)M(k1, i) + i(2i1)M(k1, i1) + i(i1)M(k1, i2) ]/k.


EXAMPLE

M(2,2)=6 because B(2,X^2) = 0*B(0,X)+0*B(1,X)+6*B(2,X)+18*B(3,X)+12*B(4,X).


CROSSREFS

Cf. for binomial polynomials: A080959.
Sequence in context: A244142 A161800 A246608 * A094596 A143024 A271971
Adjacent sequences: A100341 A100342 A100343 * A100345 A100346 A100347


KEYWORD

nonn,tabl


AUTHOR

Jean Francis Michon, Nov 18 2004


STATUS

approved



