cp's OEIS Frontend

A346204 a(n) is the number of permutations on [n] with at least one strong fixed point and at least one small descent.

%I A346204 #47 Aug 07 2021 04:15:05
%S A346204 0,0,2,5,24,128,795,5686,46090,418519,4213098,46595650,561773033,
%T A346204 7333741536,103065052300,1551392868821,24902155206164,424588270621876,
%U A346204 7663358926666175,145967769353476594,2926073829112697318,61577929208485406331,1357369100658321844470,31276096500003460511422
%N A346204 a(n) is the number of permutations on [n] with at least one strong fixed point and at least one small descent.
%C A346204 A small descent in a permutation p is a position i such that p(i)-p(i+1)=1.
%C A346204 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.
%D A346204 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, Vol. 1, CRC Press, 2001.
%H A346204 M. Lind, E. Fiorini, A. Woldar, and W. H. T. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Wong/wong31.html">On Properties of Pebble Assignment Graphs</a>, Journal of Integer Sequences, 24(6), 2020.
%F A346204 a(n) = A006932(n) - A346199(n).
%e A346204 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.
%o A346204 (Python)
%o A346204 import math
%o A346204 bn = [1,1,1]
%o A346204 wn = [0,0,0]
%o A346204 kn = [1,1,1]
%o A346204 def summation(n):
%o A346204     final = bn[n] - bn[n-1]
%o A346204     for k in range(4,n+1):
%o A346204         final -= wn[k-1]*bn[n-k]
%o A346204     return final
%o A346204 def smallsum(n):
%o A346204     final = bn[n-1]
%o A346204     for k in range(4,n+1):
%o A346204         final += wn[k-1]*bn[n-k]
%o A346204     return final
%o A346204 def derrangement(n):
%o A346204     finalsum = 0
%o A346204     for i in range(n+1):
%o A346204         if i%2 == 0:
%o A346204             finalsum += math.factorial(n)*1//math.factorial(i)
%o A346204         else:
%o A346204             finalsum -= math.factorial(n)*1//math.factorial(i)
%o A346204     if finalsum != 0:
%o A346204         return finalsum
%o A346204     else:
%o A346204         return 1
%o A346204 def fixedpoint(n):
%o A346204     finalsum = math.factorial(n-1)
%o A346204     for i in range(2,n):
%o A346204         finalsum += math.factorial(i-i)*math.factorial(n-i-1)
%o A346204         print(math.factorial(i-i)*math.factorial(n-i-1))
%o A346204     return finalsum
%o A346204 def no_cycles(n):
%o A346204     goal = n
%o A346204     cycles = [0, 1]
%o A346204     current = 2
%o A346204     while current<= goal:
%o A346204         new = 0
%o A346204         k = 1
%o A346204         while k<=current:
%o A346204             new += (math.factorial(k-1)-cycles[k-1])*(math.factorial(current-k))
%o A346204             k+=1
%o A346204         cycles.append(new)
%o A346204         current+=1
%o A346204     return cycles
%o A346204 def total_func(n):
%o A346204     for i in range(3,n+1):
%o A346204         bn.append(derrangement(i+1)//(i))
%o A346204         kn.append(smallsum(i))
%o A346204         wn.append(summation(i))
%o A346204     an = no_cycles(n)
%o A346204     tl = [int(an[i]-kn[i]) for i in range(n+1)]
%o A346204     factorial = [math.factorial(x) for x in range(0,n+1)]
%o A346204     print("A346189 :" + str(wn[1:]))
%o A346204     print("A346198 :" + str([factorial[i]-wn[i]-tl[i]-kn[i] for i in range(n+1)][1:]))
%o A346204     print("A346199 :" + str(kn[1:]))
%o A346204     print("A346204 :" + str(tl[1:]))
%o A346204 total_func(20)
%Y A346204 Cf. A000255, A000166, A000153, A000261, A001909, A001910, A055790, A346189, A346198, A346199.
%K A346204 nonn,more
%O A346204 1,3
%A A346204 _Eugene Fiorini_, _Jared Glassband_, _Garrison Lee Koch_, _Sophia Lebiere_, _Xufei Liu_, _Evan Sabini_, _Nathan B. Shank_, _Andrew Woldar_, Jul 10 2021