具有函数迭代的不变性的函数

青青子衿

如何构造出满足 $f(f(f(f(f(x)))))=f(x)$ 的函数 $f(x)$例如：$f(x)=\frac{1+x}{1-x}$那么，像 $f(f(x))=f(x), f(f(f(x)))=f(x), f(f(f(f(x))))=f(x)$

Tesla35

回复 1# 青青子衿


    那岂不是很多。。
反函数，倒数，负倒数，相反数。
分一下迭代奇偶吧

其妙

看迭代周期噻，

hbghlyj

topologicalmusings.wordpress.com/2009/03/28/n … otent-endofunctions/

1. import math
3. def count_idempotent_functions(n):
4.     """
5.     Count the number of idempotent functions f: {1, ..., n} -> {1, ..., n}
6.     satisfying f(f(x)) = f(x) for all x. The formula is:
7.     sum_{k=1..n} [C(n, k) * k^(n - k)],
8.     where C(n, k) is the binomial coefficient.
9.     """
10.     total = 0
11.     for k in range(1, n + 1):
12.         total += math.comb(n, k) * (k ** (n - k))
13.     return total
15. for n in range(1, 11):
16.     print(f"n = {n}, number of idempotent functions = {count_idempotent_functions(n)}")

Copy the Code

hbghlyj

