12
\$\begingroup\$

Consider the following probability puzzle.

We start with a string of bits all set to 0. At each step we choose a bit uniformly and independently at random and flip it. The value your code has to compute is the probability of getting to the all 1s bit string before you get back to the all 0s bit string.

Let \$n\$ be the length of the starting bitstring.

Examples:

\$n = 1\$. The output is 1.

\$n = 2\$. The output is 1/2.

\$n = 3\$. The output is 2/5.

The remaining outputs for n up to 20 are:

3/8,3/8,5/13,60/151,105/256,35/83,63/146,630/1433,1155/2588,6930/15341,12870/28211,24024/52235,9009/19456,9009/19345,17017/36362,306306/651745,2909907/6168632.

Your code should take \$n\$ as the input and give the right output. The output must be exact, for example as a fraction. There is no need for the fraction to be fully reduced.

Your code must work for \$n\$ up to at least \$20\$ and run without timing out on TIO .

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can we take n as zero-indexed? \$\endgroup\$ – Manish Kundu Mar 28 at 18:03
  • \$\begingroup\$ @ManishKundu Yes that's fine \$\endgroup\$ – Anush Mar 28 at 18:10
  • 2
    \$\begingroup\$ This seems to be \$\frac{A046826}{A046825}\$. A046826 / A046825. \$\endgroup\$ – tsh Mar 29 at 2:32
  • \$\begingroup\$ Is it allowed to output in factorial base? \$\endgroup\$ – Command Master Mar 29 at 9:55
  • 3
    \$\begingroup\$ @CommandMaster I don't know what that means but I think the answer is no. \$\endgroup\$ – Anush Mar 29 at 10:11

10 Answers 10

9
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes

$$n! \div \left( \sum ^n _{k=0} k!(n-k)! \right)$$

#!/Sum[k!(#-k)!,{k,0,#}]&

Try it online!

-4 bytes from @ovs

\$\endgroup\$
5
  • \$\begingroup\$ Exactly the same answer I had :)) \$\endgroup\$ – Manish Kundu Mar 28 at 18:10
  • \$\begingroup\$ 26 bytes by using the definition of the binomial coefficient. \$\endgroup\$ – ovs Mar 28 at 18:23
  • 1
    \$\begingroup\$ What's the origin of this formula? I was going to approach this as finding the eigenvectors of a matrix representing the transition probabilities... is there a connection to that or is this an entirely different method? \$\endgroup\$ – Jonah Mar 28 at 19:23
  • 1
    \$\begingroup\$ @Jonah oeis.org/A046825 \$\endgroup\$ – ZaMoC Mar 28 at 19:41
  • \$\begingroup\$ @Jonah a linear algebra solution would be great but might be hard to do exactly? \$\endgroup\$ – Anush Mar 28 at 21:12
8
\$\begingroup\$

M, 7 6 bytes

cRİS‘İ

Try it online!

M is Jelly's more mathematical (and out-of-date) sibling. While Jelly uses floating point maths, M uses rational numbers where possible.

Similarly to J42161217's Mathematica answer, we use the binomial coefficient. This calculates the exact value of

$$1 \div \left(1 + \sum ^n _{k=1} \frac 1 {\binom n k}\right)$$

How it works

cRİS‘İ - Main link. Takes n on the left
 R     - Range [1, 2, ..., n]
c      - Calculate nCk for each k
  İ    - Inverse; Get the reciprocal of each
   S   - Sum
    ‘  - Increment, to account for nC0
     İ - Inverse; Get the reciprocal again
\$\endgroup\$
3
  • \$\begingroup\$ Can you explain why this formula is correct? \$\endgroup\$ – Anush Mar 28 at 19:14
  • 1
    \$\begingroup\$ @Anush No, my understanding of the maths behind this question isn't good enough. But, if J42161217's answer is valid, then so is mine \$\endgroup\$ – caird coinheringaahing Mar 28 at 19:15
  • \$\begingroup\$ @tsh That was my initial answer, unfortunately, M doesn't have a "range from 0" builtin like Jelly, so it would be a byte longer (check the revision history for the exact code + explanation) \$\endgroup\$ – caird coinheringaahing Mar 29 at 2:53
7
\$\begingroup\$

Factor + math.combinatorics math.unicode, 45 43 bytes

[ dup [0,b] [ nCk -1 ^ ] with map Σ -1 ^ ]

Try it online!

This uses the formula graciously offered in the following M answer.

Edit: use -1 ^ instead of recip since it's 1 byte shorter.

Explanation:

