We're gonna need a bigger podium!

Question

If \$R\$ runners were to run a race, in how many orders could they finish such that exactly \$T\$ runners tie?

Challenge

Given a positive integer \$R\$ and a non-negative integer \$0\leq T\leq {R}\$ produce the number of possible finishing orders of a race with \$R\$ runners of which \$T\$ tied.

Note, however, that runners that tie do not necessarily all tie with each other.

---

You may accept the number of runners that did not tie, \$R-T\$, in place of either \$R\$ or \$T\$ if you would prefer, just say so in your answer. You may also accept just \$R\$ and output a list of results for \$0\leq T \leq R\$.

This is code-golf, so try to make the shortest code in bytes in your language of choice.

---

Examples

1. \$f(R=5, T=0)=120\$

No runners tied and the five runners could have finished in any order, thus \$f(R=5, T=0)=R!=5!=120\$

2. \$f(R=5, T=1)=0\$

There are zero ways for exactly one runner to have tied since ties involve at least two runners.

3. \$f(R=4, T=2)=36\$

• The first two tied - ** * * - \$\binom{4}{2}\binom{2}{1}\binom{1}{1}=6\times 2\times 1=12\$ ways:
  • AB C D AB D C
AC B D AC D B
AD B C AD C B
BC A D BC D A
BD A C BD C A
CD A B CD B A
• The middle two tied - * ** * - \$\binom{4}{1}\binom{3}{2}\binom{1}{1}=4\times 3\times 1=12\$ ways:
  • A BC D A BD C A CD B
B AC D B AD C B CD A
C AB D C AD B C BD A
D AB C D AC B D BC A
• The last two tied - * * ** - \$\binom{4}{1}\binom{3}{1}\binom{2}{2}=4\times 3\times 1=12\$ ways:
  • A B CD A C BD A D BC
B A CD B C AD B D AC
C A BD C B AD C D AB
D A BC D B AC D C AB

4. \$f(R=5, T=5)=21\$

• All five runners tied - ***** - \$\binom{5}{5}=1\$ way
• The first two and the last three tied - ** *** - \$\binom{5}{2}\binom{3}{3}=10\times 1=10\$ ways:
  • AB CDE AC BDE AD BCE AE BCD BC ADE BD ACE BE ACD CD ABE CE ABD DE ABC
• The first three and the last two tied - *** ** - \$\binom{5}{3}\binom{2}{2}=10\times1=10\$ ways:
  • ABC DE ABD CE ABE CD ACD BE ACE BD ADE BC BCD AE BCE AD BDE AC CDE AB

Test cases

R,T => f(R,T)
1,0 => 1
1,1 => 0
2,0 => 2
2,1 => 0
2,2 => 1
3,0 => 6
3,1 => 0
3,2 => 6
3,3 => 1
4,0 => 24
4,1 => 0
4,2 => 36
4,3 => 8
4,4 => 7
5,0 => 120
5,1 => 0
5,2 => 240
5,3 => 60
5,4 => 100
5,5 => 21
7,5 => 5166

As a table, with x if the input does not need to be handled (all of them would be zero):

T R: 1     2     3     4     5     6     7
0    1     2     6    24   120   720  5040
1    0     0     0     0     0     0     0
2    x     1     6    36   240  1800 15120
3    x     x     1     8    60   480  4200
4    x     x     x     7   100  1170 13440
5    x     x     x     x    21   372  5166
6    x     x     x     x     x   141  3584
7    x     x     x     x     x     x   743

---

Isomorphic problem

This is the same as \$a(n=R,k=R-T)\$ which is given in A187784 at the Online Encyclopedia of Integer Sequences as the number of ordered set partitions of \$\{1,2,\dots,n\}\$ with exactly \$k\$ singletons.

Answer 1

MATL, 26 24 bytes

xt:Z^!"@tufm?@&=sqz1G=vs

Inputs T, then R. The code takes a while for R≥5.

Try it online! You can also see the examples: 1, 2, 3, 4. Or verify test cases for R≤4.

Explanation

The program consists of three major steps:

1. Generate all tuples of length R containing (possibly repeated) numbers from the set [1, 2, ..., R].

2. Keep only those tuples such the tuple contains all numbers [1, 2, ..., u], where u is the number of distinct elements in the tuple. So [1 2 1] would be kept, whereas [1 3 1] or [2 3 2] would be rejected.

3. For each tuple that survived the previous step, count how many of its R entries are equal to some other entry. Let this count be e. The output of the program is the amount of tuples for which e equals T.

Answer 2

JavaScript (ES6), 88 bytes

Expects (t)(r).

t=>F=(r,q=r-t,p=1,v=0)=>q|r?v+r&&F(r,q,p,--v)+F(r+v,q-!~v,(g=_=>v?(~r-v)/v++*g():p)()):p

Try it online!

Algorithm

Starting with \$q=r-t\$ and \$p=1\$, we recursively look for all ordered integer partitions of \$r\$. Whenever a new term \$v\$ is added to a given partition \$P\$ of \$r\$:

• we multiply \$p\$ by the number of ways to choose \$v\$ racers among the remaining ones: $$p\gets p\times\binom{r}{v}$$
• we subtract \$v\$ from \$r\$
• we decrement \$q\$ if \$v=1\$

Once a valid partition \$P\$ is complete (ending with \$r=0\$), we test whether we also have \$q=0\$, meaning that there are \$r-t\$ singletons in the finishing order of the race, i.e. \$t\$ ties. If so, we add the product \$p\$ to the final result. Otherwise, we ignore this partition.

Answer 3

