The twelve signs of the horoscope (AQUARIUS, ARIES, and so on) run a race along the Zodiac. In how many different ways can the race end, if ties are possible?

I get 28,091,567,595 ways they can cross the finish line, best explained by the table below, produced by two stages of computer program.

The table lists the 77 ways in which the groups may be formed without regard to which zodiacal signs are members thereof.  The ways column lists how many ways the zodiacal signs can occupy that configuration of sets. The factor specifies how many ways those sets of people (each set being a cohort of tied individuals) can be rearranged.  I'll start by describing the first few lines.

The first row is all 1's, indicating each person crossed the finish line individually--there were no ties, so each group consisted of one member. There were 12! = 479001600 ways of populating the groups with individual members. Once this is done, there's no further rearranging needed, so the total ways for this is just the 12!.

The second row represents 10 individuals crossing the finish line separately and one pair crossing together. There are 12! / 2! ways of populating the groups, as the last two positions are indifferent as to the order of entry of their individual members.  But there are 11 positions that the group of two can have: the illustrated line has them tied for last place (places 11 and 12), but they may be tied for 1 and 2, or 2 and 3, or 3 and 4, etc., so we need to multiply by a factor of 11 to get the total ways accounted for by this line.

To take a more complicate case, consider the line

 1  1  1  1  2  2  4                        4989600  105    523908000

 
The 4989600 represents just the ways that individuals can come in places 1 through 4, with a tie for 5th and 6th place, a tie for 7th and 8th, as well as a 4-way tie for 9th thru 12th. This is 12!/(2!2!4!), as within the two groups of 2 and one group of 4, order doesn't matter.  But again, the 1,1,1,1,2,2,4 could itself be rearranged, into 7!/(4!2!) = 105 ways, each with 4989600 ways of filling the members' names, so the total ways is 4989600*105 = 523908000.

The total of the 77 total ways is 28,091,567,595, which is the answer.

                                              ways factor  total ways
 1  1  1  1  1  1  1  1  1  1  1  1       479001600    1    479001600
 1  1  1  1  1  1  1  1  1  1  2          239500800   11   2634508800
 1  1  1  1  1  1  1  1  1  3              79833600   10    798336000
 1  1  1  1  1  1  1  1  2  2             119750400   45   5388768000
 1  1  1  1  1  1  1  1  4                 19958400    9    179625600
 1  1  1  1  1  1  1  2  3                 39916800   72   2874009600
 1  1  1  1  1  1  1  5                     3991680    8     31933440
 1  1  1  1  1  1  2  2  2                 59875200   84   5029516800
 1  1  1  1  1  1  2  4                     9979200   56    558835200
 1  1  1  1  1  1  3  3                    13305600   28    372556800
 1  1  1  1  1  1  6                         665280    7      4656960
 1  1  1  1  1  2  2  3                    19958400  168   3353011200
 1  1  1  1  1  2  5                        1995840   42     83825280
 1  1  1  1  1  3  4                        3326400   42    139708800
 1  1  1  1  1  7                             95040    6       570240
 1  1  1  1  2  2  2  2                    29937600   70   2095632000
 1  1  1  1  2  2  4                        4989600  105    523908000
 1  1  1  1  2  3  3                        6652800  105    698544000
 1  1  1  1  2  6                            332640   30      9979200
 1  1  1  1  3  5                            665280   30     19958400
 1  1  1  1  4  4                            831600   15     12474000
 1  1  1  1  8                                11880    5        59400
 1  1  1  2  2  2  3                        9979200  140   1397088000
 1  1  1  2  2  5                            997920   60     59875200
 1  1  1  2  3  4                           1663200  120    199584000
 1  1  1  2  7                                47520   20       950400
 1  1  1  3  3  3                           2217600   20     44352000
 1  1  1  3  6                               110880   20      2217600
 1  1  1  4  5                               166320   20      3326400
 1  1  1  9                                    1320    4         5280
 1  1  2  2  2  2  2                       14968800   21    314344800
 1  1  2  2  2  4                           2494800   60    149688000
 1  1  2  2  3  3                           3326400   90    299376000
 1  1  2  2  6                               166320   30      4989600
 1  1  2  3  5                               332640   60     19958400
 1  1  2  4  4                               415800   30     12474000
 1  1  2  8                                    5940   12        71280
 1  1  3  3  4                               554400   30     16632000
 1  1  3  7                                   15840   12       190080
 1  1  4  6                                   27720   12       332640
 1  1  5  5                                   33264    6       199584
 1  1  10                                       132    3          396
 1  2  2  2  2  3                           4989600   30    149688000
 1  2  2  2  5                               498960   20      9979200
 1  2  2  3  4                               831600   60     49896000
 1  2  2  7                                   23760   12       285120
 1  2  3  3  3                              1108800   20     22176000
 1  2  3  6                                   55440   24      1330560
 1  2  4  5                                   83160   24      1995840
 1  2  9                                        660    6         3960
 1  3  3  5                                  110880   12      1330560
 1  3  4  4                                  138600   12      1663200
 1  3  8                                       1980    6        11880
 1  4  7                                       3960    6        23760
 1  5  6                                       5544    6        33264
 1  11                                           12    2           24
 2  2  2  2  2  2                           7484400    1      7484400
 2  2  2  2  4                              1247400    5      6237000
 2  2  2  3  3                              1663200   10     16632000
 2  2  2  6                                   83160    4       332640
 2  2  3  5                                  166320   12      1995840
 2  2  4  4                                  207900    6      1247400
 2  2  8                                       2970    3         8910
 2  3  3  4                                  277200   12      3326400
 2  3  7                                       7920    6        47520
 2  4  6                                      13860    6        83160
 2  5  5                                      16632    3        49896
 2  10                                           66    2          132
 3  3  3  3                                  369600    1       369600
 3  3  6                                      18480    3        55440
 3  4  5                                      27720    6       166320
 3  9                                           220    2          440
 4  4  4                                      34650    1        34650
 4  8                                           495    2          990
 5  7                                           792    2         1584
 6  6                                           924    1          924
 12                                               1    1            1
                                         1191578522       28091567595

                                        
