lambert@cwi.nl (Lambert Meertens) (01/11/88)
[ I pulled this off of sci.math. Thought it might be interesting to
the net. Steve ]
In article <3404@lifia.UUCP> comon@lifia.UUCP (Hubert Comon ) writes:
) The set {0,1}^n is ordered by (a1,...,an) >= (b1,...,bn) iff
) for all i, ai >= bi.
) What is the number of increasing mappings from {0,1}^n into {0,1} ?
2^(n.2^(n-1)). Proof: Let B = {b0,...b[2^n-1]} denote the set of all bit
strings of length n, and put, for x in B, I(x) = {y in B | y >= x}. Each
element of the Cartesian product II = I(b0)*...*I(b[2^n-1]) spells out a
different increasing mapping from B to B (for which x in B is mapped to the
component from I(x)), and all increasing mappings are represented thus.
The answer to be determined is therefore #II = PROD_(x in B)(#I(x)).
For a given x, #I(x) depends only on the number of 0-bits in x; if that
number equals z, there are 2^z elements in I(x). So, putting Z(x) = # of
0-bits in x and B(z) = {x in B | Z(x) = z}, we have
#II = PROD_(x in B)(2^Z(x))
= 2^SUM_(x in B) Z(x)
= 2^SUM_(z in {0..n}) SUM_(x in B(z)) Z(x)
= 2^SUM_(z in {0..n}) SUM_(x in B(z)) z
= 2^SUM_(z in {0..n}) z.#B(z)
= 2^SUM_(z in {0..n}) z.choose(n,z)
= 2^SUM_(z in {1..n}) z.choose(n,z)
= 2^SUM_(z in {1..n}) n.choose(n-1,z-1)
= 2^(n.(SUM_(z in {1..n}) choose(n-1,z-1)))
= 2^(n.(SUM_(z in {0..n-1}) choose(n-1,z)))
= 2^(n.2^(n-1))
--
Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl