<p>Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.</p>

<p>Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.</p>

<p>Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.</p>

<p>Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum_{j \in S} a_{ij}$ which uses $|S|-1$ additions. $\sum_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum_{k=1}^{n} (k-1) \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} - \sum_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$. </p>

<p>Additions for Ryser+Gray: The Gray code version does not give you a smaller <em>formula</em>, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.</p>

CC BY-SA 3.0
2011-11-09T13:01:01.570Z
Are you sure about Ryser + Gray count? It seems to give $3 \times 6 + 2 \times 7=32$ total for $n=3$. However, brute force would give $2(3!)$ multiplies and $3!-1$ additions which will be $17$. For $n=4$, your count gives is $4 \times 14 + 3 \times 15=101$ while brute force would give $3(4!)+4!-1=95$. The gap reduces but still was just wondering!
v s
CC BY-SA 3.0
2011-11-09T19:05:48.490Z
You can check my reasoning. I'm pretty sure I did it right, but of course it's possible I made a mistake. I would not find it too surprising if either of these algorithms were less efficient than brute force for very small input sizes. After all, as a simpler example, $n! < 2^{n}$ when $n < 4$.
Joshua Grochow
CC BY-SA 4.0
2021-12-20T03:30:00.717Z
Wikipedia claims O(2^(n-1)*n^2) and O(2^(n-1)*n) respectively for these.  So you are suggesting that the formula on the "Computing the Permanent" page is off by a factor of 2?
Gregory Morse
CC BY-SA 4.0
2021-12-21T09:51:39.510Z
@GregoryMorse: big-Oh notation hides any constant factor by definition, so what it says on Wikipedia is consistent with what I wrote. I also spelled out all my calculations so readers can check for themselves. If you find an error in my calculation please do let me know.
Joshua Grochow
CC BY-SA 4.0
2021-12-21T20:38:57.487Z
@JoshuaGrochow no your precise estimations are wrong and wikipedia is right.  For every set S is a subset equal of [n] can be partitioned into 2 partitions P0 and P1 such that they can be ordered so S0 in P0, S1 in P1, |S0|+|S1|=n.  Therefore the worst case is this average which results in halving so there are actually only 2^(n-1) sums. There is an error and you should be quite a bit less confident in contradicting a source that although can have mistake, is far more authoritative than yourself.  Especially since you certainly made a mistake in your calculations based on this simple argument.
Gregory Morse
CC BY-SA 4.0
2021-12-21T20:49:32.740Z
@JoshuaGrochow you obviously have no understanding of the practical uses of big O notation as despite that the strict mathematical definition requires a positive constant, a notation which requires a constant less than one would serve no purpose.  So by convention constants are always greater than one, and putting additional constraints in a big O formula is done to indicate exactness.  Though apparently you've not spent a lot of time thinking about this topic.
Gregory Morse
CC BY-SA 4.0
2021-12-22T23:48:08.403Z
@GregoryMorse: I looked into it since I didn't understand your explanation. Nijenhuis & Wilf explains it in detail on p. 222-3 (formula 24b on p. 223); this is what is ref'd on Wikipedia. In contrast, I was analyzing the original Ryser formula (p. 27 of Ryser's book) w/o the trick from N&W, and then Ryser+Gray (still w/o N&W). I believe this explains the discrepancy but if you still think there is an error please let me know. Your second comment was insulting and inappropriate - please see https://cstheory.stackexchange.com/conduct.
Joshua Grochow
CC BY-SA 4.0
2021-12-23T12:09:38.690Z
@JoshuaGrochow I apologize if you found my comment insulting.  Yes this trick is the one being referred to.  Interestingly if requiring exact integer arithmetic, then you end up having to multiply the inner equations all by 2 and dividing by 2^(n-1) at the end, giving a formula more or less similar to the Glynn variant but probably with a very slightly worse constant in terms of additions.
Gregory Morse
CC BY-SA 4.0
2021-12-23T12:20:07.293Z
@JoshuaGrochow In fact by multiplying the inner sums by 2 actually leads ultimately to basically an exact derivation of the Glynn formula, which means Muir algebra is not necessary to derive that variant.  This form may be better however, as Glynn uses {-1,1} for the deltas instead of {0,1} which is more natural in set-phrasing.
Gregory Morse
CC BY-SA 3.0
2011-11-09T03:11:05.230Z
2011-11-09T03:11:05.230Z
Joshua Grochow
<p>What is the exact number of multiplication operations and addition operations needed to calculate the permanent in <a href="http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula">Ryser's formula</a> (both original and the Gray coded version)?</p>

<p>I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a <a href="http://ww.scottaaronson.com/talks/wildidea.ppt">calculation</a> for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.</p>

<p>I am also looking for counts for other calculations/formulas of Permanent.</p>

CC BY-SA 3.0
2011-11-08T17:42:18.580Z
It would be useful to add a link to the referred formula (or even mention it inline)
Suresh Venkat
CC BY-SA 3.0
2011-11-08T22:11:56.713Z
A good upperbound seems to be stated in the Wikipedia article so I am confused about the motivation for this question.
Kaveh
CC BY-SA 3.0
2011-11-08T23:56:12.607Z
It's possible the key word here is "exact" i.e without O() ?
Suresh Venkat
CC BY-SA 3.0
2011-11-09T00:33:38.437Z
@SureshVenkat Yes. Precisely. I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for 4x4 determinant where he uses Gaussian elimination. http://www.scottaaronson.com/talks/wildidea.ppt

He mentions estimating the precise gap between permanent and determinant calculation for 4x4 is already a notorious open problem.
v s
CC BY-SA 3.0
2011-11-09T00:34:27.547Z
Also there are some other formulas. I was curious if someone has made a study on their exact complexity.
v s
CC BY-SA 3.0
2011-11-09T00:34:44.237Z
@Kaveh I am not looking for asymptotic results.
v s
CC BY-SA 3.0
2011-11-09T00:49:42.520Z
@vs: thanks for the explanation. :) By the way, it might be better to include what you wrote in the comment about inside the post so other would know why you are interested in the problem without a need to read comments.
Kaveh
CC BY-SA 3.0
2011-11-09T13:01:47.153Z
@Kaveh I have updated the question.
v s
<ds.algorithms><co.combinatorics><permanent>
Exact arithmetic complexity of Ryser's formula for computing permanent
v s
# Exact arithmetic complexity of Ryser's formula for computing permanent

