inversion numbers

(0.001 seconds)

1—10 of 45 matching pages

2: 27.5 Inversion Formulas

§27.5 Inversion Formulas

… ►

27.5.2

\sum_{d\mathbin{|}n}\mu\left(d\right)=\left\lfloor\frac{1}{n}\right\rfloor,

ⓘ

Symbols:: $\mu\left(\NVar{n}\right)$ : Möbius function, $\left\lfloor\NVar{x}\right\rfloor$ : floor of $x$ , $d$ : positive integer and $n$ : positive integer
A&S Ref:: 24.3.1 II.B (in slightly different form)
Referenced by:: §27.5
Permalink:: http://dlmf.nist.gov/27.5.E2
Encodings:: pMML, png, TeX
See also:: Annotations for §27.5 and Ch.27

… ►Special cases of Möbius inversion pairs are: … ►Other types of Möbius inversion formulas include: … ►

3: 26.16 Multiset Permutations

… ►The definitions of inversion number and major index can be extended to permutations of a multiset such as

351322453154\in\mathfrak{S}_{\{1^{2},2^{2},3^{3},4^{2},5^{3}\}}

. …

4: 26.13 Permutations: Cycle Notation

… ►

26.13.6

{\left(j,k\right)}={\left(k-1,k\right)}{\left(k-2,k-1\right)}\cdots{\left(j+1,% j+2\right)}\*{\left(j,j+1\right)}{\left(j+1,j+2\right)}\cdots{\left(k-1,k% \right)}.

ⓘ

Symbols:: ${\left(\NVar{S}\right)}$ : cycle, $j$ : nonnegative integer and $k$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.13.E6
Encodings:: pMML, png, TeX
See also:: Annotations for §26.13 and Ch.26

… ►Given a permutation

\sigma\in\mathfrak{S}_{n}

, the inversion number of

\sigma

, denoted

\mathop{\mathrm{inv}}(\sigma)

, is the least number of adjacent transpositions required to represent

\sigma

. …

5: 26.15 Permutations: Matrix Notation

… ►The inversion number of

\sigma

is a sum of products of pairs of entries in the matrix representation of

\sigma

: …

6: 26.14 Permutations: Order Notation

… ►As an example,

35247816

is an element of

\mathfrak{S}_{8}.

The inversion number is the number of pairs of elements for which the larger element precedes the smaller: …

►Reed et al. (1990, pp. 458–470) describes a number-theoretic approach to Fourier analysis (called the arithmetic Fourier transform) that uses the Möbius inversion (27.5.7) to increase efficiency in computing coefficients of Fourier series. …

8: 22.20 Methods of Computation

… ►

22.20.4

\phi_{n-1}=\frac{1}{2}\left(\phi_{n}+\operatorname{arcsin}\left(\frac{c_{n}}{a% _{n}}\sin\phi_{n}\right)\right),

ⓘ

Symbols:: $\operatorname{arcsin}\NVar{z}$ : arcsine function, $\sin\NVar{z}$ : sine function, $a_{n}$ : numbers, $c_{n}$ : numbers, $n$ : positive and $\phi_{N}$ : approximations
Referenced by:: §22.20(ii)
Permalink:: http://dlmf.nist.gov/22.20.E4
Encodings:: pMML, png, TeX
See also:: Annotations for §22.20(ii), §22.20 and Ch.22

…

9: 24.19 Methods of Computation

… ►

•

Buhler et al. (1992) uses the expansion

24.19.3

\frac{t^{2}}{\cosh t-1}=-2\sum_{n=0}^{\infty}(2n-1)B_{2n}\frac{t^{2n}}{(2n)!},

ⓘ

Symbols:: $B_{\NVar{n}}$ : Bernoulli numbers, $!$ : factorial (as in $n!$ ), $\cosh\NVar{z}$ : hyperbolic cosine function, $n$ : integer and $t$ : real or complex
Referenced by:: §24.19(ii)
Permalink:: http://dlmf.nist.gov/24.19.E3
Encodings:: pMML, png, TeX
See also:: Annotations for §24.19(ii), §24.19 and Ch.24

and computes inverses modulo $p$ of the left-hand side. Multisectioning techniques are applied in implementations. See also Crandall (1996, pp. 116–120).

…

10: 27.6 Divisor Sums

§27.6 Divisor Sums

►Sums of number-theoretic functions extended over divisors are of special interest. … ►

27.6.2

\sum_{d\mathbin{|}n}\mu\left(d\right)f(d)=\prod_{p\mathbin{|}n}(1-f(p)),

n>1

ⓘ

Symbols:: $\mu\left(\NVar{n}\right)$ : Möbius function, $d$ : positive integer, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.6.E2
Encodings:: pMML, png, TeX
See also:: Annotations for §27.6 and Ch.27

►Generating functions, Euler products, and Möbius inversion are used to evaluate many sums extended over divisors. … ►

27.6.3

\sum_{d\mathbin{|}n}|\mu\left(d\right)|=2^{\nu\left(n\right)},

ⓘ

Symbols:: $\mu\left(\NVar{n}\right)$ : Möbius function, $\nu\left(\NVar{n}\right)$ : number of distinct primes dividing a number, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E3
Encodings:: pMML, png, TeX
See also:: Annotations for §27.6 and Ch.27

…