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

0, 0, 2, 5, 24, 128, 795, 5686, 46090, 418519, 4213098, 46595650, 561773033, 7333741536, 103065052300, 1551392868821, 24902155206164, 424588270621876, 7663358926666175, 145967769353476594, 2926073829112697318, 61577929208485406331, 1357369100658321844470, 31276096500003460511422

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

Table of n, a(n) for n=1..24.

M. Lind, E. Fiorini, A. Woldar, and W. H. T. Wong, On Properties of Pebble Assignment Graphs, Journal of Integer Sequences, 24(6), 2020.

Formula

a(n) = A006932(n) - A346199(n).

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("A346189 :" + str(wn[1:]))
    print("A346198 :" + str([factorial[i]-wn[i]-tl[i]-kn[i] for i in range(n+1)][1:]))
    print("A346199 :" + str(kn[1:]))
    print("A346204 :" + str(tl[1:]))
total_func(20)

Crossrefs

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

Sequence in context: A052111 A176473 A185056 * A330512 A194349 A208969

Adjacent sequences: A346201 A346202 A346203 * A346205 A346206 A346207

Keyword

nonn,more

Author

Eugene Fiorini, Jared Glassband, Garrison Lee Koch, Sophia Lebiere, Xufei Liu, Evan Sabini, Nathan B. Shank, Andrew Woldar, Jul 10 2021

Status

approved