|
|
A346204
|
|
a(n) is the number of permutations on [n] with at least one strong fixed point and at least one small descent.
|
|
4
|
|
|
0, 0, 2, 5, 24, 128, 795, 5686, 46090, 418519, 4213098, 46595650, 561773033, 7333741536, 103065052300, 1551392868821, 24902155206164, 424588270621876, 7663358926666175, 145967769353476594, 2926073829112697318, 61577929208485406331, 1357369100658321844470, 31276096500003460511422
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A small descent in a permutation p is a position i such that p(i)-p(i+1)=1.
A strong fixed point is a fixed point (or splitter) p(k)=k such that p(i) < k for i < k and p(j) > k for j > k.
|
|
REFERENCES
|
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, Vol. 1, CRC Press, 2001.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=4, the a(4)=5 permutations on [4] with strong fixed points and small descents: {(1*, 2*, [4, 3]), (1*, [3, 2], 4*), (1*, <4, 3, 2>), ([2, 1], 3*, 4*), (<3, 2, 1>, 4*)}. *strong fixed point, []small descent, <>consecutive small descents.
|
|
PROG
|
(Python)
import math
bn = [1, 1, 1]
wn = [0, 0, 0]
kn = [1, 1, 1]
def summation(n):
final = bn[n] - bn[n-1]
for k in range(4, n+1):
final -= wn[k-1]*bn[n-k]
return final
def smallsum(n):
final = bn[n-1]
for k in range(4, n+1):
final += wn[k-1]*bn[n-k]
return final
def derrangement(n):
finalsum = 0
for i in range(n+1):
if i%2 == 0:
finalsum += math.factorial(n)*1//math.factorial(i)
else:
finalsum -= math.factorial(n)*1//math.factorial(i)
if finalsum != 0:
return finalsum
else:
return 1
def fixedpoint(n):
finalsum = math.factorial(n-1)
for i in range(2, n):
finalsum += math.factorial(i-i)*math.factorial(n-i-1)
print(math.factorial(i-i)*math.factorial(n-i-1))
return finalsum
def no_cycles(n):
goal = n
cycles = [0, 1]
current = 2
while current<= goal:
new = 0
k = 1
while k<=current:
new += (math.factorial(k-1)-cycles[k-1])*(math.factorial(current-k))
k+=1
cycles.append(new)
current+=1
return cycles
def total_func(n):
for i in range(3, n+1):
bn.append(derrangement(i+1)//(i))
kn.append(smallsum(i))
wn.append(summation(i))
an = no_cycles(n)
tl = [int(an[i]-kn[i]) for i in range(n+1)]
factorial = [math.factorial(x) for x in range(0, n+1)]
print("A346198 :" + str([factorial[i]-wn[i]-tl[i]-kn[i] for i in range(n+1)][1:]))
total_func(20)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|