Path: news.mathworks.com!not-for-mail
From: "saeed kamelian" <kamelian.20@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: special matrix construction
Date: Wed, 20 Jul 2011 04:21:09 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 35
Message-ID: <j05l3l$ql1$1@newscl01ah.mathworks.com>
References: <j047f1$lpi$1@newscl01ah.mathworks.com> <j04n7c$bh2$1@newscl01ah.mathworks.com>
Reply-To: "saeed kamelian" <kamelian.20@gmail.com>
NNTP-Posting-Host: www-05-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1311135669 27297 172.30.248.37 (20 Jul 2011 04:21:09 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 20 Jul 2011 04:21:09 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 2954849
Xref: news.mathworks.com comp.soft-sys.matlab:736797

"Roger Stafford" wrote in message <j04n7c$bh2$1@newscl01ah.mathworks.com>...
> "saeed kamelian" <kamelian.20@gmail.com> wrote in message <j047f1$lpi$1@newscl01ah.mathworks.com>...
> > ........
> > I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties
> > 1-the G matrix's element are all 1 or 0
> > 2-the G matrix always have bigger number of rows than columns or at least equal to the number of columns  (#rows>=#columns)
> > 3-sum of all of elements of G(sum of all 1's) is equal to number of rows
> > 4-sum of all elements in each row of G is equal to 1
> > 5-there is at least one 1 in each column of G matrix.
> > I want to have and list all of the possible case of G matrix with that stated properties.
> > .........
> - - - - - - - - - -
>   I haven't figured out a general way to construct your matrix (except for a brute force method that would generate all n^m possibilities and then remove the numerous invalid ones.)  However I have determined that your formula for the total count of possibilities only holds valid for two columns.  Here is a general formula for finding the count.  Let c(m,n) be the count for m rows and n columns.  Then this must hold:
> 
>  c(m,n) = n^m - n/1*c(m,n-1) - n*(n-1)/(1*2)*c(m,n-2) ...
>           - n*(n-1)*(n-2)/(1*2*3)*c(m,n-3) - ... - n*c(m,1)
> 
> where c(m,1) = 1.  The coefficients of the c-values are the binomial coefficients in (a + b)^n.  This can be applied recursively to find any c(m,n).
> 
>   For example applying this formula recursively for m = 5 gives:
> 
>  c(5,1) =   1
>  c(5,2) =  30
>  c(5,3) = 150
>  c(5,4) = 240
>  c(5,5) = 120
> 
>   You will find that as m becomes large, these counts attain extremely large values.  For example, c(15,11) = 59,056,027,430,400.
> 
> Roger Stafford
Dear Roger
thanks a lot for correcting the formula for total number of count it's itself valuable alot.
but one more question is that how i could construct the all n^m possible choise. i have some ideas but they are not generel for constructing all n^m possible choise for arbitry m and n. is there any general way?

Regards