A346204 - OEIS

%I #47 Aug 07 2021 04:15:05

%S 0,0,2,5,24,128,795,5686,46090,418519,4213098,46595650,561773033,

%T 7333741536,103065052300,1551392868821,24902155206164,424588270621876,

%U 7663358926666175,145967769353476594,2926073829112697318,61577929208485406331,1357369100658321844470,31276096500003460511422

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

%C A small descent in a permutation p is a position i such that p(i)-p(i+1)=1.

%C 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 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, Vol. 1, CRC Press, 2001.

%H 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 a(n) = A006932(n) - A346199(n).

%e 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 (Python)

%o import math

%o bn = [1,1,1]

%o wn = [0,0,0]

%o kn = [1,1,1]

%o def summation(n):

%o     final = bn[n] - bn[n-1]

%o     for k in range(4,n+1):

%o         final -= wn[k-1]*bn[n-k]

%o     return final

%o def smallsum(n):

%o     final = bn[n-1]

%o     for k in range(4,n+1):

%o         final += wn[k-1]*bn[n-k]

%o     return final

%o def derrangement(n):

%o     finalsum = 0

%o     for i in range(n+1):

%o         if i%2 == 0:

%o             finalsum += math.factorial(n)*1//math.factorial(i)

%o         else:

%o             finalsum -= math.factorial(n)*1//math.factorial(i)

%o     if finalsum != 0:

%o         return finalsum

%o     else:

%o         return 1

%o def fixedpoint(n):

%o     finalsum = math.factorial(n-1)

%o     for i in range(2,n):

%o         finalsum += math.factorial(i-i)*math.factorial(n-i-1)

%o         print(math.factorial(i-i)*math.factorial(n-i-1))

%o     return finalsum

%o def no_cycles(n):

%o     goal = n

%o     cycles = [0, 1]

%o     current = 2

%o     while current<= goal:

%o         new = 0

%o         k = 1

%o         while k<=current:

%o             new += (math.factorial(k-1)-cycles[k-1])*(math.factorial(current-k))

%o             k+=1

%o         cycles.append(new)

%o         current+=1

%o     return cycles

%o def total_func(n):

%o     for i in range(3,n+1):

%o         bn.append(derrangement(i+1)//(i))

%o         kn.append(smallsum(i))

%o         wn.append(summation(i))

%o     an = no_cycles(n)

%o     tl = [int(an[i]-kn[i]) for i in range(n+1)]

%o     factorial = [math.factorial(x) for x in range(0,n+1)]

%o     print("A346189 :" + str(wn[1:]))

%o     print("A346198 :" + str([factorial[i]-wn[i]-tl[i]-kn[i] for i in range(n+1)][1:]))

%o     print("A346199 :" + str(kn[1:]))

%o     print("A346204 :" + str(tl[1:]))

%o total_func(20)

%Y Cf. A000255, A000166, A000153, A000261, A001909, A001910, A055790, A346189, A346198, A346199.

%K nonn,more

%O 1,3

%A _Eugene Fiorini_, _Jared Glassband_, _Garrison Lee Koch_, _Sophia Lebiere_, _Xufei Liu_, _Evan Sabini_, _Nathan B. Shank_, _Andrew Woldar_, Jul 10 2021