All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 So many quintuplets... (Posted on 2011-03-17)
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.

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 3

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     128710     2002`

For the above table:

combi[n,r] :=
{
return n!/(r!*(n-r)!)
}
for n=1 to 10
{
}

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

 Search: Search body:
Forums (0)