# Permutation formula n!/(n-r)!

**URL:** <https://discourse.julialang.org/t/permutation-formula-n-n-r/123040>\
**Category:** New to Julia\
**Created:** [November 25, 2024, 7:22am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040 "2024-11-25T07:22:51Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 25, 2024, 7:22am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/1 "2024-11-25T07:22:51Z")

</div>

Hello,  
To calculate the formula **n!/(n-r)!**, I wrote the following program:

```julia
function combinations(n, r)
    n = BigInt(factorial(n))
    r = BigInt(factorial(r))
    t = BigInt(factorial(n-r))
    final = BigInt(n / (t * r))
    return final
end

function start()
    print("Please enter N: ")
    n = parse(Int, readline())
    print("Please enter R: ")
    r = parse(Int, readline())
    println(combinations(n, r))
end

start()

```

I got `InexactError` error. How to fix it?

Thank you.

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [November 25, 2024, 7:47am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/2 "2024-11-25T07:47:14Z")

</div>

You need to apply the factorial function to the numbers already converted to BigInt, not convert the numbers to BigInt after the call.

Also… you accidentally reassigned r, so the r.

Also, check out the doc for binomial if you just want the result.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [November 25, 2024, 8:27am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/3 "2024-11-25T08:27:13Z")

</div>

> [@hack3rcon](#):
>
> ```julia
> function combinations(n, r)
> n = BigInt(factorial(n))
> r = BigInt(factorial(r))
> t = BigInt(factorial(n-r))
> final = BigInt(n / (t * r))
> return final
> end
> 
> ```

Here’s a hint for better performance, and less risk of overflow:  
6!/3! = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6/(1\cdot 2\cdot 3) = 4\cdot 5\cdot 6

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [November 25, 2024, 8:36am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/4 "2024-11-25T08:36:08Z")

</div>

Maybe at this point it’s time to think why you are writing this function.

If that’s just to practice reusing your previous results, this implementation is fine.

If that’s to get an idea how things are done in practice, you need to think of how you can simplify the problem. In this implementation, you do enormous calculations to get C\_n^n, which is totally redundant, as we know it’s 1.

The things to notice are:

1. C^n\_k = C^n\_{n-k}. Using this, you can always transform your calculations so that r \ge n / 2.
2. n! / r! = (r+1)(r+2)\dots n, so that it makes sense to make a specialized function for that operation.

In the end, it might be:

```julia
function combinations(n::Integer, r::Integer)
    p = max(r, n - r)

# (p+1)(p+2)...n - implementation is left as an exercise
    numer = factorial_ratio(n, p) 
    denom = factorial(n - p)
    return div(numer, denom)
end

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 25, 2024, 9:16am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/5 "2024-11-25T09:16:09Z")

</div>

In general, stop sharing programs with `readline` inputs because a function call with inputs written into source code is much clearer to us and we can’t guess what you’re typing. You should also generally share an error’s stacktrace so we have some idea where it’s happening.

In this specific case however, it’s more apparent where things are going wrong. We know that the combination formula should always have an integer value, ignoring overflow issues. `InexactError`s happen when you try to convert non-integer values to integer types. Let’s see what you’re computing:

```julia
function combinations(n, r)
    n = BigInt(factorial(n)) # n!
    r = BigInt(factorial(r)) # r!
    t = BigInt(factorial(n-r))# (n!-r!)!
    final = BigInt(n / (t * r)) # n!/ ((n!-r!)! * r!)
    return final
end

```

Reusing variable names ruined the formula, you are neither calculating the permutation formula n!/(n-r)! in your title nor the combination formula n!/(r!(n-r)!) in your actual code. Trailing `!` are legal in variable names:

```julia
julia> function combinations2(n, r)
           n! = BigInt(factorial(n)) # n!
           r! = BigInt(factorial(r)) # r!
           n_r! = BigInt(factorial(n-r))# (n-r)!
           final = BigInt(n! / (n_r! * r!)) # n!/ ((n-r)! * r!)
           final
       end
combinations2 (generic function with 1 method)

julia> combinations2(4, 3)
4

```

But I don’t like that much because `n_r!` was very easy to mistype as `n-r!` and that mistake is only caught at runtime.

The less immediate issue is that your type conversions are misguided (`combinations2` does not fix this). If you want to deal with big integers, `n` and `r` need to be `BigInt` to begin with. There’s no point in erroring on `factorial(21)` before attempting to convert to `BigInt`. Dividing 2 `BigInt`s is also problematic because it makes a `BigFloat`, which is designed to have a limited but adjustable precision. If you don’t fix any possible precision losses from that, converting to `BigInt` afterward won’t help. Since n!/r! or n!/(n-r)! is a product of a sequence of integers, try to pick the `prod` call to minimize intermediate values.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 25, 2024, 9:29am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/6 "2024-11-25T09:29:14Z")

</div>

Hello,  
I changed my code as below:

```julia
function combinations(n, r)
    n = BigInt(factorial(n))
    r = BigInt(factorial(r))
    v = BigInt(n - r)
    t = BigInt(factorial(v))
    final = BigInt(n / (t * r))
    return final
end

```

I got the following error:

```julia
Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 25, 2024, 9:31am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/7 "2024-11-25T09:31:03Z")

</div>

Thanks for providing the `readline` inputs for clarity, but you should share the other lines in the error’s stacktrace for clarity as well. That aside, you’re running into the same error because you didn’t fix the reusage of variable names that ruined the formula.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 25, 2024, 9:37am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/8 "2024-11-25T09:37:43Z")

