Determine the total number of quintuplets (A,B,C,D,E) of positive integers such that A<=B<=C<=D<=E<=N. Both analytic and software solution for N=1, 2, ...9,10,...N required.

Starting with 1 and proceeding through N there occur N-1 increments of 1 each. Interspersed with these can be placed A, B, C, D and E, including the possibility that one or more may be before the first increment or after the last.

For example, A,B,+1,+1,C,+1,D,+1,E,+1,+1 represents the case where N=7 and A=B=1, C=3, D=4 and E=5. The final two +1's represent the fact that we were allowed to go up to 7, so that if the E had been delayed till after these two +1's, E would have been 7.

Each such sequence of letters (in alphabetic order) and +1's corresponds 1-to-1 with one of the quintuplets. Since the letters are in order, they don't need to be specified, so shorthand for the above sequence is xx++x+x+x++, with each x representing A or the next successive letter of the alphabet and each + representing +1, so it represents (1,1,3,4,5) within the context of N=7.

There are 5 x's and N-1 +'s, so the solution is C(N-1+5,5) or C(N+4,5).

 N  # of sequences
 1        1
 2        6
 3       21
 4       56
 5      126
 6      252
 7      462
 8      792
 9     1287
10     2002

For the above table:

combi[n,r] :=
 {
 return n!/(r!*(n-r)!)
 }
for n=1 to 10
 {
 answer=combi[n+4,5]
 println["$n"+"\t"+"$answer"]
 }

The numbers for N = 2 through 5 can be verified by counting below:

(1,1,1,1,1)
(1,1,1,1,2)
(1,1,1,2,2)
(1,1,2,2,2)
(1,2,2,2,2)
(2,2,2,2,2)

(1,1,1,1,1)
(1,1,1,1,2)
(1,1,1,1,3)
(1,1,1,2,2)
(1,1,1,2,3)
(1,1,1,3,3)
(1,1,2,2,2)
(1,1,2,2,3)
(1,1,2,3,3)
(1,1,3,3,3)
(1,2,2,2,2)
(1,2,2,2,3)
(1,2,2,3,3)
(1,2,3,3,3)
(1,3,3,3,3)
(2,2,2,2,2)
(2,2,2,2,3)
(2,2,2,3,3)
(2,2,3,3,3)
(2,3,3,3,3)
(3,3,3,3,3)

(1,1,1,1,1)
(1,1,1,1,2)
(1,1,1,1,3)
(1,1,1,1,4)
(1,1,1,2,2)
(1,1,1,2,3)
(1,1,1,2,4)
(1,1,1,3,3)
(1,1,1,3,4)
(1,1,1,4,4)
(1,1,2,2,2)
(1,1,2,2,3)
(1,1,2,2,4)
(1,1,2,3,3)
(1,1,2,3,4)
(1,1,2,4,4)
(1,1,3,3,3)
(1,1,3,3,4)
(1,1,3,4,4)
(1,1,4,4,4)
(1,2,2,2,2)
(1,2,2,2,3)
(1,2,2,2,4)
(1,2,2,3,3)
(1,2,2,3,4)
(1,2,2,4,4)
(1,2,3,3,3)
(1,2,3,3,4)
(1,2,3,4,4)
(1,2,4,4,4)
(1,3,3,3,3)
(1,3,3,3,4)
(1,3,3,4,4)
(1,3,4,4,4)
(1,4,4,4,4)
(2,2,2,2,2)
(2,2,2,2,3)
(2,2,2,2,4)
(2,2,2,3,3)
(2,2,2,3,4)
(2,2,2,4,4)
(2,2,3,3,3)
(2,2,3,3,4)
(2,2,3,4,4)
(2,2,4,4,4)
(2,3,3,3,3)
(2,3,3,3,4)
(2,3,3,4,4)
(2,3,4,4,4)
(2,4,4,4,4)
(3,3,3,3,3)
(3,3,3,3,4)
(3,3,3,4,4)
(3,3,4,4,4)
(3,4,4,4,4)
(4,4,4,4,4)

