Python 3, (削除) 93 (削除ここまで) (削除) 84 (削除ここまで) 77 bytes

-9 bytes thanks to @xnor!

Going for the brownie points, but still exponential runtime ;)

f=lambda n,k,d=1:(n<2or~-n*(f(n-1,k,d+1)*(d!=k-1)+f(n-1,k-d)))/(d-(k==1)or 1)

Try it online!

• 1
  \$\begingroup\$ I noticed that r only ever appeared in comparison to k, so you can eliminate it: Try it online! \$\endgroup\$

  xnor

  – xnor

  2024年02月07日 20:44:39 +00:00

  Commented Feb 7, 2024 at 20:44
• \$\begingroup\$ @xnor thanks! I should've looked a bit closer, just from writing the O(n^2) APL answer I knew this could be done with fewer variables \$\endgroup\$

  ovs

  – ovs

  2024年02月07日 21:58:23 +00:00

  Commented Feb 7, 2024 at 21:58

Python 3, (削除) 124 (削除ここまで) (削除) 119 (削除ここまで) 117 bytes

-5 bytes thanks to enzo.

lambda n,k:sum(all(r==sum(q<r for q in s)for r in s)for s in product([k-1],*[range(n)]*(n-1)))
from itertools import*

Try it online!

This uses the sum function two times too many, considering the algorithm doesn't involve any addition at all...

Explanation

The algorithm is pretty simple. Let's assume there are \$n = 3\$ contestants and Alice's rank \$k = 1\$. The ranks that follow will be 0-indexed because it's more convenient to work with. First, it generates a list of possible rankings where Alice's rank, or the first rank in the list, is \0ドル\$. This is done by taking the Cartesian product of the singleton list \$[0]\$ with \$n - 1 = 2\$ copies of \$[0, 3)\$.

[(0, 0, 0), (0, 0, 1), (0, 0, 2),
 (0, 1, 0), (0, 1, 1), (0, 1, 2),
 (0, 2, 0), (0, 2, 1), (0, 2, 2)]

Then, it knocks out invalid rankings by checking if each rank is equal to "the number of other participants who performed strictly better than them", or in other words, the number of ranks lower than the rank in question.

[(0, 0, 0), (0, 0, 2),
 (0, 1, 1), (0, 1, 2),
 (0, 2, 0), (0, 2, 1)]

Finally, it returns the number of rankings remaining, which is \6ドル\$.

• 1
  \$\begingroup\$ Amazing answer! -5 bytes \$\endgroup\$

  enzo

  – enzo

  2024年02月07日 12:35:35 +00:00

  Commented Feb 7, 2024 at 12:35

APL(Dyalog Unicode), ^{(削除) 58 (削除ここまで)} 57 bytes ^SBCS

{⍵÷⍨⍺(⊣{n×ばつ⍵÷1⌈(⌽-⍺∘=)⍳n←≢⍵} ×ばつ(≠∨=∘⍳)∘≢)⍣⍵⊢0,⍨⍵⍴1}

Try it on APLgolf!

A dynamic programming adaption of my recursive Python answer. Runs in \$ \mathcal{O}(n^2) \$. A brute force approach would 25 bytes:

{⊃+⌿⍺=1+↑∪(+/∘.<⍨) ̈,⍳⍵⍴⍵}

Try it on APLgolf!

Nekomata + -n, 11 bytes

RJ:mhmj↕ũh=

Attempt This Online!

RJ:mhmj↕ũh= Take input n, k
R Range from 1 to n
 J Split the range into a list of parts
 :mhm Replace every element in each part with the head of the part
 For example, [[1],[2,3],[4,5]] -> [[1],[2,2],[4,4]]
 j Join the list of parts into a single list
 ↕ Take a permutation
 ũ Remove duplicate permutations
 h= Check if the head of the list is equal to k

-n counts the number of solutions.

JavaScript (ES6), 63 bytes

A port of ovs' great Python answer. Now including the optimization suggested by xnor.

Expects (n, k).

f=(n,k,d=1)=>(--n?n*=(~d+k&&f(n,k,d+1))+f(n,k-d):1)/(d-!~-k||1)

Try it online!

JavaScript (ES7), 114 bytes

Expects (n)(k).