</div>

Thanks.  
The new code is:

```julia
function combinations(n, r)
    x = BigInt(factorial(n))
    z = BigInt(factorial(r))
    t = BigInt(factorial(x - z))
    final = BigInt(x / (t * z))
    return final
end

```

And error is:

```julia
Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)
Stacktrace:
  [1] BigInt(x::BigFloat)
    @ Base.MPFR ./mpfr.jl:374
  [2] combinations(n::Int64, r::Int64)
    @ Main ~/Julia/File.jl:249
  [3] star()
    @ Main ~/Julia/File.jl:257
  [4] top-level scope
    @ ~/Julia/File.jl:259
  [5] include(fname::String)
    @ Base.MainInclude ./client.jl:489
  [6] run(debug_session::VSCodeDebugger.DebugAdapter.DebugSession, error_handler::VSCodeDebugger.var"#3#4"{String})
    @ VSCodeDebugger.DebugAdapter ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/DebugAdapter/src/packagedef.jl:122
  [7] startdebugger()
    @ VSCodeDebugger ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/VSCodeDebugger/src/VSCodeDebugger.jl:45
  [8] top-level scope
    @ ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/debugger/run_debugger.jl:12
  [9] include(mod::Module, _path::String)
    @ Base ./Base.jl:495
 [10] exec_options(opts::Base.JLOptions)
    @ Base ./client.jl:318
 [11] _start()
    @ Base ./client.jl:552
in expression starting at /Julia/File.jl:259
 * Terminal will be reused by tasks, press any key to close it.

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 25, 2024, 9:41am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/9 "2024-11-25T09:41:41Z")

</div>

Still the same error over the exact same value. It’s really worth commenting through your lines to 100% know what you’re computing

```julia
function combinations(n, r)
    x = BigInt(factorial(n)) # n!
    z = BigInt(factorial(r)) # r!
    t = BigInt(factorial(x - z)) # (n! - r!)!
    final = BigInt(x / (t * z)) # n! / ( (n! - r!)! * r! )
    return final
end

```

`t = BigInt(factorial(x - z))` does (n! - r!)!, that is nowhere in the permutations or combinations formula. See my first comment for an edit where this particular mistake is fixed.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 25, 2024, 9:44am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/10 "2024-11-25T09:44:55Z")

</div>

Thank you so much.  
The correct version is as follows:

```julia
function combinations(n, r)
    x = BigInt(factorial(n))
    z = BigInt(factorial(r))
    t = BigInt(factorial(n - r))
    final = BigInt(x / (t * z))
    return final
end

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [November 25, 2024, 10:59am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/11 "2024-11-25T10:59:43Z")

</div>

> [@hack3rcon](#):
>
> `BigInt(factorial(n))`

You are still ignoring that you have to convert to `BigInt` _before_ calculating the factorial: `factorial(BigInt(n))` etc.

Also, you are ignoring the advice that:

> [@DNF](#):
>
> 6!/3! = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6/(1\cdot 2\cdot 3) = 4\cdot 5\cdot 6

And finally, you are ignoring the advice to not use floating point division.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 25, 2024, 1:45pm UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/12 "2024-11-25T13:45:48Z")

</div>

> [@hack3rcon](#):
>
> ```julia
> function combinations(n, r)
> x = BigInt(factorial(n))
> z = BigInt(factorial(r))
> t = BigInt(factorial(n - r))
> final = BigInt(x / (t * z))
> return final
> end
> 
> ```

As @DNF said, to avoid overflow you need to convert to `BigInt` _before_ computing factorials. It’s easiest to do this once, before the subsequent calls:

```julia
function combinations(n, r)
    nbig, rbig = BigInt(n), BigInt(r) # convert to BigInt to avoid overflow
    x = factorial(nbig)
    z = factorial(rbig)
    t = factorial(nbig - rbig)
    final = div(x, t * z) # use integer division, not /
    return final
end

```

Note that this corresponds to the built-in `binomial(n, r)` function.

There are more efficient ways of computing it by canceling terms from the factorials in the numerator and denominator analytically, as @DNF mentioned, but you want to focus on correctness before worrying about performance.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [November 25, 2024, 3:59pm UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/13 "2024-11-25T15:59:04Z")

</div>

Are you a ChatGPT bot? Why give the exact same code again and say “The new code is:” or “The correct version is as follows:”?

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 26, 2024, 6:26am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/14 "2024-11-26T06:26:11Z")

</div>

Hi,  
Thanks.  
But `n` and `r` are ordinary integers. Why does a memory overflow occur?

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 26, 2024, 6:29am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/15 "2024-11-26T06:29:45Z")

