A381975 Number of ways for n competitors to rank in a competition in which each match has 4 possible outcomes in which each competitor gains 0, 1, 2 or 3 points.

1, 1, 2, 9, 58, 459, 4370, 48999, 632884, 9254473, 151155362, 2727862751

Offset: 0

Author

SiYang Hu, May 06 2025

Keywords

• nonn
• more

Comments

Also, the number of maps f:{1, 2, ..., n} -> {1, 2, ..., n} such that f(f(f(x))) >= x for all 1 <= x <= n.

When this definition is changed to f(f(x)), then the result would be the Fubini numbers (A000670).

Crossrefs

Cf. A000142, A000312, A000670, A001470.

Programs

Haskell

validMappings :: Int -> Int
validMappings n = validMappingsDFS n [0] 1 where
  checkCondition f = all (\x -> f !! (f !! (f !! (x-1)) - 1) - 1 >= x) [1..n]
  validMappingsDFS n f x
    | x > n = if checkCondition f then 1 else 0
    | otherwise = sum [validMappingsDFS n (take (x-1) f ++ [i] ++ drop x f) (x+1) | i <- [1..n]]

Mathematica

CheckCondition[f_, n_] := AllTrue[Range[n], (f[[f[[f[[#]]]]]] >= # &)]
validMappingsDFS[n_, f_, x_] := Module[{i, f2, count},
  If[x > n,
    If[CheckCondition[f, n], 1, 0],
    count = 0;
    For[i = 1, i <= n, i++,
      f2 = f; f2[[x]] = i;  (* Assign mapping for f[x] *)
      count += validMappingsDFS[n, f2, x + 1];  (* Explore further *)
    ];
    count
  ]
]
A381975[n_] := validMappingsDFS[n, ConstantArray[0, n], 1]
Table[A381975[n], {n, 0, 6}]

Python

def validMappings(n):
    def checkCondition(f, n):
        return all(f[f[f[x]]] >= x for x in range(1, n+1))
    def validMappingsDFS(n, f, x):
        if x > n:
            return 1 if checkCondition(f, n) else 0
        return sum(validMappingsDFS(n, f[:x] + [i] + f[x+1:], x+1) for i in range(1, n+1))
    return validMappingsDFS(n, [0] * (n+1), 1)

R

validMappings <- function(n) {
  checkCondition <- function(f, n) all(sapply(1:n, function(x) f[f[f[x]]] >= x))
  validMappingsDFS <- function(n, f, x) {
    if (x > n) return(ifelse(checkCondition(f, n), 1, 0))
    sum(sapply(1:n, function(i) { f[x] <- i; validMappingsDFS(n, f, x + 1) }))
  }
  validMappingsDFS(n, rep(0, n), 1)
}

Extensions

a(11) from Sean A. Irvine, May 13 2025