# We're gonna need a bigger podium!

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 , 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.

• For cases where T=1, can we output the same as T=0? Mar 19 at 3:34
• @emanresuA no, T=1 is in bounds and should produce zero. Mar 19 at 4:03
• Can I take only $R$ and output a list of the answers for all $0 \leq T \leq R$? Mar 19 at 16:55
• @CommandMaster I'll allow that (though hopefully not just to avoid a fetch but rather to make for an interesting golf). Mar 19 at 21:33

# 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.

# 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.

# PARI/GP, 46 bytes

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


Attempt This Online!

# 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.

# 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\$$.

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


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

Brute-force, so pretty slow.

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)


# 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) \$$.

# 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.

# 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.