18
\$\begingroup\$

The system

Assume the Earth is flat and that it extends infinitely in all directions. Now assume we have one infinitely long train railway and n trains in that railway. All trains have different speeds and all trains are going in the same direction. When a faster train reaches a slower train, the two trains connect (becoming a single train) and the new train keeps going at the speed with which the slower train was going.

E.g., if we have two trains, one going at speed 1 and another at speed 9, the lines below "simulate" what would happen on the railway:

9               1
         9       1
                 11
                  11
                   11

whereas if the trains start in a different order, we'd have

1 9
 1         9
  1                 9
   1                          9
etc...

With that being said, given a train/position/speed configuration there comes a time when no more connections will be made and the number of trains on the railway stays constant.

Task

Given the number n of trains in the railway, your task is to compute the total number of trains there will be on the railway, after all the connections have been made, summing over all n! possible arrangements of the n trains.

A possible algorithm would be:

  • Start counter at 0
  • Go over all possible permutations of the train speeds
    • Simulate all the connections for this permutation
    • Add the total number of remaining trains to the counter
  • Return the counter

Note that you can assume the train speeds are whatever n distinct numbers that you see fit, what really matters is the relationships between train speeds, not the magnitudes of the differences in speeds.

Input

You must take n, a positive integer, as input.

Output

An integer representing the total number of trains that there will be on the railway, summed over all possible permutations of the trains.

Test cases

1 -> 1
2 -> 3
3 -> 11
4 -> 50
5 -> 274
6 -> 1764
7 -> 13068
8 -> 109584
9 -> 1026576
10 -> 10628640
11 -> 120543840
12 -> 1486442880
13 -> 19802759040
14 -> 283465647360
15 -> 4339163001600
16 -> 70734282393600
17 -> 1223405590579200
18 -> 22376988058521600
19 -> 431565146817638400
20 -> 8752948036761600000

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

Improve this question
\$\endgroup\$
5
  • 5
    \$\begingroup\$ This is A000254. \$\endgroup\$
    – FryAmTheEggman
    Mar 15, 2020 at 18:16
  • 2
    \$\begingroup\$ @FryAmTheEggman OEIS, removing the fun of all sequence-related challenges since God knows when \$\endgroup\$
    – RGS
    Mar 15, 2020 at 18:20
  • 8
    \$\begingroup\$ always check OEIS before you post... \$\endgroup\$
    – ZaMoC
    Mar 15, 2020 at 18:30
  • 1
    \$\begingroup\$ Interestingly, whether the trains take the speed of the slower or the faster one when they collide doesn't actually change the final answer, though I don't have a rigorous proof for this (yet). \$\endgroup\$
    – hyper-neutrino ♦
    Mar 15, 2020 at 18:52
  • \$\begingroup\$ @HyperNeutrino I guess the explanation on my answer is a possible way to prove; the explanation can be perfectly adapted to the case where the faster trains stay fast :) \$\endgroup\$
    – RGS
    Mar 15, 2020 at 19:17

20 Answers 20

Reset to default
9
\$\begingroup\$

Jelly,  5  4 bytes

!:RS

Try it online! Or see the test-suite.

How?

When we introduce an \$n^{\text{th}}\$ train it allows:

  • \$(n-1)!\$ states - by being placed behind none of the \$n-1\$ existing trains and being faster than all of them.
  • all the previous end states, each in \$n\$ different ways - by being placed behind at least one existing train and being faster than \$[0,n-1]\$ of the \$n-1\$ existing trains

We know \$a(1) = 1\$ so... 

n  a(n) 
1  1
2  1! + 1*2
3  2! + 1!*3 + 1*2*3
4  3! + 2!*4 + 1!*3*4 + 1*2*3*4
5  4! + 3!*5 + 2!*4*5 + 1!*3*4*5 + 1*2*3*4*5
... etc

Which is:

n  a(n) 
1  1
2  1 + 2
3  1*2 + 1* 3 + 2*3
4  1*2*3 + 1*2* 4 + 1* 3*4 + 2*3*4
5  1*2*3*4 + 1*2*3* 5 + 1*2* 4*5 + 1* 3*4*5 + 2*3*4*5
...
n  n!/n + n!/(n-1) + n!/(n-2) + ... + n!/1

Hence the code:

!:RS - integer, n
!    - (n) factorial      n!
  R  - range (n)          [1,...,n-2,n-1,n]
 :   - integer division   [n!/1,...,n!/(n-2),n!/(n-1),n!/n]
   S - sum                a(n)