The first program computed all the columns except the factor and total ways. Its results were placed into a file that the second program read.

First program:

   10    Fact12=!(12)
  100    for A=1 to 12
  200     if A=12 then ?a,tab(41);:print using(10,0),Fact12//Fact12: Ct=Ct+Fact12//Fact12
  300    for B=A to 12-A
  400     if A+B=12 then ?a;b;tab(41);:print using(10,0),Fact12//(!(A)*!(B)) Ct=Ct+Fact12//(!(A)*!(B))
  500    for C=B to 12-A-B
  600     if A+B+C=12 then ?a;b;c;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)): Ct=Ct+Fact12//(!(A)*!(B)*!(C))
  700    for D=C to 12-A-B-C
  800     if A+B+C+D=12 then ?a;b;c;d;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D))
  900    for E=D to 12-A-B-C-D
 1000     if A+B+C+D+E=12 then ?a;b;c;d;e;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E))
 1100    for F=E to 12-A-B-C-D-E
 1200     if A+B+C+D+E+F=12 then ?a;b;c;d;e;f;tab(41);:print using(10,0),fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F))
 1300    for G=F to 12-A-B-C-D-E-F
 1400     if A+B+C+D+E+F+G=12 then
 1409     :?a;b;c;d;e;f;g;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G))
 1410     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G))
 1500    for H=G to 12-A-B-C-D-E-F-G
 1600     if A+B+C+D+E+F+G+H=12 then
 1609     :?a;b;c;d;e;f;g;h;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H))
 1610     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H))
 1700    for I=H to 12-A-B-C-D-E-F-G-H
 1800     if A+B+C+D+E+F+G+H+I=12 then
 1809     :?a;b;c;d;e;f;g;h;i;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I))
 1810     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I))
 1900    for J=I to 12-A-B-C-D-E-F-G-H-I
 2000     if A+B+C+D+E+F+G+H+I+J=12 then
 2009     :?a;b;c;d;e;f;g;h;i;j;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J))
 2010     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J))
 2100    for K=J to 12-A-B-C-D-E-F-G-H-I-J
 2200     if A+B+C+D+E+F+G+H+I+J+K=12 then
 2209     :?a;b;c;d;e;f;g;h;i;j;k;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K))
 2210     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K))
 2300    for L=K to 12-A-B-C-D-E-F-G-H-I-J-K
 2309     ?a;b;c;d;e;f;g;h;i;j;k;l;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K)*!(L))
 2310     Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K)*!(L))
 2500    next
 2600    next
 2700    next
 2800    next
 2900    next
 3000    next
 3100    next
 3200    next
 3300    next
 3400    next
 3500    next
 3600    next
 3700    print tab(40);:? using(11,0),Ct
 3800 

The second program read the first program's output, computed the factor and the total ways:

DECLARE FUNCTION fact# (x#)
DEFDBL A-Z
OPEN "horoshij.txt" FOR INPUT AS #1
OPEN "horoshi2.txt" FOR OUTPUT AS #2
DO
 LINE INPUT #1, l$
 lCt = 0: typCt = 0: longCt = 0
 IF LEFT$(l$, 3) > "   " THEN
   FOR i = 1 TO 34 STEP 3
     s$ = MID$(l$, i, 3)
     IF s$ > "   " THEN
       lCt = lCt + 1
       longCt = longCt + 1
       IF lCt > 1 THEN
         IF s$ <> ps$ THEN
           typCt = typCt + 1
           nCt(typCt) = lCt - 1
           lCt = 1
         END IF
       END IF
     ELSE
       EXIT FOR
     END IF
     ps$ = s$
   NEXT
   typCt = typCt + 1
   nCt(typCt) = lCt
   factor = fact(longCt)
   FOR i = 1 TO typCt
     factor = factor / fact(nCt(i))
   NEXT
   oNum = VAL(MID$(l$, 40))
   tNum = oNum * factor
   PRINT #2, l$;
   PRINT #2, USING "##### ############"; factor; tNum
   tot = tot + tNum
 ELSE
   PRINT #2, l$;
   PRINT #2, USING "     ############"; tot
 END IF
LOOP UNTIL EOF(1)
CLOSE

FUNCTION fact (x)
  f = 1
  FOR i = 2 TO x
   f = f * i
  NEXT
  fact = f
END FUNCTION

A similar pair of programs verifies Jer's finding of 75 for 4 racers:

 1  1  1  1                                      24    1           24
 1  1  2                                         12    3           36
 1  3                                             4    2            8
 2  2                                             6    1            6
 4                                                1    1            1
                                                 47                75
                                                 
but finds 541, rather than 931 for 5 racers:

 1  1  1  1  1                                  120    1          120
 1  1  1  2                                      60    4          240
 1  1  3                                         20    3           60
 1  2  2                                         30    3           90
 1  4                                             5    2           10
 2  3                                            10    2           20
 5                                                1    1            1
                                                246               541

 

Posted by Charlie on 2006-11-28 16:00:11