16
\$\begingroup\$

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.

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

8 Answers 8

7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

PARI/GP, 46 bytes

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

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 55 bytes

⊞υE²¬ιFN⊞υ⊞OE⁺²ιΣE∨κ¹×§§υ⁻ιμ⁻κ∧μ⊕μ÷Π⁻⊕ι…⁰⊕μΠ…·¹⊕μ⁰I§⊟υN

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.

⊞υE²¬ι

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

FN

Loop \$ R \$ times.

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

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) $$

I§⊟υN

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.