17
\$\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!

\$\endgroup\$
5
  • 5
    \$\begingroup\$ This is A000254. \$\endgroup\$ – FryAmTheEggman Mar 15 '20 at 18:16
  • 2
    \$\begingroup\$ @FryAmTheEggman OEIS, removing the fun of all sequence-related challenges since God knows when \$\endgroup\$ – RGS Mar 15 '20 at 18:20
  • 8
    \$\begingroup\$ always check OEIS before you post... \$\endgroup\$ – ZaMoC Mar 15 '20 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 '20 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 '20 at 19:17

20 Answers 20

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)
\$\endgroup\$
8
  • 2
    \$\begingroup\$ What sorcery is this? \$\endgroup\$ – RGS Mar 15 '20 at 18:29
  • \$\begingroup\$ me: thinks i did something in jelly // jonathan allan: hello \$\endgroup\$ – hyper-neutrino Mar 15 '20 at 18:31
  • 2
    \$\begingroup\$ Still submitted a five when there was a four :p \$\endgroup\$ – Jonathan Allan Mar 15 '20 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 '20 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 '20 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}$$

\$\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 '20 at 19:56
  • \$\begingroup\$ @FryAmTheEggman No worries! I was just a bit puzzled by the reason for changing it. \$\endgroup\$ – Arnauld Mar 15 '20 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\$ ().

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 5 bytes

!IL÷O

Try it online!

\$\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.
\$\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 '20 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!

\$\endgroup\$
3
  • \$\begingroup\$ 49 bytes using walrus operator \$\endgroup\$ – Surculose Sputum Mar 15 '20 at 19:51
  • \$\begingroup\$ @SurculoseSputum thanks! \$\endgroup\$ – Jonathan Allan Mar 15 '20 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 '20 at 0:00
3
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

Tr[#!/Range@#]&     

-1 byte from @Greg Martin

Try it online!

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

Charcoal, 12 bytes

≔…·¹NθIΣ÷Πθθ

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

≔…·¹Nθ

Create a range from 1 to n.

    θ   Range `1`..`n`
   Π    Product i.e. `n!`
  ÷     Vectorised divide by
     θ  Range `1`..`n`
 Σ      Sum
I       Cast to string
        Implicitly print
\$\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.

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

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

\$\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!

\$\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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ this one was hard to beat: {+/*/'1+&:'~=x} or +/*/'1+&:'~=: \$\endgroup\$ – ngn Mar 25 '20 at 19:56
  • \$\begingroup\$ actually, in oK it also works without the final : \$\endgroup\$ – ngn Mar 25 '20 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 '20 at 20:40
  • 1
    \$\begingroup\$ @ngn I tried a different approach \$\endgroup\$ – Galen Ivanov Mar 25 '20 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 '20 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
\$\endgroup\$
0
\$\begingroup\$

Japt -x, 5 bytes

ÆÊ/°X

Try it

\$\endgroup\$
0
\$\begingroup\$

Racket, 70 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Factor, 61 bytes

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

Try it online!

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

\$\endgroup\$
2
  • \$\begingroup\$ 63 bytes by rearranging the operations a bit \$\endgroup\$ – Surculose Sputum Mar 16 '20 at 10:24
  • \$\begingroup\$ @SurculoseSputum Nice refactor - thanks! :-) \$\endgroup\$ – Noodle9 Mar 16 '20 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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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