cp's OEIS Frontend

A051459 Number of orderings of the subsets of a set with n elements that are compatible with the subsets' sizes; i.e., if A, B are two subsets with A <= B then Card(A) <= Card(B).

%I A051459 #49 Nov 24 2023 16:00:06
%S A051459 1,1,2,36,414720,189621927936000000,
%T A051459 2156695499113014719143826715127578624000000000000
%N A051459 Number of orderings of the subsets of a set with n elements that are compatible with the subsets' sizes; i.e., if A, B are two subsets with A <= B then Card(A) <= Card(B).
%C A051459 a(7) has 127 digits and too large to include in sequence. - _Ray Chandler_, Nov 22 2003
%C A051459 From _Valentin Bakoev_, Nov 20 2017, May 17 2019: (Start)
%C A051459 a(n) is the number of possible orderings of the vectors of the n-dimensional Boolean cube (hypercube) {0,1}^n in accordance with their (Hamming) weights. For arbitrary vectors u, v of {0, 1}^n, if wt(u)<wt(v) then u precedes v in this ordering. If wt(u)=wt(v) there is no precedence by weight between them and each of them can be before the other. The formula for a(n) is explained easily by the notion "layer" of the cube - the set of all vectors of equal weights. The k-th layer of the cube is formed by all vectors of weight k. Obviously, any vector from the i-th layer precedes any vector from the j-th layer, for 0 <= i < j <= n. Hence the vectors can be rearranged only into the same layer. The k-th layer of the cube consists of C(n,k) vectors of weight k, that can be rearranged in C(n,k)! ways, for k= 0..n. Finally, the formula is obtained by applying the multiplication rule.
%C A051459 a(n) is also the number of all possible topological orders (sortings) of the directed acyclic graph (DAG) defined by the same poset: {0,1}^n and the relation weight order as it is defined and explained above.
%C A051459 Both comments correspond to the name of the sequence since the corresponding Boolean algebras are isomorphic. (End)
%H A051459 Michael De Vlieger, <a href="/A051459/b051459.txt">Table of n, a(n) for n = 0..9</a>
%H A051459 Valentin Bakoev, <a href="https://doi.org/10.1142/S179383092150021X">Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube</a>, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); <a href="https://arxiv.org/abs/1811.04421">arXiv preprint</a>, arXiv:1811.04421 [cs.DM], 2018-2020.
%F A051459 a(n) = C(n, 0)! * C(n, 1)! * C(n, 2)! * ... * C(n, n)! = A000722(n) / A022914(n).
%F A051459 log(a(n)) ~ log(2) * n * 2^n. - _Vaclav Kotesovec_, Nov 24 2023
%p A051459 a:= n-> mul(binomial(n, i)!, i=0..n):
%p A051459 seq(a(n), n=0..6);  # _Alois P. Heinz_, Nov 20 2017
%t A051459 Array[Product[Binomial[#, i]!, {i, #}] &, 7, 0] (* _Michael De Vlieger_, Nov 20 2017 *)
%o A051459 (Maxima) a(n):= prod(binomial(n,k)!,k,0,n); /* _Valentin Bakoev_, May 17 2019 */
%o A051459 (PARI) a(n) = prod(k=0, n, binomial(n, k)!); \\ _Michel Marcus_, May 18 2019
%Y A051459 Cf. A000722, A001142, A022914, A294648.
%K A051459 nonn
%O A051459 0,3
%A A051459 Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 15 2003
%E A051459 More terms from _Ray Chandler_, Nov 22 2003
%E A051459 a(0)=1 prepended by _Alois P. Heinz_, Nov 20 2017