fundamental principles of counting - 2nd try

dear Richard,
dear Stavros,

thanks for your valuable hints pointing me to
. recursive functions using Lisp (rjF) [I will try it]
. solving the apply-problem (sM) in case 2
. some literature (sM).

In the following I will
(1) give the solution to case 2 and
(2) have an open problem for a simple solution to case 4.

ad 1.
-----
So, here is a working function for case 2,
case 2: wOwR (combinations with order, with repetitions
        e.g. in {1,2,3,4} choose 2 elements randomly wO wR)

(%i40) Events_wOwR(n,k) := block( [S: setify(makelist(i,i,1,n))],
                           listify( apply(cartesian_product,
makelist(S,i,1,k))) )$
       Events_wOwR(4,2);
       length(%);
(%o41)
[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,
1],[4,2],[4,3],[4,4]]
(%o42) 16

ad 2.
-----
Now for cas 4 nOwR (combinations no order with repetitions,
e.g. in {1,2,3,4} choose 2 elements with nO and wR).

For teaching purpose, my idea is simply to 'cancel'
all list elements in the output of cas 2, which are
'identical at set level',
e.g. in list Events_wOwR(4,2) (see (%o41))
the pairs [1,2] ~ [2,1] are the same set([1,2])=set([2,1])={1,2},
so only one exemplar should survive the filtering.
The solution is very roughly:

(%i57) Events_nOwR (n,k)  := fullsetify( Events_wOwR(n,k) )$
       Events_nOwR(4,2);
(%o58) {{1},{1,2},{1,3},{1,4},{2},{2,3},{2,4},{3},{3,4},{4}}

.. but [1,1] --> {1}, which is not ok.

Q: how to do the right 'filtering'?

Any hints are highly welcome, hth

Wolfgang

-----Urspr?ngliche Nachricht-----
Von: Stavros Macrakis <macrakis at alum.mit.edu>
An: Wolfgang Lindner <LindnerW at t-online.de>
Datum: Freitag, 6. August 2010 16:00
Betreff: Re: [Maxima] fundamental principles of counting - 2nd try

|On Fri, Aug 6, 2010 at 06:58, Wolfgang Lindner <LindnerW at t-online.de>
wrote:
|
|> Q1: If S is a set, how to produce a sequence of k instances
|>    of S e.g. to call cartesian_product(S,S,..S)?
|>    makelist(S,i,1,k) don't work ..
|>
|
|apply(cartesian_product, makelist(S,i,1,k))
|
[..]
|In combinatory algorithms like this, taking subsets of a full cartesian
|product is bound to be inefficient.
| But maybe you only care about small cases?

Yes, so it is - teaching demos.