| 1 |
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Combinatória</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot"><link rel="home" href="index.html" title="Manual do Genius"><link rel="up" href="ch11.html" title="Chapter 11. List of GEL functions"><link rel="prev" href="ch11s09.html" title="Álgebra linear"><link rel="next" href="ch11s11.html" title="Cálculo"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Combinatória</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s09.html">Prev</a> </td><th width="60%" align="center">Chapter 11. List of GEL functions</th><td width="20%" align="right"> <a accesskey="n" href="ch11s11.html">Next</a></td></tr></table><hr></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="genius-gel-function-list-combinatorics"></a>Combinatória</h2></div></div></div><div class="variablelist"><dl class="variablelist"><dt><span lang="en" class="term"><a name="gel-function-Catalan"></a>Catalan</span></dt><dd><pre lang="en" class="synopsis">Catalan (n)</pre><p lang="en">Get <code class="varname">n</code>th Catalan number.</p><p lang="en"> |
| 2 |
See |
| 3 |
<a class="ulink" href="http://planetmath.org/CatalanNumbers" target="_top">Planetmath</a> for more information. |
| 4 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Combinations"></a>Combinations</span></dt><dd><pre lang="en" class="synopsis">Combinations (k,n)</pre><p lang="en">Get all combinations of k numbers from 1 to n as a vector of vectors. |
| 5 |
(See also <a class="link" href="ch11s10.html#gel-function-NextCombination">NextCombination</a>) |
| 6 |
</p><p lang="en"> |
| 7 |
See |
| 8 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Combination" target="_top">Wikipedia</a> for more information. |
| 9 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-DoubleFactorial"></a>DoubleFactorial</span></dt><dd><pre lang="en" class="synopsis">DoubleFactorial (n)</pre><p lang="en">Double factorial: <strong class="userinput"><code>n(n-2)(n-4)...</code></strong></p><p lang="en"> |
| 10 |
See |
| 11 |
<a class="ulink" href="http://planetmath.org/DoubleFactorial" target="_top">Planetmath</a> for more information. |
| 12 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Factorial"></a>Factorial</span></dt><dd><pre lang="en" class="synopsis">Factorial (n)</pre><p lang="en">Factorial: <strong class="userinput"><code>n(n-1)(n-2)...</code></strong></p><p lang="en"> |
| 13 |
See |
| 14 |
<a class="ulink" href="http://planetmath.org/Factorial" target="_top">Planetmath</a> for more information. |
| 15 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-FallingFactorial"></a>FallingFactorial</span></dt><dd><pre lang="en" class="synopsis">FallingFactorial (n,k)</pre><p lang="en">Falling factorial: <strong class="userinput"><code>(n)_k = n(n-1)...(n-(k-1))</code></strong></p><p lang="en"> |
| 16 |
See |
| 17 |
<a class="ulink" href="http://planetmath.org/FallingFactorial" target="_top">Planetmath</a> for more information. |
| 18 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Fibonacci"></a>Fibonacci</span></dt><dd><pre lang="en" class="synopsis">Fibonacci (x)</pre><p lang="en">Aliases: <code class="function">fib</code></p><p lang="en"> |
| 19 |
Calculate <code class="varname">n</code>th Fibonacci number. That |
| 20 |
is the number defined recursively by |
| 21 |
<strong class="userinput"><code>Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)</code></strong> |
| 22 |
and |
| 23 |
<strong class="userinput"><code>Fibonacci(1) = Fibonacci(2) = 1</code></strong>. |
| 24 |
</p><p lang="en"> |
| 25 |
See |
| 26 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_top">Wikipedia</a> or |
| 27 |
<a class="ulink" href="http://planetmath.org/FibonacciSequence" target="_top">Planetmath</a> or |
| 28 |
<a class="ulink" href="http://mathworld.wolfram.com/FibonacciNumber.html" target="_top">Mathworld</a> for more information. |
| 29 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-FrobeniusNumber"></a>FrobeniusNumber</span></dt><dd><pre lang="en" class="synopsis">FrobeniusNumber (v,arg...)</pre><p lang="en"> |
| 30 |
Calculate the Frobenius number. That is calculate largest |
| 31 |
number that cannot be given as a non-negative integer linear |
| 32 |
combination of a given vector of non-negative integers. |
| 33 |
The vector can be given as separate numbers or a single vector. |
| 34 |
All the numbers given should have GCD of 1. |
| 35 |
</p><p lang="en"> |
| 36 |
See |
| 37 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Coin_problem" target="_top">Wikipedia</a> or |
| 38 |
<a class="ulink" href="http://mathworld.wolfram.com/FrobeniusNumber.html" target="_top">Mathworld</a> for more information. |
| 39 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-GaloisMatrix"></a>GaloisMatrix</span></dt><dd><pre lang="en" class="synopsis">GaloisMatrix (combining_rule)</pre><p lang="en">Galois matrix given a linear combining rule (a_1*x_1+...+a_n*x_n=x_(n+1)).</p></dd><dt><span lang="en" class="term"><a name="gel-function-GreedyAlgorithm"></a>GreedyAlgorithm</span></dt><dd><pre lang="en" class="synopsis">GreedyAlgorithm (n,v)</pre><p lang="en"> |
| 40 |
Find the vector <code class="varname">c</code> of non-negative integers |
| 41 |
such that taking the dot product with <code class="varname">v</code> is |
| 42 |
equal to n. If not possible returns <code class="constant">null</code>. <code class="varname">v</code> |
| 43 |
should be given sorted in increasing order and should consist |
| 44 |
of non-negative integers. |
| 45 |
</p><p lang="en"> |
| 46 |
See |
| 47 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Greedy_algorithm" target="_top">Wikipedia</a> or |
| 48 |
<a class="ulink" href="http://mathworld.wolfram.com/GreedyAlgorithm.html" target="_top">Mathworld</a> for more information. |
| 49 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-HarmonicNumber"></a>HarmonicNumber</span></dt><dd><pre lang="en" class="synopsis">HarmonicNumber (n,r)</pre><p lang="en">Aliases: <code class="function">HarmonicH</code></p><p lang="en">Harmonic Number, the <code class="varname">n</code>th harmonic number of order <code class="varname">r</code>. |
| 50 |
That is, it is the sum of <strong class="userinput"><code>1/k^r</code></strong> for <code class="varname">k</code> |
| 51 |
from 1 to n. Equivalent to <strong class="userinput"><code>sum k = 1 to n do 1/k^r</code></strong>.</p><p lang="en"> |
| 52 |
See |
| 53 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Harmonic_number" target="_top">Wikipedia</a> for more information. |
| 54 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Hofstadter"></a>Hofstadter</span></dt><dd><pre lang="en" class="synopsis">Hofstadter (n)</pre><p lang="en">Hofstadter's function q(n) defined by q(1)=1, q(2)=1, q(n)=q(n-q(n-1))+q(n-q(n-2)).</p><p lang="en"> |
| 55 |
See |
| 56 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Hofstadter_sequence" target="_top">Wikipedia</a> for more information. |
| 57 |
The sequence is <a class="ulink" href="https://oeis.org/A005185" target="_top">A005185 in OEIS</a>. |
| 58 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-LinearRecursiveSequence"></a>LinearRecursiveSequence</span></dt><dd><pre lang="en" class="synopsis">LinearRecursiveSequence (seed_values,combining_rule,n)</pre><p lang="en">Compute linear recursive sequence using Galois stepping.</p></dd><dt><span lang="en" class="term"><a name="gel-function-Multinomial"></a>Multinomial</span></dt><dd><pre lang="en" class="synopsis">Multinomial (v,arg...)</pre><p lang="en">Calculate multinomial coefficients. Takes a vector of |
| 59 |
<code class="varname">k</code> |
| 60 |
non-negative integers and computes the multinomial coefficient. |
| 61 |
This corresponds to the coefficient in the homogeneous polynomial |
| 62 |
in <code class="varname">k</code> variables with the corresponding powers. |
| 63 |
</p><p lang="en"> |
| 64 |
The formula for <strong class="userinput"><code>Multinomial(a,b,c)</code></strong> |
| 65 |
can be written as: |
| 66 |
</p><pre lang="en" class="programlisting">(a+b+c)! / (a!b!c!) |
| 67 |
</pre><p lang="en"> |
| 68 |
In other words, if we would have only two elements, then |
| 69 |
<strong class="userinput"><code>Multinomial(a,b)</code></strong> is the same thing as |
| 70 |
<strong class="userinput"><code>Binomial(a+b,a)</code></strong> or |
| 71 |
<strong class="userinput"><code>Binomial(a+b,b)</code></strong>. |
| 72 |
</p><p lang="en"> |
| 73 |
See |
| 74 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Multinomial_theorem" target="_top">Wikipedia</a>, |
| 75 |
<a class="ulink" href="http://planetmath.org/MultinomialTheorem" target="_top">Planetmath</a>, or |
| 76 |
<a class="ulink" href="http://mathworld.wolfram.com/MultinomialCoefficient.html" target="_top">Mathworld</a> for more information. |
| 77 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-NextCombination"></a>NextCombination</span></dt><dd><pre lang="en" class="synopsis">NextCombination (v,n)</pre><p lang="en">Get combination that would come after v in call to |
| 78 |
combinations, first combination should be <strong class="userinput"><code>[1:k]</code></strong>. This |
| 79 |
function is useful if you have many combinations to go through and you don't |
| 80 |
want to waste memory to store them all. |
| 81 |
</p><p lang="en"> |
| 82 |
For example with Combinations you would normally write a loop like: |
| 83 |
</p><pre lang="en" class="screen"><strong class="userinput"><code>for n in Combinations (4,6) do ( |
| 84 |
SomeFunction (n) |
| 85 |
);</code></strong> |
| 86 |
</pre><p lang="en"> |
| 87 |
But with NextCombination you would write something like: |
| 88 |
</p><pre lang="en" class="screen"><strong class="userinput"><code>n:=[1:4]; |
| 89 |
do ( |
| 90 |
SomeFunction (n) |
| 91 |
) while not IsNull(n:=NextCombination(n,6));</code></strong> |
| 92 |
</pre><p lang="en"> |
| 93 |
See also <a class="link" href="ch11s10.html#gel-function-Combinations">Combinations</a>. |
| 94 |
</p><p lang="en"> |
| 95 |
See |
| 96 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Combination" target="_top">Wikipedia</a> for more information. |
| 97 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Pascal"></a>Pascal</span></dt><dd><pre lang="en" class="synopsis">Pascal (i)</pre><p lang="en">Get the Pascal's triangle as a matrix. This will return |
| 98 |
an <code class="varname">i</code>+1 by <code class="varname">i</code>+1 lower diagonal |
| 99 |
matrix that is the Pascal's triangle after <code class="varname">i</code> |
| 100 |
iterations.</p><p lang="en"> |
| 101 |
See |
| 102 |
<a class="ulink" href="http://planetmath.org/PascalsTriangle" target="_top">Planetmath</a> for more information. |
| 103 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Permutations"></a>Permutations</span></dt><dd><pre lang="en" class="synopsis">Permutations (k,n)</pre><p lang="en">Get all permutations of <code class="varname">k</code> numbers from 1 to <code class="varname">n</code> as a vector of vectors.</p><p lang="en"> |
| 104 |
See |
| 105 |
<a class="ulink" href="http://mathworld.wolfram.com/Permutation.html" target="_top">Mathworld</a> or |
| 106 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Permutation" target="_top">Wikipedia</a> for more information. |
| 107 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-RisingFactorial"></a>RisingFactorial</span></dt><dd><pre lang="en" class="synopsis">RisingFactorial (n,k)</pre><p lang="en">Aliases: <code class="function">Pochhammer</code></p><p lang="en">(Pochhammer) Rising factorial: (n)_k = n(n+1)...(n+(k-1)).</p><p lang="en"> |
| 108 |
See |
| 109 |
<a class="ulink" href="http://planetmath.org/RisingFactorial" target="_top">Planetmath</a> for more information. |
| 110 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-StirlingNumberFirst"></a>StirlingNumberFirst</span></dt><dd><pre lang="en" class="synopsis">StirlingNumberFirst (n,m)</pre><p lang="en">Aliases: <code class="function">StirlingS1</code></p><p lang="en">Stirling number of the first kind.</p><p lang="en"> |
| 111 |
See |
| 112 |
<a class="ulink" href="http://planetmath.org/StirlingNumbersOfTheFirstKind" target="_top">Planetmath</a> or |
| 113 |
<a class="ulink" href="http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html" target="_top">Mathworld</a> for more information. |
| 114 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-StirlingNumberSecond"></a>StirlingNumberSecond</span></dt><dd><pre lang="en" class="synopsis">StirlingNumberSecond (n,m)</pre><p lang="en">Aliases: <code class="function">StirlingS2</code></p><p lang="en">Stirling number of the second kind.</p><p lang="en"> |
| 115 |
See |
| 116 |
<a class="ulink" href="http://planetmath.org/StirlingNumbersSecondKind" target="_top">Planetmath</a> or |
| 117 |
<a class="ulink" href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html" target="_top">Mathworld</a> for more information. |
| 118 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-Subfactorial"></a>Subfactorial</span></dt><dd><pre lang="en" class="synopsis">Subfactorial (n)</pre><p lang="en">Subfactorial: n! times sum_{k=0}^n (-1)^k/k!.</p></dd><dt><span lang="en" class="term"><a name="gel-function-Triangular"></a>Triangular</span></dt><dd><pre lang="en" class="synopsis">Triangular (nth)</pre><p lang="en">Calculate the <code class="varname">n</code>th triangular number.</p><p lang="en"> |
| 119 |
See |
| 120 |
<a class="ulink" href="http://planetmath.org/TriangularNumbers" target="_top">Planetmath</a> for more information. |
| 121 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-nCr"></a>nCr</span></dt><dd><pre lang="en" class="synopsis">nCr (n,r)</pre><p lang="en">Aliases: <code class="function">Binomial</code></p><p lang="en">Calculate combinations, that is, the binomial coefficient. |
| 122 |
<code class="varname">n</code> can be any real number.</p><p lang="en"> |
| 123 |
See |
| 124 |
<a class="ulink" href="http://planetmath.org/Choose" target="_top">Planetmath</a> for more information. |
| 125 |
</p></dd><dt><span lang="en" class="term"><a name="gel-function-nPr"></a>nPr</span></dt><dd><pre lang="en" class="synopsis">nPr (n,r)</pre><p lang="en">Calculate the number of permutations of size |
| 126 |
<code class="varname">r</code> of numbers from 1 to <code class="varname">n</code>.</p><p lang="en"> |
| 127 |
See |
| 128 |
<a class="ulink" href="http://mathworld.wolfram.com/Permutation.html" target="_top">Mathworld</a> or |
| 129 |
<a class="ulink" href="https://en.wikipedia.org/wiki/Permutation" target="_top">Wikipedia</a> for more information. |
| 130 |
</p></dd></dl></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s09.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch11s11.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Álgebra linear </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Cálculo</td></tr></table></div></body></html> |