login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A100344 Gives the i-th 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 i-th binomial polynomial: B(i,X) = X(X-1)...(X-i+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 > (i-1)^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 quasi-reduced 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, 677-686.

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^2-k+1)M(k-1, i) + i(2i-1)M(k-1, i-1) + i(i-1)M(k-1, i-2) ]/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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 15 20:47 EST 2019. Contains 319184 sequences. (Running on oeis4.)