(Asked by: username_0 on 2011-11-08)

What is the exact number of multiplication operations and addition operations needed to calculate the permanent in [Ryser's formula](http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula) (both original and the Gray coded version)?

I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a [calculation](http://ww.scottaaronson.com/talks/wildidea.ppt) for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.

I am also looking for counts for other calculations/formulas of Permanent.

**Tags:** ds.algorithms, co.combinatorics, permanent

> **Comments:**
> **username_1**: It would be useful to add a link to the referred formula (or even mention it inline)  
> **username_2**: A good upperbound seems to be stated in the Wikipedia article so I am confused about the motivation for this question.  
> **username_1**: It's possible the key word here is "exact" i.e without O() ?  
> **username_0**: @SureshVenkat Yes. Precisely. I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for 4x4 determinant where he uses Gaussian elimination. http://www.scottaaronson.com/talks/wildidea.ppt  He mentions estimating the precise gap between permanent and determinant calculation for 4x4 is already a notorious open problem.  
> **username_0**: Also there are some other formulas. I was curious if someone has made a study on their exact complexity.  
> **username_0**: @username_2 I am not looking for asymptotic results.  
> **username_2**: @vs: thanks for the explanation. :) By the way, it might be better to include what you wrote in the comment about inside the post so other would know why you are interested in the problem without a need to read comments.  
> **username_0**: @username_2 I have updated the question.  

---

## 1 answers

### Answer by username_3 on 2011-11-09. Score: 7 | Accepted answer

Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.

Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.

Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.

Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum\_{j \in S} a\_{ij}$ which uses $|S|-1$ additions. $\sum\_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum\_{k=1}^{n} (k-1) \binom{n}{k} = \sum\_{k=1}^{n} k \binom{n}{k} - \sum\_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$.

Additions for Ryser+Gray: The Gray code version does not give you a smaller *formula*, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.

> **Comments:**
> **username_0**: Are you sure about Ryser + Gray count? It seems to give $3 \times 6 + 2 \times 7=32$ total for $n=3$. However, brute force would give $2(3!)$ multiplies and $3!-1$ additions which will be $17$. For $n=4$, your count gives is $4 \times 14 + 3 \times 15=101$ while brute force would give $3(4!)+4!-1=95$. The gap reduces but still was just wondering!  
> **username_3**: You can check my reasoning. I'm pretty sure I did it right, but of course it's possible I made a mistake. I would not find it too surprising if either of these algorithms were less efficient than brute force for very small input sizes. After all, as a simpler example, $n! < 2^{n}$ when $n < 4$.  
> **username_4**: Wikipedia claims O(2^(n-1)*n^2) and O(2^(n-1)*n) respectively for these.  So you are suggesting that the formula on the "Computing the Permanent" page is off by a factor of 2?  
> **username_3**: @GregoryMorse: big-Oh notation hides any constant factor by definition, so what it says on Wikipedia is consistent with what I wrote. I also spelled out all my calculations so readers can check for themselves. If you find an error in my calculation please do let me know.  
> **username_4**: @JoshuaGrochow no your precise estimations are wrong and wikipedia is right.  For every set S is a subset equal of [n] can be partitioned into 2 partitions P0 and P1 such that they can be ordered so S0 in P0, S1 in P1, |S0|+|S1|=n.  Therefore the worst case is this average which results in halving so there are actually only 2^(n-1) sums. There is an error and you should be quite a bit less confident in contradicting a source that although can have mistake, is far more authoritative than yourself.  Especially since you certainly made a mistake in your calculations based on this simple argument.  
> **username_4**: @JoshuaGrochow you obviously have no understanding of the practical uses of big O notation as despite that the strict mathematical definition requires a positive constant, a notation which requires a constant less than one would serve no purpose.  So by convention constants are always greater than one, and putting additional constraints in a big O formula is done to indicate exactness.  Though apparently you've not spent a lot of time thinking about this topic.  
> **username_3**: @GregoryMorse: I looked into it since I didn't understand your explanation. Nijenhuis & Wilf explains it in detail on p. 222-3 (formula 24b on p. 223); this is what is ref'd on Wikipedia. In contrast, I was analyzing the original Ryser formula (p. 27 of Ryser's book) w/o the trick from N&W, and then Ryser+Gray (still w/o N&W). I believe this explains the discrepancy but if you still think there is an error please let me know. Your second comment was insulting and inappropriate - please see https://cstheory.stackexchange.com/conduct.  
> **username_4**: @JoshuaGrochow I apologize if you found my comment insulting.  Yes this trick is the one being referred to.  Interestingly if requiring exact integer arithmetic, then you end up having to multiply the inner equations all by 2 and dividing by 2^(n-1) at the end, giving a formula more or less similar to the Glynn variant but probably with a very slightly worse constant in terms of additions.  
> **username_4**: @JoshuaGrochow In fact by multiplying the inner sums by 2 actually leads ultimately to basically an exact derivation of the Glynn formula, which means Muir algebra is not necessary to derive that variant.  This form may be better however, as Glynn uses {-1,1} for the deltas instead of {0,1} which is more natural in set-phrasing.  

---