1. from math import comb, factorial
3. def count_functions(n):
4.     total = 0
5.     # k is the number of fixed points, l is the number of 2-cycles
6.     for k in range(n+1):
7.         for l in range((n//2)+1):
8.             s = k + 2*l
9.             if s > n:
10.                 break
11.             # Choose which s elements form the cycles
12.             ways_subset = comb(n, s)
13.             # Within those s elements, choose k of them to be fixed points
14.             # and partition the remaining 2l into l 2-cycles
15.             ways_cycle_struct = comb(s, k) * factorial(2*l) // (2**l * factorial(l))
16.             # The remaining n-s elements each map into any of those s cycle elements
17.             ways_outside = s ** (n - s)
18.             total += ways_subset * ways_cycle_struct * ways_outside
19.     return total
21. for n in range(1, 11):
22.     print(f"n={n}, count={count_functions(n)}")

Copy the Code

hbghlyj

1. import math
3. def count_functions(n):
4.     """
5.     Counts the number of functions f: {1..n} -> {1..n} such that
6.     f(f(f(f(x)))) = f(x) for all x in {1..n}.
7.    
8.     Key observations:
9.     - The condition f^4(x) = f(x) for all x is satisfied exactly by
10.       functions whose cycles are only of length 1 or 3.
11.     - Moreover, any element not in a cycle must map directly (in one step)
12.       to an element on one of these 1- or 3-cycles (no longer chains are allowed).
13.    
14.     Let c1 be the number of 1-cycles and c3 be the number of 3-cycles.
15.     Then we choose c1 + 3*c3 distinct elements from n to form the cycles.
16.     Among those c1 + 3*c3 chosen elements, we choose c1 to be 1-cycles;
17.     the remaining 3*c3 form c3 disjoint 3-cycles.
18.     The other n - (c1 + 3*c3) elements each map in one step to any
19.     of the cycle elements.
20.    
21.     The count of ways to form these cycles is:
22.    
23.       Choose(c1 + 3*c3, c1) * ( (3*c3)! / (3^(c3) * c3!) ) * (c1 + 3*c3)^(n - (c1 + 3*c3))
24.    
25.     Summing over all valid c1, c3 (with c1 + 3*c3 <= n) gives the total.
26.     """
27.     total = 0
28.     for c3 in range(n // 3 + 1):
29.         for c1 in range(n - 3*c3 + 1):
30.             cycle_count_choice = math.comb(c1 + 3*c3, c1)
31.             
32.             # Number of ways to arrange c3 disjoint 3-cycles among 3*c3 distinct elements:
33.             # (3*c3)! / (3^(c3) * c3!)
34.             if c3 > 0:
35.                 cycle_3_ways = math.factorial(3*c3) // (3**c3 * math.factorial(c3))
36.             else:
37.                 cycle_3_ways = 1  # if c3=0, there's exactly 1 way (no 3-cycles)
38.             
39.             # For the remaining n - (c1 + 3*c3) elements, each one can map to any
40.             # of the c1 + 3*c3 cycle elements
41.             ways_for_remaining = (c1 + 3*c3)**(n - (c1 + 3*c3))
42.             
43.             total += cycle_count_choice * cycle_3_ways * ways_for_remaining
44.     return total
46. for n in range(1, 11):
47.     print(f"n = {n}, count = {count_functions(n)}")

Copy the Code

hbghlyj

n元集上的函数$f$的个数
1,4,25,224,2601,36352,588337,10809360,222264145,5057068256
在OEIS中没有找到，是不是算错了

1. import math
3. def precompute_ways_chains(max_n):
4.     """
5.     Precompute the number of ways to attach 'rem = n - M' elements as chains (of length up to 4)
6.     into any of M cycle nodes.
8.     Each of the 'rem' elements can form a chain of length 1..4 ending in a cycle node. We count
9.     how many ways they can form those chains collectively.
10.    
11.     We'll store these counts in ways_chains_table[n][M].
12.     """
13.     # Precompute factorials for speed
14.     factorials = [1]*(max_n+1)
15.     for i in range(1, max_n+1):
16.         factorials[i] = factorials[i-1]*i
18.     def multinomial(total, counts):
19.         # multinomial coefficient = total! / (counts[0]! * counts[1]! * ... )
20.         num = factorials[total]
21.         for c in counts:
22.             num //= factorials[c]
23.         return num
25.     ways_chains_table = [[0]*(max_n+1) for _ in range(max_n+1)]
26.    
27.     for n in range(1, max_n+1):
28.         for M in range(n+1):
29.             rem = n - M
30.             if rem < 0:
31.                 continue
32.             total_ways = 0
33.             # We partition rem into (s1, s2, s3, s4) where s1 + s2 + s3 + s4 = rem
34.             # s1 = number of elements that map directly to a cycle node
35.             # s2 = number of elements that map to one of those s1 elements
36.             # s3 = number that map to an element among s2...
37.             # s4 = number that map to an element among s3...
38.             # Each chain ends at a cycle node, so effectively the chain length is from 1 up to 4.
39.             for s1 in range(rem+1):
40.                 for s2 in range(rem+1 - s1):
41.                     for s3 in range(rem+1 - s1 - s2):
42.                         s4 = rem - s1 - s2 - s3
43.                         # The multinomial factor to choose which elements go to s1, s2, s3, s4
44.                         multi = multinomial(rem, (s1, s2, s3, s4))
45.                         # attachments factor = M^s1 * s1^s2 * s2^s3 * s3^s4
46.                         
47.                         # If s1=0 but s2>0, that implies references to 0 existing elements => invalid
48.                         if s1 == 0 and s2 > 0:
49.                             continue
50.                         if s2 == 0 and s3 > 0:
51.                             continue
52.                         if s3 == 0 and s4 > 0:
53.                             continue
54.                         
55.                         attach_factor = (M**s1) * (s1**s2) * (s2**s3) * (s3**s4)
56.                         total_ways += multi * attach_factor
57.             ways_chains_table[n][M] = total_ways
58.    
59.     return ways_chains_table
61. def count_functions_power5(n, ways_chains_table):
62.     """
63.     Count the number of functions f: {1..n} -> {1..n} such that
64.     f(f(f(f(f(x))))) = f(x) for all x.
66.     Valid cycle lengths under this condition are 1, 2, and 4 because f^5(x)=f(x)
67.     implies the cycle length divides (5-1)=4 or is 1 itself. Then every non-cycle
68.     element must chain within up to 4 steps into a cycle node.
69.     """
70.     total = 0
71.     # c1: count of 1-cycles, c2: count of 2-cycles, c4: count of 4-cycles
72.     for c4 in range(n // 4 + 1):
73.         for c2 in range((n - 4*c4) // 2 + 1):
74.             c1_max = n - 2*c2 - 4*c4
75.             for c1 in range(c1_max + 1):
76.                 # M = total cycle elements
77.                 M = c1 + 2*c2 + 4*c4
78.                 # Choose M distinct elements out of n
79.                 ways_choose_M = math.comb(n, M)
80.                 # Among these M, choose c1 for 1-cycles
81.                 ways_choose_c1 = math.comb(M, c1)
82.                 # Remaining M-c1 = 2*c2 + 4*c4 for the 2- and 4-cycles
84.                 # We first choose which 2*c2 among these (2*c2 + 4*c4) will form the 2-cycles
85.                 ways_choose_2c2 = math.comb(2*c2 + 4*c4, 2*c2)
86.                 # Count ways to form c2 disjoint 2-cycles from 2*c2 distinct elements:
87.                 ways_2cycles = math.factorial(2*c2) // (2**c2 * math.factorial(c2))
88.                 # Count ways to form c4 disjoint 4-cycles from 4*c4 distinct elements:
89.                 ways_4cycles = math.factorial(4*c4) // (4**c4 * math.factorial(c4))
90.                
91.                 # Ways to attach the remaining n-M elements in chains of length <=4
92.                 ways_attach = ways_chains_table[n][M]
93.                
94.                 total += (ways_choose_M *
95.                           ways_choose_c1 *
96.                           ways_choose_2c2 *
97.                           ways_2cycles *
98.                           ways_4cycles *
99.                           ways_attach)
100.     return total
102. ways_chains_table = precompute_ways_chains(10)
103. for i in range(1, 11):
104.     print(f"n={i}, count={count_functions_power5(i, ways_chains_table)}")

Copy the Code