It's a quotation (anonymous function) that takes an (0-indexed) integer as input and returns a number (probably a ratio) as output. Assuming 4 is on top of the data stack when this quotation is called...

  • dup Duplicate TOS (top of stack). Stack: 4 4
  • [0,b] Create a range object from the number at TOS (0 to 4 inclusive). Stack: 4 T{ range f 0 5 1 }
  • [ nCk -1 ^ ] Push a quotation to the data stack to be used later by with. Stack: 4 T{ range f 0 5 1 } [ nCk -1 ^ ]
  • with Partial application on the left. It sticks that 4 that's been lingering on the data stack into the quotation that's about to be used by map in such a way that it comes before the range elements being mapped over. Stack: T{ range f 0 5 1 } [ 4 [ nCk -1 ^ ] swapd call ]
  • map Apply a quotation to each element of a sequence, collecting the results into a sequence of the same size. (Inside the quotation now...) Stack: 4 0
  • nCk Outputs the total number of unique combinations of size TOS that can be taken from a set of size NOS (next on stack). Also known as 4 choose 0. Stack: 1
  • -1 ^ Take the reciprocal. Shorter than 1 swap / and recip. Stack: 1
  • Now map applies the quotation to each element of the range sequence and we end up with... Stack: { 1 1/4 1/6 1/4 1 }
  • Σ Take the sum of a sequence. Stack: 2+2/3
  • -1 ^ Take the reciprocal. Stack: 3/8.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice! I've found a same-length alternative using locals (maybe you can find some other golf in this): Try it online! \$\endgroup\$ – Leo Mar 29 at 0:54
5
\$\begingroup\$

Python 2, 85 bytes

n=input()
B=9**9;p=1;q=0
for i in range(n+1):x=(B+1)**n/B**i%B;q=p+x*q;p*=x
print p,q

Try it online!

A nice solution made uglier by the requirement that we output an exact fraction. With floats, it looks like:

62 bytes

lambda n,B=9**9:1/sum(1./((B+1)**n/B**i%B)for i in range(n+1))

Try it online!

We use the formula $$ \left(\sum ^n _{i=0} {\binom n i}^{-1}\right)^{-1}$$ and compute the binomials coefficients using this trick. This gives us a sleeves-rolled-up solution without any imports or built-ins for factorial or binomial coefficients.

The original code implements fraction arithmetic by updating the fraction p/q. It might be shortenable but I don't really care to golf it. A more direct but longer conversion uses the fractions library:

94 bytes

from fractions import*
lambda n,B=9**9:1/sum(1/Fraction(((B+1)**n/B**i%B))for i in range(n+1))

Try it online!


This replace-and-evaluate monstrosity would save bytes over the floats version, but it gives wrong answers where some \$\binom{n}{i}\$ ends in a zero digit.

56 bytes, doesn't work

lambda n:1/eval(`(10**17+1)**n`.replace('0'*9,'e0+1./'))

Try it online!

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

Python 2,  83  77 bytes

-4 thanks to dingledooper! (from math import factorial as f -> f=lambda n:0**n or n*f(n-1))
-2 thanks to ovs! (0**n or -> n<1or)

f=lambda n:n<1or n*f(n-1)
lambda n:(f(n),sum(f(i)*f(n-i)for i in range(n+1)))

An unnamed function accepting n that returns a tuple (numerator, denominator) (not simplified).

Try it online! (1-20, including simplified fraction)

\$\endgroup\$
6
  • \$\begingroup\$ 80 bytes \$\endgroup\$ – dingledooper Mar 29 at 0:09
  • \$\begingroup\$ Thanks @dingledooper! \$\endgroup\$ – Jonathan Allan Mar 29 at 0:30
  • 1
    \$\begingroup\$ It looks like it's shorter to calculate factorial manually \$\endgroup\$ – dingledooper Mar 29 at 3:20
  • \$\begingroup\$ @dingledooper I should really have tried that too. Thanks! \$\endgroup\$ – Jonathan Allan Mar 29 at 12:21
  • \$\begingroup\$ n<1or ... saves 2 bytes in the factorial function. If you don't like the (True, 1) output for 0, change f(n) to +f(n) in the main function. \$\endgroup\$ – ovs Mar 29 at 12:58
2
\$\begingroup\$

Jelly, 7 bytes

5 bytes with cŻİSİ if we may print with floating point inaccuracy.

cŻPṄ:ƊS

A full program printing a numerator and then a denominator (not simplified).

Try it online!

How?

cŻPṄ:ƊS - Main Link: integer, n
 Ż      - zero range -> [0,1,2,...,n]
c       - (n) choose (that) (vectorises) -> [1, n, ..., n, 1] (Pascal row n)
     Ɗ  - last three links as a monad - f(Pascal row n):
  P     -   product (of Pascal row n)
   Ṅ    -   print (product) and a newline; yield (product)
    :   -   (product) integer divide (Pascal row n) (vectorises)
      S -   sum
        - implicit print
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 61 bytes

