| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
The subset relation imposes a linear ordering on subsets of n things. In how many ways can this ordering be linearized? This problem is somewhat related to the 'other' problem I mentioned in connection with Golumb rulers, and to the problem of topological sorting. It is a very hard problem. For example, with three things (a, b, and c), the subsets may be ordered 48 different ways: (0 denotes the empty set, and it must always come first): 0 a b ab c ac bc abc 0 a b ab c bc ac abc 0 a b c ab ac bc abc 0 a b c ab bc ac abc 0 a b c ac ab bc abc 0 a b c ac bc ab abc 0 a b c bc ab ac abc 0 a b c bc ac ab abc plus similar orderings for each of the other 5 permutations of a, b, and c. Let the number of orderings be G(n); i.e., G(3) = 48. What is G(4)? What is the general behaviour of G(n)?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 533.1 | CLT::GILBERT | $ no /nono vaxnotes | Fri Jul 11 1986 21:22 | 5 | |
> This problem is somewhat related to the 'other' problem I mentioned > in connection with Golumb rulers, and to the problem of topological > sorting. These are notes 382 and 530, respectively. | |||||
| 533.2 | My brain hurts! | CHOVAX::YOUNG | Chi-Square | Wed Jul 16 1986 02:30 | 54 |
I guess the lack of replies is an indication of just how hard it
is, Peter.
Well, obviusly its general behaviour is bounded on the lower side
by:
N-1
TT / N! \ Where N is the # of elements
|| |------------| in the set.
|| \(N-i)!(i)!/
i=0
And even more obviously on upper side by:
N-2
( 2 )!
However, I guess that this is not too close together.
After some thought, I think that the following is a fairly close
approximation:
N-1 / /i\ \
TT | C\N/ |
|| P | |
|| | /i\ / / /i+1\ \ |
i=0 \ C\N/ + INT \ \/ C\ N / - N + i / /
WHERE:
P is the permutations function
C is the combinations function
INT is truncation to integer
and /
\/ is an ugly radical sign.
I have written a program that calulates this function up to 10:
1 : 1.00000000000000000000000000000000
2 : 2.00000000000000000000000000000000
3 : 36.0000000000000000000000000000000
4 : 14515200.0000000000000000000000000
5 : 137665519681536000000.000000000000
6 : 3.035412611846024274664686211693671E+0055
7 : 8.076496788298603617921503553321940E+0140
8 : 3.468921860443092867421657701318964E+0345
9 : 7.393249980616734873209478328969008E+0817
10 : 1.201218032197510450827494586470578E+1900
Unfortunately, I have not calculated any of the coresponding exact
values. How close is this? (In orders of magnitude)
-- Barry
| |||||
| 533.3 | Oops. | CHOVAX::YOUNG | Chi-Square | Wed Jul 16 1986 14:48 | 24 |
Re. .2:
Here is the function as I intended it:
N-1 / /i\ \
TT | C\N/ |
|| P | |
|| | /i\ / / / /i+1\ \ / \ |
i=0 \ C\N/ + INT \ \/ \ C\ N / - N + i / / 2 / /
Also the simpler function:
N
(2 - 1)
2
Seems to be fairly close, bounding the upper side.
-- Barry
| |||||
| 533.4 | G(4) | CLT::GILBERT | It's a Dusey | Tue Jul 22 1986 10:22 | 2 |
I've hand-calculated G(4) = 1615870. I don't much trust that figure, but the excersize should be useful in writing a program to compute G. | |||||
| 533.5 | my brain hurts, too! | CLT::GILBERT | It's a Dusey | Tue Jul 22 1986 19:36 | 8 |
The approximations in .2 are not too bad! (factor of 10 or so in G(4) and G(5)). G(1) = 1 G(2) = 2 G(3) = 48 G(4) = 1680384 = 2^10 * 3 * 547 = 1.6e6 G(5) = 14807804035657359360 = 2^13 * 3 * 5 * 8171 * 18223 * 809309 = 1.4e19 G(6) = ? | |||||