imfatandugly
04-21-2007, 06:38 PM
ok, got a couple problems i've been working on that I can't figure out and am so frustrated enough that i'm going to give $$$$ to the first person to answer them. The first one gos for $20(will transfer on stars or ftp). If the first one gets answered i will post the second and so on...
They are increasingly difficult (as far as I can tell).
problem 1.
Let Q(n)={set of nxn matrices with one 1 and the rest 0's in each row}
Let P(n)={set of permutations of the nxn Identity matrix}
For two matrices A,B in Q(n) we say that A ~B if there exists a matrix C in P(n) such that AC=B.
you can check that ~ is an actual equivilance relation on P(n) and serves to partition that set. I want an explicit formula for the size of P(n)/~.
This is equivilant to finding strings of length n where each character in the string can be taken from {x(1),....,x(n)} and calling one string the same as another if you can exchange the names of the variables to get the other (in a 1-1 manner).
For example if we are looking at n=3, there are 27 strings to start off with. aaa,aab,aac,aba,abb,abc,baa,bab,....,ccb,ccc
but most of these are the same i.e. aaa, bbb,ccc are "the same". aab,aac,bba,bbc,cca,ccb are the same. abc,bca,cab,acb, are the same....etc.
so under our equivilance relation there are only 5 different strings....{aaa,aab,aba,abb,abc}
If n=2 there are only 2 cases...{aa,ab}
I make it a bit easier. I'm going to give you a pascal like triangle, with an implicit formula to make it as big as you wish, your job is to find an explicit formula for the sum of the numbers in the nth row
heres what the triangle looks like
1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
This is a weighted pascals triangle where instead of a given number being the sum of the two numbers above it, the kth number in is k times the number above it plus the one to its left. Also, the top of the triangle starts at (1,1) instead of (0,0). The nth row, kth collumn gives the number of strings of length n, where k different variables are used. You get another $10 for finding an explicit formula for the nth row, kth cullumn of this triangle.
They are increasingly difficult (as far as I can tell).
problem 1.
Let Q(n)={set of nxn matrices with one 1 and the rest 0's in each row}
Let P(n)={set of permutations of the nxn Identity matrix}
For two matrices A,B in Q(n) we say that A ~B if there exists a matrix C in P(n) such that AC=B.
you can check that ~ is an actual equivilance relation on P(n) and serves to partition that set. I want an explicit formula for the size of P(n)/~.
This is equivilant to finding strings of length n where each character in the string can be taken from {x(1),....,x(n)} and calling one string the same as another if you can exchange the names of the variables to get the other (in a 1-1 manner).
For example if we are looking at n=3, there are 27 strings to start off with. aaa,aab,aac,aba,abb,abc,baa,bab,....,ccb,ccc
but most of these are the same i.e. aaa, bbb,ccc are "the same". aab,aac,bba,bbc,cca,ccb are the same. abc,bca,cab,acb, are the same....etc.
so under our equivilance relation there are only 5 different strings....{aaa,aab,aba,abb,abc}
If n=2 there are only 2 cases...{aa,ab}
I make it a bit easier. I'm going to give you a pascal like triangle, with an implicit formula to make it as big as you wish, your job is to find an explicit formula for the sum of the numbers in the nth row
heres what the triangle looks like
1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
This is a weighted pascals triangle where instead of a given number being the sum of the two numbers above it, the kth number in is k times the number above it plus the one to its left. Also, the top of the triangle starts at (1,1) instead of (0,0). The nth row, kth collumn gives the number of strings of length n, where k different variables are used. You get another $10 for finding an explicit formula for the nth row, kth cullumn of this triangle.