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