Improve this answer
\$\endgroup\$
8
  • 2
    \$\begingroup\$ What sorcery is this? \$\endgroup\$
    – RGS
    Mar 15, 2020 at 18:29
  • \$\begingroup\$ me: thinks i did something in jelly // jonathan allan: hello \$\endgroup\$
    – hyper-neutrino ♦
    Mar 15, 2020 at 18:31
  • 2
    \$\begingroup\$ Still submitted a five when there was a four :p \$\endgroup\$
    – Jonathan Allan
    Mar 15, 2020 at 18:32
  • 2
    \$\begingroup\$ @htmlcoderexe I am pretty sure RGS was not refering to the terseness of the language but rather the underlying method (which I had not described at the time) \$\endgroup\$
    – Jonathan Allan
    Mar 17, 2020 at 14:28
  • 1
    \$\begingroup\$ @htmlcoderexe Please refer to JonathanAllan's comment above mine :D I have submitted a couple of Jelly answers myself, but I am not very accustomed to its built-ins, so even a short answer like this 4-byter can throw me off... That was what I was referring to :) \$\endgroup\$
    – RGS
    Mar 17, 2020 at 14:36
4
\$\begingroup\$

JavaScript (ES6), 34 bytes

f=n=>n>1?(n+--n)*f(n)-n*n*f(n-1):n

Try it online!

This is an implementation of the recurrence relation:

$$\cases{ a(0)=0\\ a(1)=1\\ a(n) = a(n-1) \times (2n - 1) - a(n-2) \times (n - 1)^2,\:n>1}$$

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'm sorry for the error in editing, I thought I had checked and assumed it was a bug (which was probably silly). \$\endgroup\$
    – FryAmTheEggman
    Mar 15, 2020 at 19:56
  • \$\begingroup\$ @FryAmTheEggman No worries! I was just a bit puzzled by the reason for changing it. \$\endgroup\$
    – Arnauld
    Mar 15, 2020 at 19:58
4
\$\begingroup\$

APL (Dyalog), 5 bytes

+/!÷⍳

Try it online!

Calculates the sum of (+/) the factorial of \$n\$ (!) divided by (÷) the range 1 to \$n\$ (⍳).

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 5 bytes

!IL÷O

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 3, 57 bytes

f=lambda n:n and n*f(n-1)+math.factorial(n-1)
import math

Try it online!

Implements the recurrence relation given by

$$\begin{cases}a(n) = n\times a(n-1) + (n-1)! \\ a(0) = 0 \end{cases}$$