PARI/GP, 46 bytes

f(r,t)=Vec(r!/(2-exp(x+O(x^t++))+x)^r-=t-2)[t]

Attempt This Online!

Answer 4

R, 105 bytes

(or 91 bytes in in R≥4.1 by exchanging function for \)

function(r,n)sum(apply(expand.grid(rep(list(1:r),r)),1,function(v)all(1:max(v)%in%v,sum(table(v)<2)==n)))

Attempt This Online!

Input is r=runners, n=non-tied finishers.

Port of Luis Mendo's answer: upvote that one!

---

R + partitions, 95 bytes

(or 81 bytes in R≥4.1 by exchanging function for \)

function(r,n)sum(apply(partitions::setparts(r),2,function(v)prod((sum(table(v)<2)==n):max(v))))

Try it at rdrr.io

Input is r=runners, n=non-tied finishers.

Lazily uses partitions library to gather all set partitions, selects those with n singleton sets, and sums the factorials of the number of sets in each partition to account for the number of possible orders.

Answer 5

05AB1E, 21 15 bytes

LZãʒÐêāQi¢≠OQ]g

-6 bytes by porting @LuisMendo's MATL answer, so make sure to upvote him as well!

Inputs in the order \$R,T\$.

Try it online or verify all test cases.

Original 21 bytes answer:

Lœ€.œ€`€€{Ùʒ€g1ÝKOQ}g

Inputs in the order \$R,T\$.

Brute-force, so pretty slow.

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, first (implicit) input-integer R]
 Zã       # Get the cartesian power of R, creating all possible lists of length R using
          # items of the [1,R]-ranged list, including duplicates
ʒ         # Filter this list of lists by:
 Ð        #  Triplicate the current list
  ê       #  Uniquify and sort the top list
   ā      #  Push a list in the range [1,length] (without popping the list)
    Q     #  Check if the top two lists are equal
 i        #  If this is truthy:
  ¢       #   Pop the remaining two lists, and get the count of each integer
   ≠      #   Check for each count whether it's NOT equal to 1
    O     #   Sum the amount of non-1 counts together
     Q    #   Check if this is equal to the second (implicit) input-integer T
          #  (implicit else: use the current list we've triplicated - which is falsey)
]         # Close both the if-statement and filter
 g        # Pop and push its length to get the amount of remaining valid lists
          # (which is output implicitly as result)

L         # Push a list in the range [1, first (implicit) input-integer R]
 œ        # Get all permutations of this list
  €       # Map over each permutation:
   .œ     #  Get all partitions of this permutation
     €`   # Flatten it one level down to a list of partitions
€         # Map over each partition:
 €        #  Inner map over each part in this partition:
  {       #   Sort the integers in the current part
   Ù      # After the nested map, uniquify the list of partitions with sorted parts
ʒ         # Filter the list of partitions by:
 €g       #  Get the length of each part
   1Ý     #  Push pair [0,1]
     K    #  Remove all 0s and 1s from the list of lengths
      O   #  Sum the remaining lengths (of >=2) together
       Q  #  Check whether this sum is equal to the second (implicit) input-integer `T`
}g        # After the filter: pop and push the length of the remaining partitions
          # (which is output implicitly as result)

Answer 6

Charcoal, 55 bytes

⊞υＥ²¬ιＦＮ⊞υ⊞ＯＥ⁺²ιΣＥ∨κ¹×§§υ⁻ιμ⁻κ∧μ⊕μ÷Π⁻⊕ι…⁰⊕μΠ…·¹⊕μ⁰Ｉ§⊟υＮ

Try it online! Link is to verbose version of code. Takes \$ R \$ and \$ T \$ as parameters. Explanation: Using dynamic programming with a recurrence relation turned out to be a byte shorter than porting @DominicvanEssen's R + partitions answer.

⊞υＥ²¬ι

Start with \$ f(0, 0) = 1 \$ and \$ f(0, 1) = 0 \$.

ＦＮ

Loop \$ R \$ times.

⊞υ⊞ＯＥ⁺²ιΣＥ∨κ¹×§§υ⁻ιμ⁻κ∧μ⊕μ÷Π⁻⊕ι…⁰⊕μΠ…·¹⊕μ⁰

Calculate \$ f(R, T) \$ using the recurrence relation below and append an extra zero for \$ f(R, R + 1) \$.

$$ f(R, T) = R f(R - 1, T) + \sum _ { i = 2 } ^ T \binom R i f(R - i, T - i) $$

Ｉ§⊟υＮ

Output \$ f(R, T) \$.

Answer 7

Nekomata + -n, 13 bytes

R↕J:ᵐo=ᵐ#←¬∑=

Attempt This Online!

Takes input as \$R,R-T\$.

Brute force. Very slow.

R↕J:ᵐo=ᵐ#←¬∑=
R                   Range from 1 to the first input (R)
 ↕                  Non-deterministically choose a permutation
  J                 Split the permutation into a list of lists
   :ᵐo=             Check if all the sublists are sorted
       ᵐ#←¬∑        Count the number of sublists with length 1
            =       Check if the number is equal to the second input (R-T)

-n counts the number of solutions.

Answer 8

Wolfram Language (Mathematica), 57 bytes

SeriesCoefficient[1/(2-Exp@x+x-y*x),{x,0,R},{y,0,R-T}]*R!

Try it online!

Accroding to the question description, this is the same as \$a(n=R,k=R-T)\$ which is given in A187784 at the Online Encyclopedia of Integer Sequences as the number of ordered set partitions of \$\{1,2,\dots,n\}\$ with exactly \$k\$ singletons.