User:Richard Pinch/sandbox-CZ

Stirling numbers

In combinatorics, the Stirling numbers count certain arrangements of objects into a given number of structures. There are two kinds of Stirling number, depending on the nature of the structure being counted.

The Stirling number of the first kind S(n,k) counts the number of ways n labelled objects can be arranged into k cycles: cycles are regarded as equivalent, and counted only once, if they differ by a cyclic permutation, thus [ABC] = [BCA] = [CAB] but is counted as different from [CBA] = [BAC] = [ACB]. The order of the cycles in the list is irrelevant.

For example, 4 objects can be arranged into 2 cycles in eleven ways, so S(4,2) = 11:

• [ABC],[D]
• [ACB],[D]
• [ABD],[C]
• [ADB],[C]
• [ACD],[B]
• [ADC],[B]
• [BCD],[A]
• [BDC],[A]
• [AB],[CD]
• [AC],[BD]
• [AD],[BC]

The Stirling number of the second kind s(n,k) counts the number of ways n labelled objects can be arranged into k subsets: cycles are regarded as equivalent, and counted only once, if they have the same elements, thus {ABC} = {BCA} = {CAB} = {CBA} = {BAC} = {ACB}. The order of the subsets in the list is irrelevant.

For example, 4 objects can be arranged into 2 subsets in seven ways, so s(4,2) = 7:

• {ABC},{D}
• {ABD},{C}
• {ACD},{B}
• {BCD},{A}
• {AB},{CD}
• {AC},{BD}
• {AD},{BC}

References

• Template:Cite book

Tau function

In mathematics, Ramanujan's tau function is an arithmetic function which may defined in terms of the Delta form by the formal infinite product

\[q \prod_{n=1}^\infty \left(1-q^n\right)^{24} = \sum_n \tau(n) q^n .\,\]

Since Δ is a Hecke eigenform, the tau function is multiplicative, with formal Dirichlet series and Euler product

\[ \sum_n \tau(n) n^{-s} = \prod_p \left(1 - \tau(p) p^{-s} + p^{11-2s} \right)^{-1} .\,\]

Turan sieve

In mathematics, in the field of number theory, the Turán sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Pál Turán in 1934.

Description

In terms of sieve theory the Turán sieve is of combinatorial type: deriving from a rudimentary form of the inclusion-exclusion principle. The result gives an upper bound for the size of the sifted set.

Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let A_p denote the set of elements of A divisible by p and extend this to let A_d the intersection of the A_p for p dividing d, when d is a product of distinct primes from P. Further let A₁ denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

\[S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . \]

We assume that |A_d| may be estimated, when d is a prime p by

\[ \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p \]

and when d is a product of two distinct primes d = p q by

\[ \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q} \]

where X   =   |A| and f is a function with the property that 0 ≤ f(d) ≤ 1. Put

\[ U(z) = \sum_{p \mid P(z)} f(p) . \]

Then

\[ S(A,P,z) \le \frac{X}{U(z)} + \frac{2}{U(z)} \sum_{p \mid P(z)} \left\vert R_p \right\vert + \frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert . \]

Applications

• The Hardy–Ramanujan theorem that the normal order of ω(n), the number of distinct prime factors of a number n, is log(log(n));
• Almost all integer polynomials (taken in order of height) are irreducible.

References

• Template:Cite book

Tutte matrix

In graph theory, the Tutte matrix \(A\) of a graph G = (V,E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.

If the set of vertices V has 2n elements then the Tutte matrix is a 2n × 2n matrix A with entries

\[A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\ -x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\ 0\;\;\;\;\mbox{otherwise} \end{cases}\]

where the x_ij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables x_ij, i<j ): this coincides with the square of the pfaffian of the matrix A and is non-zero (as a polynomial) if and only if a perfect matching exists. (It should be noted that this is not the Tutte polynomial of G.)

The Tutte matrix is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References

• Template:Cite book
• Template:Cite book
• Template:Cite journal

Weierstrass preparation theorem

In algebra, the Weierstrass preparation theorem describes a canonical form for formal power series over a complete local ring.

Let O be a complete local ring and f a formal power series in O''X''. Then f can be written uniquely in the form

\[f = (X^n + b_{n-1}X^{n-1} + \cdots + b_0) u(x) , \,\]

where the b_i are in the maximal ideal m of O and u is a unit of O''X''.

The integer n defined by the theorem is the Weierstrass degree of f.

References

• Template:Cite book

Zipf distribution

In probability theory and statistics, the Zipf distribution and zeta distribution refer to a class of discrete probability distributions. They have been used to model the distribution of words in words in a text , of text strings and keys in databases, and of the sizes of businesses and towns.

The Zipf distribution with parameter n assigns probability proportional to 1/r to an integer r ≤ n and zero otherwise, with normalization factor H_n, the n-th harmonic number.

A Zipf-like distribution with parameters n and s assigns probability proportional to 1/r^s to an integer r ≤ n and zero otherwise, with normalization factor \(\sum_{r=1}^n 1/r^s\).

The zeta distribution with parameter s assigns probability proportional to 1/r^s to all integers r with normalization factor given by the Riemann zeta function 1/ζ(s).

References

• Template:Cite book