Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!lambert
From: lambert@cwi.nl (Lambert Meertens)
Newsgroups: comp.hypercube
Subject: Re: A counting problem in the hypercube
Message-ID: <844@hubcap.UUCP>
Date: 11 Jan 88 14:53:19 GMT
Sender: fpst@hubcap.UUCP
Lines: 33
Summary: Solution
Approved: hypercube@hubcap.clemson.edu

[ 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