(1,1,1,1,1)
(1,1,1,1,2)
(1,1,1,1,3)
(1,1,1,1,4)
(1,1,1,1,5)
(1,1,1,2,2)
(1,1,1,2,3)
(1,1,1,2,4)
(1,1,1,2,5)
(1,1,1,3,3)
(1,1,1,3,4)
(1,1,1,3,5)
(1,1,1,4,4)
(1,1,1,4,5)
(1,1,1,5,5)
(1,1,2,2,2)
(1,1,2,2,3)
(1,1,2,2,4)
(1,1,2,2,5)
(1,1,2,3,3)
(1,1,2,3,4)
(1,1,2,3,5)
(1,1,2,4,4)
(1,1,2,4,5)
(1,1,2,5,5)
(1,1,3,3,3)
(1,1,3,3,4)
(1,1,3,3,5)
(1,1,3,4,4)
(1,1,3,4,5)
(1,1,3,5,5)
(1,1,4,4,4)
(1,1,4,4,5)
(1,1,4,5,5)
(1,1,5,5,5)
(1,2,2,2,2)
(1,2,2,2,3)
(1,2,2,2,4)
(1,2,2,2,5)
(1,2,2,3,3)
(1,2,2,3,4)
(1,2,2,3,5)
(1,2,2,4,4)
(1,2,2,4,5)
(1,2,2,5,5)
(1,2,3,3,3)
(1,2,3,3,4)
(1,2,3,3,5)
(1,2,3,4,4)
(1,2,3,4,5)
(1,2,3,5,5)
(1,2,4,4,4)
(1,2,4,4,5)
(1,2,4,5,5)
(1,2,5,5,5)
(1,3,3,3,3)
(1,3,3,3,4)
(1,3,3,3,5)
(1,3,3,4,4)
(1,3,3,4,5)
(1,3,3,5,5)
(1,3,4,4,4)
(1,3,4,4,5)
(1,3,4,5,5)
(1,3,5,5,5)
(1,4,4,4,4)
(1,4,4,4,5)
(1,4,4,5,5)
(1,4,5,5,5)
(1,5,5,5,5)
(2,2,2,2,2)
(2,2,2,2,3)
(2,2,2,2,4)
(2,2,2,2,5)
(2,2,2,3,3)
(2,2,2,3,4)
(2,2,2,3,5)
(2,2,2,4,4)
(2,2,2,4,5)
(2,2,2,5,5)
(2,2,3,3,3)
(2,2,3,3,4)
(2,2,3,3,5)
(2,2,3,4,4)
(2,2,3,4,5)
(2,2,3,5,5)
(2,2,4,4,4)
(2,2,4,4,5)
(2,2,4,5,5)
(2,2,5,5,5)
(2,3,3,3,3)
(2,3,3,3,4)
(2,3,3,3,5)
(2,3,3,4,4)
(2,3,3,4,5)
(2,3,3,5,5)
(2,3,4,4,4)
(2,3,4,4,5)
(2,3,4,5,5)
(2,3,5,5,5)
(2,4,4,4,4)
(2,4,4,4,5)
(2,4,4,5,5)
(2,4,5,5,5)
(2,5,5,5,5)
(3,3,3,3,3)
(3,3,3,3,4)
(3,3,3,3,5)
(3,3,3,4,4)
(3,3,3,4,5)
(3,3,3,5,5)
(3,3,4,4,4)
(3,3,4,4,5)
(3,3,4,5,5)
(3,3,5,5,5)
(3,4,4,4,4)
(3,4,4,4,5)
(3,4,4,5,5)
(3,4,5,5,5)
(3,5,5,5,5)
(4,4,4,4,4)
(4,4,4,4,5)
(4,4,4,5,5)
(4,4,5,5,5)
(4,5,5,5,5)
(5,5,5,5,5)

from

OPEN "manyquin.txt" FOR OUTPUT AS #2
FOR n = 2 TO 5
  FOR a = 1 TO n
  FOR b = a TO n
  FOR c = b TO n
  FOR d = c TO n
  FOR e = d TO n
   PRINT #2, "(";
   PRINT #2, LTRIM$(STR$(a)); ",";
   PRINT #2, LTRIM$(STR$(b)); ",";
   PRINT #2, LTRIM$(STR$(c)); ",";
   PRINT #2, LTRIM$(STR$(d)); ",";
   PRINT #2, LTRIM$(STR$(e)); ")"
  NEXT
  NEXT
  NEXT
  NEXT
  NEXT
  PRINT #2,
NEXT
CLOSE 2

 

Posted by Charlie on 2011-03-17 13:31:16