n=>k=>eval("for(j=t=n**n;j--;)t-=(a=[...Array(n)].map((_,i)=>x=j/n**i%n|0)).some(r=>a.map(v=>q-=v<r,q=r)|q|~x+k)")

Try it online!

Commented

This is a version without eval() for readability.

n => // outer function taking n
k => { // inner function taking k
 for( // loop:
 j = t = n ** n; // start with j = t = n ** n, where:
 // j = iteration counter
 // t = success counter
 j--; // stop once j = 0 has been processed
 ) //
 t -= // decrement t for each failure
 ( a = // let a[] be an array of n entries,
 [...Array(n)] // which are turned into 0-indexed rankings
 .map((_, i) => // for each value at index i in a[]:
 x = // save the last value in x
 j / n ** i // fill with an integer in [0 .. n-1],
 % n | 0 // according to j and i
 ) // end of map()
 ).some(r => // for each ranking r in a[]:
 a.map(v => // for each ranking v in a[]:
 q -= v < r, // decrement q if v < r
 q = r // starting with q = r
 ) // end of map()
 | q // some() is triggered if q != 0
 | ~x + k // or x != k - 1 (i.e. the last ranking
 // is not Alice's ranking)
 ); // end of some() / end of for()
 return t // return the success counter
} //

05AB1E, 15 bytes

L¤ãʒ<Ðδ›OQ}€нQO

Port of @totallyhuman's Python answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

L # Push a list in the range [1, first (implicit) input-integer n]
 ¤ # Push its last item (without popping): n
 ã # Cartesian product to get all n-sized lists using [1,n]-ranged integers
 ʒ # Filter it by:
 < # Decrease all values in the list by 1
 Ð # Triplicate the list
 δ # Pop two, and apply double-vectorized:
 › # Larger than check
 O # Sum each inner list/row together
 Q # Check if this list of sums equals the original list we've triplicated
 }€н # After the filter: only leave the first item of each remaining list
 Q # Check for each whether it equals the second (implicit) input-integer k
 O # Sum those checks together
 # (which is output implicitly as result)

Jelly, 27 bytes (fast version)

c×ばつc×ばつ÷8

A dyadic Link that accepts \$n\$ on the left and \$k\$ on the right and yields the count of weak orderings given a labelled item's rank.

Try it online! Or see the test-suite.

How?

First calculates the first \$n+1\$ Fubini numbers (A000670): \$F(a) \forall a \in [0,n]\$.

This is achieved by expanding the recursive calculation \$F(a) = \sum_{j=1}^a{F(a-j)\binom{a}{j}}, F(0)=1\$ as a reduction of dot-products over the relevant portion of Pascal's triangle. (I think this can probably be golfed a little by using the recursive calculation itself.)

Then uses that to calculate half of the number of necklaces of partitions of n+1 labelled beads (\$\frac{1}{2}\$A000629) which is simply \$F\$ but with the first term halved: \$\frac{N(a)}{2} \forall a \in [0,n]\$

Finally applies the formula suggested by Nitrodon in the comments:

$$R(n,k)=F(k-1)N(n-k)\binom{n-1}{k-1}$$

