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

 Getting Maps In 2080 (Posted on 2007-08-17)
Let S = {1; 2; 3; 4; 5; 6; 7}

Analytically determine the number of maps f from S to S such that f2080(x) = x for every x belonging to S.

Note: The iteration is denoted by the superscript, such that f1(x) = f(x) and
fn(x) = f(fn-1(x)) for all n > 1.

 See The Solution Submitted by K Sengupta Rating: 4.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 one case missing--computer lists all combinations Comment 4 of 4 |
(In reply to solution by Charlie)

The cases were supposed to show all combinations of 5, 4, 2 and 1 that add up to 7, but one was left out: 4, 1, 1, 1. It was found by the following:

FOR no5s = 0 TO 1
FOR no4s = 0 TO (7 - 5 * no5s) / 4
FOR no2s = 0 TO (7 - 5 * no5s - 4 * no4s) / 2
no1s = 7 - 5 * no5s - 4 * no4s - 2 * no2s
FOR i = 1 TO no5s: PRINT "5, "; : NEXT
FOR i = 1 TO no4s: PRINT "4, "; : NEXT
FOR i = 1 TO no2s: PRINT "2, "; : NEXT
FOR i = 1 TO no1s: PRINT "1, "; : NEXT
PRINT
NEXT
NEXT
NEXT

whose output was:

1, 1, 1, 1, 1, 1, 1,
2, 1, 1, 1, 1, 1,
2, 2, 1, 1, 1,
2, 2, 2, 1,
4, 1, 1, 1,
4, 2, 1,
5, 1, 1,
5, 2,

The contribution of 4, 1, 1, 1 is given as follows:

There are C(7,4)= 35 ways of choosing the participants in the cycle of 4. Again, any cycle of 4 can done in 6 different ways, as the lowest of the four can go to any of 3 numbers, and that number can go to either of 2 numbers.

So this accounts for 35*6=210 functions.

Added to the 1870 functions (permutations) found previously, this brings the total to 2080, in fact the same 2080 as in the title.

 Posted by Charlie on 2007-08-20 10:36:24

 Search: Search body:
Forums (0)