cp's OEIS Frontend

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.

%I A100344 #17 Jan 04 2021 19:58:03
%S A100344 1,0,1,2,0,0,6,18,12,0,0,4,72,248,300,120,0,0,1,123,1322,4800,7800,
%T A100344 5880,1680,0,0,0,126,3864,32550,121212,235200,248640,136080,30240
%N 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.
%C A100344 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".
%C A100344 For example:
%C A100344 B(0,X^2) = 1*B(0,X)
%C A100344 B(1,X^2) = 0*B(0,X)+1*B(1,X)+2*B(2,X)
%C A100344 B(2,X^2) = 0*B(0,X)+0*B(1,X)+6*B(2,X)+18*B(3,X)+12*B(4,X)
%C A100344 The coefficients may be written in a "Pascal's triangle" arrangement:
%C A100344 1
%C A100344 0 1 2
%C A100344 0 0 6 18 12
%C A100344 0 0 4 72 248 300 120
%C A100344 0 0 1 1 123 1322 4800 7800 5880 1680
%C A100344 They are always < binomial(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.
%C A100344 They have a combinatorial interpretation if i > 0. Let the set I={1,...,i} and I X I the set of pairs, M(k,i) is the number of subsets with k pairs in I X I such that any element of I appears as a coordinate in at least one pair.
%C A100344 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.
%C A100344 The M(k,i) sequence allows the enumeration of quasi-reduced ordered binary decision diagram (QROBDD) canonically associated to Boolean functions (see references).
%H A100344 J. F. Michon, J.-B. Yunes and P. Valarcher, <a href="http://www.numdam.org/item/ITA_2005__39_4_677_0/">On maximal QROBDD's of Boolean functions</a>, Theor. Inform. Appl. 39 (2005), no. 4, 677-686.
%F A100344 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.
%e A100344 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).
%Y A100344 Cf. for binomial polynomials: A080959.
%K A100344 nonn,tabl
%O A100344 0,4
%A A100344 _Jean Francis Michon_, Nov 18 2004