How: If you have \$n\$ trains on the railway, consider removing the faster one from the railway and take the \$(n-1)!\$ permutations of the remaining \$n-1\$ trains. For each permutation of the \$n-1\$ trains, there are \$n\$ places where you can put the \$n\$th train, the fastest one.

  • If you put it in the front, then the connections made by the other \$n-1\$ trains remain exactly the same, and those never catch up with the faster train. So placing it in the front adds a new train to the total sum.
  • If you put it in any other of the \$n - 1\$ positions, it will just connect to the train in front and then we are back at the case when we had \$n - 1\$ trains on the railway, so the total number of trains stays the same.
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You beat me to it! Took me a while to figure out this recurrent relation. I also missed that Python has a factorial function :( \$\endgroup\$
    – Surculose Sputum
    Mar 15, 2020 at 19:24
3
\$\begingroup\$

Python 3.8,  50  49 bytes

-1 thanks to Surculose Sputum (using walrus in 3.8 to save some ~-s)

f=lambda n:n>1and(2*n-1)*f(n:=n-1)-n*n*f(n-1)or n

Try it online!

A 52 using a different approach:

f=lambda n,k=2:n*k and~-n*f(n-1,k)+f(n-1,k-1)or n==k

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 49 bytes using walrus operator \$\endgroup\$
    – Surculose Sputum
    Mar 15, 2020 at 19:51
  • \$\begingroup\$ @SurculoseSputum thanks! \$\endgroup\$
    – Jonathan Allan
    Mar 15, 2020 at 20:03
  • 1
    \$\begingroup\$ @SurculoseSputum I keep seeing your username and thinking it says "Sucralose Spectrum". I need to go to bed. \$\endgroup\$
    – S.S. Anne
    Mar 17, 2020 at 0:00
3
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

Tr[#!/Range@#]&

-1 byte from @Greg Martin

Try it online!

Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ well done beating the builtin Abs@StirlingS1[#+1,2]& \$\endgroup\$
    – Greg Martin
    Mar 16, 2020 at 7:37
  • \$\begingroup\$ @GregMartin I think now I'm done ;) \$\endgroup\$
    – ZaMoC
    Mar 16, 2020 at 13:04
  • \$\begingroup\$ I think you can shave one more byte with Tr[#!/Range@#]& :) \$\endgroup\$
    – Greg Martin
    Mar 16, 2020 at 19:03
2
\$\begingroup\$

Charcoal, 12 bytes

≔…·¹ＮθＩΣ÷Πθθ

Try it online! Link is to verbose version of code. Explanation:

≔…·¹Ｎθ

Create a range from 1 to n.

    θ   Range `1`..`n`
   Π    Product i.e. `n!`
  ÷     Vectorised divide by
     θ  Range `1`..`n`
 Σ      Sum
Ｉ       Cast to string
        Implicitly print
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 2, 57 52 50 bytes

-2 bytes thanks to @JonathanAllan ! 

i=x=0
f=1
exec"i+=1;x=i*x+f;f*=i;"*input()
print x

Try it online!

If the sequence is 0-indexed, we can cut down 2 more bytes

Python 2, 48 bytes

i=x=f=1
exec"i+=1;x=i*x+f;f*=i;"*input()
print x

Try it online!

How: This solution uses the exec trick, which repeats the code n times, then exec the repeated code.

f is the current factorial.
x (the solution function) is defined by the recurrent relation:
$$x(i)=ix(i-1)+(i-1)!$$
and
$$x(0)=0$$

@RGS's answer has a really nice explanation for this formula.

Improve this answer
\$\endgroup\$
2
1
\$\begingroup\$

Perl 6, 22 bytes

{sum [*]($_)X/$_}o^*+1

Try it online!

Returns the sum of the factorial of \$n\$ divided by the range 1 to \$n\$.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

W j, 5 4 bytes

After scanning through the source, I realized an undocumented feature - the j flag can actually sum the output at the end!

7Uëÿ

Uncompressed:

*rak/

Explanation

*r     % Reduce via multiplication
       % (Contains implicit range)
  ak   % Range from input to 1
    /  % Division (integer division when
       % none of the operands are floating-points)
Flag:j % Sum the resulting list
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 34 bytes

a 0=0
a n=n*a(n-1)+product[1..n-1]

Try it online!

This implements the OEIS definition.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 38 bytes

f(n){n=n>1?(n+n--)*f(n)-n*n*f(n-1):n;}

Port of Jonathan Allan's Python 3.8 answer.

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 9 bytes

1#.!%1+i.

Try it online!

1#.           the sum of (by conversion to base 1)
   !          n factorial
    %         divided by
     1+i.     the list 1..n

K (oK), 16 12 bytes

-4 bytes thanks to ngn!

+/*/'1+&:'~=

Try it online!

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ this one was hard to beat: {+/*/'1+&:'~=x} or +/*/'1+&:'~=: \$\endgroup\$
    – ngn
    Mar 25, 2020 at 19:56
  • \$\begingroup\$ actually, in oK it also works without the final : \$\endgroup\$
    – ngn
    Mar 25, 2020 at 20:02
  • \$\begingroup\$ @ngn Very nice use of the identity matrix! (I forgot about the monadic use of =) Thanks for your lesson! \$\endgroup\$
    – Galen Ivanov
    Mar 25, 2020 at 20:40
  • 1
    \$\begingroup\$ @ngn I tried a different approach \$\endgroup\$
    – Galen Ivanov
    Mar 25, 2020 at 21:11
  • 1
    \$\begingroup\$ .. and i forgot oK has atom^ :) one of the things i tried was a^/:a:1+!x \$\endgroup\$
    – ngn
    Mar 25, 2020 at 21:51
0
\$\begingroup\$

Jelly, 9 bytes

Œ!«\€Q€FL

Try it online!

this is the non-smart trivial approach

Explanation

Observe that if we have a list of trains' speeds, moving left, then we can cumulatively reduce by minimum to get the final list of trains' speeds.

Œ!«\€Q€FL  Main Link
Œ!         all permutations (defaults over a range)
    €      For each permutation
   \       Cumulatively reduce by
  «        minimum
      €    For each permutation
     Q     remove duplicate values
       F   join all of the trains (flatten)
        L  and get the final length
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Japt -x, 5 bytes

ÆÊ/°X

Try it

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Racket, 70 bytes

(λ(x)(let([a(range 1(+ 1 x))])(apply +(map(λ(y)(/(apply * a)y))a))))

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Factor, 61 bytes

: f ( n -- n ) [1,b] dup [ product ] dip [ / ] with map sum ;

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 70 \$\cdots\$ 64 63 bytes

Saved a byte thanks to ceilingcat!!!
Saved a byte thanks to Surculose Sputum!!! 

l;c;i;t;f(n){l=0;for(c=i=1;i<n;l=c,c=t)t=-l*i*i+c*(i+++i);n=c;}

Try it online!

Uses Arnauld's formula.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 63 bytes by rearranging the operations a bit \$\endgroup\$
    – Surculose Sputum
    Mar 16, 2020 at 10:24
  • \$\begingroup\$ @SurculoseSputum Nice refactor - thanks! :-) \$\endgroup\$
    – Noodle9
    Mar 16, 2020 at 11:17
0
\$\begingroup\$

MathGolf, 5 bytes

╒k!╠Σ

Try it online.

Or

!k╒/Σ

Try it online.

Explanation:

╒      # Push a list in the range [1, (implicit) input-integer]
 k!    # Push the input-integer again, and pop and push its factorial
   ╠   # Divide the factorial by each value in the list (b/a builtin)
    Σ  # And sum that list
       # (after which the entire stack joined together is output implicitly as result)

!      # Push the factorial of the (implicit) input-integer
 k╒    # Push the input-integer again, and pop and push a list in the range [1, input]
   /   # Divide the factorial by each value in the list
    Σ  # And sum that list
       # (after which the entire stack joined together is output implicitly as result)
Improve this answer
\$\endgroup\$

Your Answer

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

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