n=>[(g=n=>n?n*g(~-n):1)(n),(h=k=>g(k)*g(n-k)+(k&&h(~-k)))(n)]

Try it online!

Search the sample output given by OP on OEIS, and you may find out A046825. Use the formula given on that page:

$$ \begin{split} f(n) & = \frac{1}{\sum_{k=0}^{n}\frac{1}{C_n\left(k\right)}} \\ & = \frac{1}{\sum_{k=0}^{n}\frac{k!\left(n-k\right)!}{n!}} \\ & = \frac{n!}{\sum_{k=0}^{n}k!\left(n-k\right)!} \end{split} $$

It may need +1 byte (change 1 to 1n) if larger (\$n>21\$) testcases is required.

Note: I have no idea why it works.

\$\endgroup\$
3
  • \$\begingroup\$ How can I improve the explanation in my answer as to how that formula works? \$\endgroup\$ – Neil Mar 29 at 9:53
  • 1
    \$\begingroup\$ @Neil I don't know. Maybe give a proof as what math textbooks do. And everyone would give up understanding it. :) \$\endgroup\$ – tsh Mar 29 at 10:14
  • \$\begingroup\$ No, I didn't mean a proof, I meant that I found a sequence with a comment that gives the direct solution to the problem in terms of that sequence, rather than guessing the formula from the sequence that turns up when you search the terms. \$\endgroup\$ – Neil Mar 29 at 10:43
2
\$\begingroup\$

Charcoal, 24 bytes

FN⊞υ∨¬ι×⌈υιI⟦⌈υΣE⮌υ×ι§υκ

Try it online! Link is to verbose version of code. Explanation: Flipping n random bits in a string is equivalent to a random walk over the vertices of an n-dimensional hypercube; moving along an edge corresponds to flipping one of the bits. The starting point is the string of all 0s and the diagonally opposite vertex is the string of all 1s. The probability that it visits that vertex before it returns to the starting point is then documented in the linked page as being (n-1)!/A003149(n-1).

FN⊞υ∨¬ι×⌈υι

Input n and calculate the factorials up to n-1.

I⟦⌈υΣE⮌υ×ι§υκ

Output (n-1)! as the numerator and the sum of the termwise product of the factorials with their reverse as the denominator.

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

05AB1E, 6 9 8 bytes

-1 thanks to Command Master.

!,Ý!Â*O,

Try it online!

!,Ý!Â*O,  # full program
 ,        # output...
          # implicit input...
!         # factorial
       ,  # output...
      O   # sum of...
  Ý       # [0, 1, 2, ...,
          # ..., implicit input...
  Ý       # ]...
          # (implicit) with each element...
   !      # factorial...
          # (implicit) with each element...
     *    # multiplied by...
          # (implicit) corresponding element in...
  Ý       # [0, 1, 2, ...,
          # ..., implicit input...
  Ý       # ]...
          # (implicit) with each element...
   !      # factorial...
    Â     # reversed
\$\endgroup\$
7
  • 2
    \$\begingroup\$ "The output must be exact, for example as a fraction." Unless 05AB1E uses exact reciprocals, this is an invalid answer \$\endgroup\$ – caird coinheringaahing Mar 29 at 1:01
  • \$\begingroup\$ @ChartZBelatedly It does give exact output. \$\endgroup\$ – Makonede Mar 29 at 1:15
  • 1
    \$\begingroup\$ 05AB1E uses floating point arithmetic, therefore the output may look exact (up to a certain number of decimal places), but it will fail for certain inputs, due to floating point issues \$\endgroup\$ – caird coinheringaahing Mar 29 at 1:23
  • 1
    \$\begingroup\$ Additionally, I can confirm that reciprocal is inexact, through testing and digging through the source code (it's just 1 / to_number(a) and to_number gives normal number types, and I don't believe Elixir uses exact arithmetic) \$\endgroup\$ – hyper-neutrino Mar 29 at 1:24
  • 1
    \$\begingroup\$ !,Ý!Â*O, 8 bytes \$\endgroup\$ – Command Master Mar 29 at 9:33
1
\$\begingroup\$

R, 45 40 bytes

Using J42161217's Mathematica answer, and following Guiseppe's astounding improvement,

   function(n,`!`=gamma)c(!n,(!1:n)%*%!n:1)

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 40 bytes - quite apart from the nice effect of using ! as the factorial, ! has lower precedence than * (where unary - has higher precedence) so we can remove one pair of parentheses. \$\endgroup\$ – Giuseppe Mar 29 at 19:32

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.