</div>

Hi,  
No, I’m not.  
First of all, why do you think something like ChatGPT hasn’t existed before? Second, I don’t know what benefit a bot-based Q&A would have for a newbie like me?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 26, 2024, 6:57am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/16 "2024-11-26T06:57:18Z")

</div>

> [@hack3rcon](#):
>
> But `n` and `r` are ordinary integers. Why does a memory overflow occur?

Fixed precision integer datatypes generally silently overflow (or underflow). It doesn’t mean you run out of memory (that’ll be an `OutofMemoryError` or some sort of crash) and it isn’t the kind of overflow where you write to the wrong memory addresses, it’s the value circling when the computation attempts to go outside its range. For an easy example, imagine a 2-bit signed integer. Its values are only -2, -1, 0 and 1. There cannot be a value of 2, so if you attempt 1+1, you circle back to -2.

> [@Henrique\_Becker](#):
>
> Are you a ChatGPT bot? Why give the exact same code again and say “The new code is:” or “The correct version is as follows:”?

Respectfully, I haven’t seen OP repeat code in this thread and I double checked just now. They were editing variable names as I suggested, albeit in a few attempts that didn’t fix the formula error.

While formulaic responses are characteristic of generative AI, they are ALSO characteristic of people who have less experience in English. Similarly, GPT detectors were observed to [misidentify non-native speakers](https://arxiv.org/abs/2304.02819) at a higher rate, paradoxically reducing the detection rate after the submitted essays’ vocabulary was edited by ChatGPT. I think we should be more cautious before making inflammatory accusations, be more open to other explanations.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [November 26, 2024, 6:58am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/17 "2024-11-26T06:58:06Z")

</div>

It is an _integer overflow_. The largest Int64 is `typemax(Int64)` (gives 9223372036854775807). When you exceed this value then it “wraps around” to the negatives:

```julia-repl
julia> typemax(Int64)+10
-9223372036854775799

julia> typemax(Int64)*2
-2

```

Since factorial grows very fast this happens very easily. In fact for Int64 the first factorial to overflow is only 21:

```julia-repl
julia> factorial(20)
2432902008176640000

julia> factorial(21)
ERROR: OverflowError: 21 is too large to look up in the table; consider using `factorial(big(21))` instead
# Stacktrace

```

This is why the folks in this thread (and also the helpful error message) advise you to use `BigInt` instead which indeed will fill up the memory instead of overflowing.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 26, 2024, 7:10am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/18 "2024-11-26T07:10:17Z")

</div>

Thank you so much.  
Could a template like this fix the problem?

```julia
function Test(VARIABLE::Type, VARIABLE::Type)
    <BODY>
end

Test(VARIABLE::Type, VARIABLE::Type)

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 26, 2024, 7:15am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/19 "2024-11-26T07:15:44Z")

</div>

Sorry I can’t tell what problem that could possibly fix or how it’s relevant to anything in this thread. It just looks like an unfinished method for a call taking two types, and I am curious why you wrote this.

---

<div class="post-metadata">

**Author:** ![hack3rcon](https://avatars.discourse-cdn.com/v4/letter/h/96bed5/32.png) [@hack3rcon](https://discourse.julialang.org/u/hack3rcon)\
**Post date:** [November 26, 2024, 7:27am UTC](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040/20 "2024-11-26T07:27:30Z")

</div>

For example, I call the function as follows:

```julia
Test(a::BigInt, b::BigInt)

```

Wouldn’t this automatically convert the values ​​`a` and `b` to BigInt?

[Next page](https://discourse.julialang.org/t/permutation-formula-n-n-r/123040.md?page=2)