a couple problems WITH PRIZE FOR SOLVING

[imfatandugly]

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.

[gumpzilla]

These sequences look familiar. A bit of searching gives me: This Wiki page. Tada.

If that helps, which I bet it will, I'll take Stars transfers.

[Wyman]

You are looking for the number of equivalences on n elements. The sequence goes (as sums of your triangle rows):

1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323 [ref: http://www.research.att.com/~njas/se...nguage=english ]

I have found a closed form solution in an article from the 50's, with proof. I have a pdf, but for copyright reasons, I won't make an image and post. If you pm me your email, I will ship the pdf though. The closed form, btw, is:

[PattdownManiac]

fold early shove late ship it!

[imfatandugly]

[ QUOTE ]
These sequences look familiar. A bit of searching gives me: This Wiki page. Tada.

If that helps, which I bet it will, I'll take Stars transfers.

[/ QUOTE ]

your sn is gumpzilla I imagine?

[Duke]

I really thought that the OP was going to post some of the millenium problems with a $200k prize or something if they shared the solutions with them, and only them, first.