c×ばつc×ばつ÷8 - Link: n, k
 € - for each {v in [1..n]}:
 Ɱ` - map across {w in [1..v]} with:
c - {v} choose {w}
 U - reverse each -> [[1C1], [2C2, 2C1], [3C3, 3C2, 3C1], ...]
 ƒ1 - starting with 1 reduce by:
 \ - last two links as a dyad f(current, next):
 ḋ - {current} dot-product {next}
 ; - {current} concatenate {that}
 -> [F(a) for a in [0..n]] = Fubinis
 Ʋ - last four links as a monad - f(Fubinis):
 H1¦ - halve the first term
 Ṗ - remove the last term
 Ṛ - reverse
 , - pair {Fubinis} -> [Necklaces/2, Fubinis]
 9ịⱮ - kth element of each -> [N(n-k)/2, F(k-1)]
 P - product
 Ḥ - double -> F(k-1)*N(n-k)
 c - {n} choose {k}
 ×ばつ - multiply -> F(k-1) * N(n-k) * nCk
 ×ばつ - multiply by {k}
 ÷8 - divide by {n} -> F(k-1) * N(n-k) * (n-1)C(k-1)

Ruby, 212 bytes

... but runs in polynomial time!

def f(n)=n<1?1: n*f(n-1)
$r={}
def r(n, k)=$r[[n,k]]=k**n-(1...k).sum{|i|f(k)/f(i)/f(k-i)*$r[[n,i]]}
def q(x)=x<1?1:(1..x).sum{|i|r(x,i)}
def s(n, k)=(0..(n-k)).sum{|e|f(n-1)/f(k-1)/f(n-k-e)/f(e)*q(k-1)*q(n-k-e)}

The final solution is function s, which takes n and k as arguments.

How does it work?

Divides n - 1 people into three categories: those who were strictly better than Alice, those who were equal, and those strictly worse. We know that exactly k - 1 people ranked better than Alice, we just need to iterate over how many were equal: minimum of 0, maximum n - k.

There are 3 auxiliary functions. Function f is just factorial definition. Function r calculates how many ways to distribute n people into exactly k distinct ranks, and must be memoized else the running time goes exponential. Function q calculates how many ways do distribute x people into any number of ranks (it is just a summation of r).

Charcoal, 36 bytes

NθNηILΦEXθ⊖θ⊞O%÷ιXθ...0⊖θθ⊖η⬤ι=λLΦι‹νλ

Try it online! Link is to verbose version of code. Explanation: Based on @totallyhuman's Python answer.

Nθ Input `n` as a number
 Nη Input `k` as a number
 θ Input `n`
 X Raised to power
 θ Input `n`
 ⊖ Decremented
 E Map over implicit range
 ι Current value
 ÷ Vectorised integer divided by
 θ Input `n`
 X Vectorised raised to power
 ... Range from
 0 Literal integer `0` to
 θ Input `n`
 ⊖ Decremented
 % Vectorised modulo
 θ Input `n`
 ⊞O Concatenated with
 η Input `k`
 ⊖ Decremented
 Φ Filtered where
 ι Current list
 ⬤ All elements satisfy
 ι Current list
 Φ Filtered where
 ν Inner element
 ‹ Is less than
 λ Outer element
 L Take the length
 = Equals
 λ Current element
 L Take the length
 I Cast to string
 Implicitly print

Jelly, 13 bytes (golf version)

ṗ`<Ɱ`§‘ƊƑƇḢ€ċ

A dyadic Link that accepts \$n\$ on the left and \$k\$ on the right and yields the count of weak orderings given a labelled item's rank.

Try it online! Or see the test-suite.

How?

ṗ`<Ɱ`§‘ƊƑƇḢ€ċ - Link: n, k
ṗ` - {n} Cartesian power {n} -> all length n words of alphabet [1..n]
 Ƈ - filter keep those for which:
 Ƒ - is invariant under?:
 Ɗ - last three links as a monad - f(word):
 <Ɱ` - {word} less than mapped over {word}
 § - sums -> [count of elements less than i for i in word]
 ‘ - increment {those}
 -> all valid rankings
 Ḣ€ - head each -> Alice's rank in each valid ranking
 ċ - count occurrences of {k}

Python3, 222 bytes

from itertools import*
R=range
def f(n,k):
 t=0
 q=[(1,{*R(n)},{})]
 for a,b,c in q:
 if not b:t+=c.get(k,[-1])[0]==0
 else:
 for i in R(len(b)):
 for C in combinations(b,i+1):q+=[(a+i+1,b-{*C},{**c,a:C})]
 return t

Try it online!

JavaScript (Node.js), 120 bytes

n=>g=(k,...s)=>(s[n-1]?k==s[0]&[...s].sort((a,b)=>a-b).every(u=(t,i)=>t==u|(u=t)==i+1):g(k,n,...s))+(--s[0]?g(k,...s):0)

Try it online!

Desmos, 102 bytes

f(n,k)=∑_{a=0}^{n^n/n-1}0^{[(B[B<i].count-i)^2fori=B].max}
B=mod(floor((na+(k-1)n^n)/n^{[1...n]}),n)

Try It On Desmos!

Try It On Desmos! - Prettified

Eh, this is so scuffed but it works so whatever lmao.

• code-golf
• math
• combinatorics