text:
# Inclusion–exclusion principle

(Redirected from Inclusion-exclusion principle)
The union of sets A and B

In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|,}$

where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.

The principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.}$

This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right-hand side of the formula. In this case, when removing the contributions of over-counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total.

Inclusion–exclusion illustrated by a Venn diagram for three sets

Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:

1. Include the cardinalities of the sets.
2. Exclude the cardinalities of the pairwise intersections.
3. Include the cardinalities of the triple-wise intersections.
4. Exclude the cardinalities of the quadruple-wise intersections.
5. Include the cardinalities of the quintuple-wise intersections.
6. Continue, until the cardinality of the n-tuple-wise intersection is included (if n is odd) or excluded (n even).

The name comes from the idea that the principle is based on over-generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718);[1] but it first appears in a paper of Daniel da Silva (1854),[2] and later in a paper by J. J. Sylvester (1883).[3] Sometimes the principle is referred to as the formula of Da Silva, or Sylvester due to these publications. The principle is an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula,[4] though Legendre already used a similar device in a sieve context in 1808.

As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory.

In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix.[5] This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As Gian-Carlo Rota put it:[6]

"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."

## Statement

In its general form, the principle of inclusion–exclusion states that for finite sets A1, ..., An, one has the identity

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{i=1}^{n}\left|A_{i}\right|\;-\sum _{1\leq i

(1)

Each term of the inclusion–exclusion formula gradually corrects the count until finally each portion of the Venn diagram is counted exactly once.

This can be compactly written as

${\displaystyle {\Biggl |}\bigcup _{i=1}^{n}A_{i}{\Biggr |}=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leq i_{1}<\cdots

or

${\displaystyle {\Biggl |}\bigcup _{i=1}^{n}A_{i}{\Biggr |}=\sum _{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}}(-1)^{|J|-1}{\Biggl |}\bigcap _{j\in J}A_{j}{\Biggr |}.}$

In words, to count the number of elements in a finite union of finite sets, first sum the cardinalities of the individual sets, then subtract the number of elements which appear in more than one set, then add back the number of elements which appear in more than two sets, then subtract the number of elements which appear in more than three sets, and so on. This process naturally ends since there can be no elements which appear in more than the number of sets in the union.

In applications it is common to see the principle expressed in its complementary form. That is, letting S be a finite universal set containing all of the Ai and letting ${\displaystyle {\bar {A_{i}}}}$ denote the complement of Ai in S, by De Morgan's laws we have

${\displaystyle {\biggl |}\bigcap _{i=1}^{n}{\bar {A_{i}}}{\biggr |}={\biggl |}S-\bigcup _{i=1}^{n}A_{i}{\biggr |}=\left|S\right|\;-\sum _{i=1}^{n}\left|A_{i}\right|\;+\sum _{1\leq i

As another variant of the statement, let P1, P2, ..., Pn be a list of properties that elements of a set S may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements of S which have none of the properties. Just let Ai be the subset of elements of S which have the property Pi and use the principle in its complementary form. This variant is due to J.J. Sylvester.[1]

## Examples

### Counting integers

As a simple example of the use of the principle of inclusion–exclusion, consider the question:[7]

How many integers in {1,...,100} are not divisible by 2, 3 or 5?

Let S = {1,...,100} and P1 the property that an integer is divisible by 2, P2 the property that an integer is divisible by 3 and P3 the property that an integer is divisible by 5. Letting Ai be the subset of S whose elements have property Pi we have by elementary counting: |A1| = 50, |A2| = 33, and |A3| = 20. There are 16 of these integers divisible by 6, 10 divisible by 10 and 6 divisible by 15. Finally, there are just 3 integers divisible by 30, so the number of integers not divisible by any of 2, 3 or 5 is given by:

100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

### Counting derangements

A more complex example is the following.

Suppose there is a deck of n cards numbered from 1 to n. Suppose a card numbered m is in the correct position if it is the mth card in the deck. How many ways, W, can the cards be shuffled with at least 1 card being in the correct position?

Begin by defining set Am, which is all of the orderings of cards with the mth card correct. Then the number of orders, W, with at least one card being in the correct position, m, is

${\displaystyle W={\biggl |}\bigcup _{m=1}^{n}A_{m}{\biggr |}.}$

Apply the principle of inclusion–exclusion,

${\displaystyle W=\sum _{m_{1}=1}^{n}\left|A_{m_{1}}\right|{}-\sum _{1\leq m_{1}

Each value ${\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}}$ represents the set of shuffles having at least p values m1, ..., mp in the correct position. Note that the number of shuffles with at least p values correct only depends on p, not on the particular values of ${\displaystyle m}$. For example, the number of shuffles having the 1st, 3rd, and 17th cards in the correct position is the same as the number of shuffles having the 2nd, 5th, and 13th cards in the correct positions. It only matters that of the n cards, 3 were chosen to be in the correct position. Thus there are ${\displaystyle {n \choose p}}$ equal terms in the pth summation (see combination).

${\displaystyle W={n \choose 1}\left|A_{1}\right|-{n \choose 2}\left|A_{1}\cap A_{2}\right|+{n \choose 3}\left|A_{1}\cap A_{2}\cap A_{3}\right|-\cdots +(-1)^{p-1}{n \choose p}\left|A_{1}\cap \cdots \cap A_{p}\right|\cdots .}$

${\displaystyle \left|A_{1}\cap \cdots \cap A_{p}\right|}$ is the number of orderings having p elements in the correct position, which is equal to the number of ways of ordering the remaining n − p elements, or (n − p)!. Thus we finally get:

${\displaystyle W={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{p-1}{n \choose p}(n-p)!\cdots W=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!.}$

Noting that ${\displaystyle {n \choose p}={\frac {n!}{p!(n-p)!}}}$, this reduces to

${\displaystyle W=\sum _{p=1}^{n}(-1)^{p-1}\,{\frac {n!}{p!}}.}$

A permutation where no card is in the correct position is called a derangement. Taking n! to be the total number of permutations, the probability Q that a random shuffle produces a derangement is given by

${\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},}$

a truncation to n+1 terms of the Taylor expansion of e−1. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately 1/e or 37%.

## A special case

The situation that appears in the derangement example above occurs often enough to merit special attention.[8] Namely, when the size of the intersection sets appearing in the formulas for the principle of inclusion–exclusion depend only on the number of sets in the intersections and not on which sets appear. More formally, if the intersection

${\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}}$

has the same cardinality, say αk = |AJ|, for every k-element subset J of {1, ..., n}, then

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}$

Or, in the complementary form, where the universal set S has cardinality α0,

${\displaystyle {\biggl |}S\setminus \bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.}$

## A generalization

Given a family (repeats allowed) of subsets A1, A2, ..., An of a universal set S, the principle of inclusion–exclusion calculates the number of elements of S in none of these subsets. A generalization of this concept would calculate the number of elements of S which appear in exactly some fixed m of these sets.

Let N = [n] = {1,2,...,n}. If we define ${\displaystyle A_{\emptyset }=S}$, then the principle of inclusion–exclusion can be written as, using the notation of the previous section; the number of elements of S contained in none of the Ai is:

${\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.}$

If I is a fixed subset of the index set N, then the number of elements which belong to Ai for all i in I and for no other values is:[9]

${\displaystyle \sum _{I\subseteq J}(-1)^{|J|-|I|}|A_{J}|.}$

Define the sets

${\displaystyle B_{k}=A_{I\cup \{k\}}}$ for k in ${\displaystyle N\setminus I}$.

We seek the number of elements in none of the Bk which, by the principle of inclusion–exclusion (with ${\displaystyle B_{\emptyset }=A_{I}}$), is

${\displaystyle \sum _{K\subseteq N\setminus I}(-1)^{|K|}|B_{K}|.}$

The correspondence KJ = IK between subsets of N \ I and subsets of N containing I is a bijection and if J and K correspond under this map then BK = AJ, showing that the result is valid.

## In probability

In probability, for events A1, ..., An in a probability space ${\displaystyle \scriptstyle (\Omega ,{\mathcal {F}},\mathbb {P} )}$, the inclusion–exclusion principle becomes for n = 2

${\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}$

for n = 3

${\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})\qquad {}-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})\qquad {}+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}$

and in general

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}{}=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i

which can be written in closed form as

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}\mathbb {P} (A_{I})\right),}$

where the last sum runs over all subsets I of the indices 1, ..., n which contain exactly k elements, and

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

denotes the intersection of all those Ai with index in I.

According to the Bonferroni inequalities, the sum of the first terms in the formula is alternately an upper bound and a lower bound for the LHS. This can be used in cases where the full formula is too cumbersome.

For a general measure space (S,Σ,μ) and measurable subsets A1, ..., An of finite measure, the above identities also hold when the probability measure ${\displaystyle \mathbb {P} }$ is replaced by the measure μ.

### Special case

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection AI only depends on the cardinality of I, meaning that for every k in {1, ..., n} there is an ak such that

${\displaystyle a_{k}=\mathbb {P} (A_{I})\quad {\text{for every}}\quad I\subset \{1,\ldots ,n\}\quad {\text{with}}\quad |I|=k,}$

then the above formula simplifies to

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}$

due to the combinatorial interpretation of the binomial coefficient ${\displaystyle \scriptstyle {\binom {n}{k}}}$.

An analogous simplification is possible in the case of a general measure space (S,Σ,μ) and measurable subsets A1, ..., An of finite measure.

## Other forms

The principle is sometimes stated in the form[10] that says that if

${\displaystyle g(A)=\sum _{S\subseteq A}f(S)}$

then

${\displaystyle f(A)=\sum _{S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)\qquad (**)}$

The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (**).

Proof

Take ${\displaystyle {\underline {m}}=\{1,2,\ldots ,m\}}$, ${\displaystyle f({\underline {m}})=0}$, and

${\displaystyle f(S)={\bigg |}\bigcap _{i\in {\underline {m}}\backslash S}A_{i}{\bigg \backslash }\bigcup _{i\in S}A_{i}{\bigg |}\qquad {\text{and}}\qquad f(S)=\mathbb {P} {\bigg (}\bigcap _{i\in {\underline {m}}\backslash S}A_{i}{\bigg \backslash }\bigcup _{i\in S}A_{i}{\bigg )}}$

respectively for all sets ${\displaystyle S}$ with ${\displaystyle S\subsetneq {\underline {m}}}$. Then we obtain

${\displaystyle g(A)={\bigg |}\bigcap _{i\in {\underline {m}}\backslash A}A_{i}{\bigg |},~~g({\underline {m}})={\bigg |}\bigcup _{i\in {\underline {m}}}A_{i}{\bigg |}\qquad {\text{and}}\qquad g(A)=\mathbb {P} {\bigg (}\bigcap _{i\in {\underline {m}}\backslash A}A_{i}{\bigg )},~~g({\underline {m}})=\mathbb {P} {\bigg (}\bigcup _{i\in {\underline {m}}}A_{i}{\bigg )}}$

respectively for all sets ${\displaystyle A}$ with ${\displaystyle A\subsetneq {\underline {m}}}$. This is because elements ${\displaystyle a}$ of ${\displaystyle \cap _{i\in {\underline {m}}\backslash A}A_{i}}$ can be contained in other ${\displaystyle A_{i}}$'s (${\displaystyle A_{i}}$'s with ${\displaystyle i\in A}$) as well, and the ${\displaystyle \cap \backslash \!\!\cup \!{\text{-}}}$formula runs exactly through all possible extensions of the sets ${\displaystyle \{A_{i}\mid i\in {\underline {m}}\backslash A\}}$ with other ${\displaystyle A_{i}}$'s, counting ${\displaystyle a}$ only for the set that matches the membership behavior of ${\displaystyle a}$, if ${\displaystyle S}$ runs through all subsets of ${\displaystyle A}$ (as in the definition of ${\displaystyle g(A)}$).

Since ${\displaystyle f({\underline {m}})=0}$, we obtain from (**) with ${\displaystyle A={\underline {m}}}$ that

${\displaystyle \sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{\left|T\right|-1}g({\underline {m}}\backslash T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-\left|S\right|-1}g(S)=g({\underline {m}})}$

and by interchanging sides, the combinatorial and the probabilistic version of the inclusion–exclusion principle follow.

If one sees a number ${\displaystyle n}$ as a set of its prime factors, then (**) is a generalization of Möbius inversion formula for square-free natural numbers. Therefore, (**) is seen as the Möbius inversion formula for the incidence algebra of the partially ordered set of all subsets of A.

For a generalization of the full version of Möbius inversion formula, (**) must be generalized to multisets. For multisets instead of sets, (**) becomes

${\displaystyle f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)\qquad (***)}$

where ${\displaystyle A-S}$ is the multiset for which ${\displaystyle (A-S)\uplus S=A}$, and

• μ(S) = 1 if S is a set (i.e. a multiset without double elements) of even cardinality.
• μ(S) = −1 if S is a set (i.e. a multiset without double elements) of odd cardinality.
• μ(S) = 0 if S is a proper multiset (i.e. S has double elements).

Notice that ${\displaystyle \mu }$${\displaystyle (A-S)}$ is just the ${\displaystyle (-1)^{\left|A\right|-\left|S\right|}}$ of (**) in case ${\displaystyle A-S}$ is a set.

Proof of (***)

Substitute

${\displaystyle g(S)=\sum _{T\subseteq S}f(T)}$

on the right hand side of (***). Notice that ${\displaystyle f(A)}$ appears once on both sides of (***). So we must show that for all ${\displaystyle T}$ with ${\displaystyle T\subsetneq A}$, the terms ${\displaystyle f(T)}$ cancel out on the right hand side of (***). For that purpose, take a fixed ${\displaystyle T}$ such that ${\displaystyle T\subsetneq A}$ and take an arbitrary fixed ${\displaystyle a\in A}$ such that ${\displaystyle a\not \in T}$.

Notice that ${\displaystyle A-S}$ must be a set for each positive or negative appearance of ${\displaystyle f(T)}$ on the right hand side of (***) that is obtained by way of the multiset ${\displaystyle S}$ such that ${\displaystyle T\subseteq S\subseteq A}$. Now each appearance of ${\displaystyle f(T)}$ on the right hand side of (***) that is obtained by way of ${\displaystyle S}$ such that ${\displaystyle A-S}$ is a set that contains ${\displaystyle a}$ cancels out with the one that is obtained by way of the corresponding ${\displaystyle S}$ such that ${\displaystyle A-S}$ is a set that does not contain ${\displaystyle a}$. This gives the desired result.

## Applications

The inclusion–exclusion principle is widely used and only a few of its applications can be mentioned here.

### Counting derangements

Main article: Derangement

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting all derangements of a finite set. A derangement of a set A is a bijection from A into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of A is n, then the number of derangements is [n! / e] where [x] denotes the nearest integer to x; a detailed proof is available here and also see the examples section above.

The first occurrence of the problem of counting the number of derangements is in an early book on games of chance: Essai d'analyse sur les jeux de hazard by P. R. de Montmort (1678 – 1719) and was known as either "Montmort's problem" or by the name he gave it, "problème des rencontres."[11] The problem is also known as the hatcheck problem.

The number of derangements is also known as the subfactorial of n, written !n. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches 1/e as n grows.

### Counting intersections

The principle of inclusion–exclusion, combined with De Morgan's law, can be used to count the cardinality of the intersection of sets as well. Let ${\displaystyle \scriptstyle {\overline {A}}_{k}}$ represent the complement of Ak with respect to some universal set A such that ${\displaystyle \scriptstyle A_{k}\,\subseteq \,A}$ for each k. Then we have

${\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}}$

thereby turning the problem of finding an intersection into the problem of finding a union.

### Graph coloring

The inclusion exclusion principle forms the basis of algorithms for a number of NP-hard graph partitioning problems, such as graph coloring.[12]

A well known application of the principle is the construction of the chromatic polynomial of a graph.[13]

### Bipartite graph perfect matchings

The number of perfect matchings of a bipartite graph can be calculated using the principle.[14]

### Number of onto functions

Given finite sets A and B, how many surjective functions (onto functions) are there from A to B? Without any loss of generality we may take A = {1,2,...,k} and B = {1,2,...,n}, since only the cardinalities of the sets matter. By using S as the set of all functions from A to B, and defining, for each i in B, the property Pi as "the function misses the element i in B" (i is not in the image of the function), the principle of inclusion–exclusion gives the number of onto functions between A and B as:[15]

${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.}$

### Permutations with forbidden positions

A permutation of the set S = {1,2,...,n} where each element of S is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements of S) is called a permutation with forbidden positions. For example, with S = {1,2,3,4}, the permutations with the restriction that the element 1 can not be in positions 1 or 3, and the element 2 can not be in position 4 are: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 and 4321. By letting Ai be the set of positions that the element i is not allowed to be in, and the property Pi to be the property that a permutation puts element i into a position in Ai, the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions.[16]

In the given example, there are 12 = 2(3!) permutations with property P1, 6 = 3! permutations with property P2 and no permutations have properties P3 or P4 as there are no restrictions for these two elements. The number of permutations satisfying the restrictions is thus:

4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.

The final 4 in this computation is the number of permutations having both properties P1 and P2. There are no other non-zero contributions to the formula.

### Stirling numbers of the second kind

The Stirling numbers of the second kind, S(n,k) count the number of partitions of a set of n elements into k non-empty subsets (indistinguishable boxes). An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an n-set into k non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of the n-set into k (possibly empty) distinguishable boxes, A1, A2, ..., Ak, and the properties Pi meaning that the partition has box Ai empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by k! to remove the artificial ordering gives the Stirling number of the second kind:[17]

${\displaystyle S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.}$

### Rook polynomials

Main article: Rook polynomial

A rook polynomial is the generating function of the number of ways to place non-attacking rooks on a board B that looks like a subset of the squares of a checkerboard; that is, no two rooks may be in the same row or column. The board B is any subset of the squares of a rectangular board with n rows and m columns; we think of it as the squares in which one is allowed to put a rook. The coefficient, rk(B) of xk in the rook polynomial RB(x) is the number of ways k rooks, none of which attacks another, can be arranged in the squares of B. For any board B, there is a complementary board B' consisting of the squares of the rectangular board that are not in B. This complementary board also has a rook polynomial RB' (x) with coefficients rk(B').

It is sometimes convenient to be able to calculate the highest coefficient of a rook polynomial in terms of the coefficients of the rook polynomial of the complementary board. Without loss of generality we can assume that nm, so this coefficient is rn(B). The number of ways to place n non-attacking rooks on the complete n × m "checkerboard" (without regard as to whether the rooks are placed in the squares of the board B) is given by the falling factorial:

${\displaystyle (m)_{n}=m(m-1)(m-2)\cdots (m-n+1).}$

Letting Pi be the property that an assignment of n non-attacking rooks on the complete board has a rook in column i which is not in a square of the board B, then by the principle of inclusion–exclusion we have:[18]

${\displaystyle r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}\;r_{t}(B').}$

### Euler's phi function

Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ kn which have no common factor with n other than 1. The principle of inclusion–exclusion is used to obtain a formula for φ(n). Let S be the set {1,2,...,n} and define the property Pi to be that a number in S is divisible by the prime number pi, for 1 ≤ ir, where the prime factorization of

${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.}$

Then,[19]

${\displaystyle \phi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leq i

## Diluted inclusion–exclusion principle

In many cases where the principle could give an exact formula (in particular, counting prime numbers using the sieve of Eratosthenes), the formula arising doesn't offer useful content because the number of terms in it is excessive. If each term individually can be estimated accurately, the accumulation of errors may imply that the inclusion–exclusion formula isn't directly applicable. In number theory, this difficulty was addressed by Viggo Brun. After a slow start, his ideas were taken up by others, and a large variety of sieve methods developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula.

Let A1, ..., An be arbitrary sets and p1, ..., pn real numbers in the closed unit interval [0,1]. Then, for every even number k in {0, ..., n}, the indicator functions satisfy the inequality:[20]

${\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots

If k is odd, replace "≥" by "≤".

## Proof of main statement

Choose an element contained in the union of all sets and let ${\displaystyle A_{1},A_{2},\dots ,A_{t}}$ be the individual sets containing it. (Note that t > 0.) Since the element is counted precisely once by the left-hand side of equation (1), we need to show that it is counted precisely once by the right-hand side. On the right-hand side, the only non-zero contributions occur when all the subsets in a particular term contain the chosen element, that is, all the subsets are selected from ${\displaystyle A_{1},A_{2},\dots ,A_{t}}$. The contribution is one for each of these sets (plus or minus depending on the term) and therefore is just the (signed) number of these subsets used in the term. We then have:

${\displaystyle |\{A_{i}\mid 1\leq i\leq t\}|-|\{A_{i}\cap A_{j}\mid 1\leq i

By the binomial theorem,

${\displaystyle 0=(1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}}$.

Using the fact that ${\displaystyle {\binom {t}{0}}=1}$ and rearranging terms, we have

${\displaystyle 1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}},}$

and so, the chosen element is counted only once by the right-hand side of equation (1).

### Algebraic proof

An algebraic proof can be obtained using indicator functions (characteristic functions of subsets of a set). The indicator function of a subset S of a set X is a function

${\displaystyle \mathbf {1} _{S}\colon X\to \{0,1\}\,}$

defined as

${\displaystyle \mathbf {1} _{S}(x):={\begin{cases}1&{\text{if }}x\in S,\\0&{\text{if }}x\notin S.\end{cases}}}$

Writing the composition of two indicator functions as a product, we have that, if ${\displaystyle A}$ and ${\displaystyle B}$ are two subsets of ${\displaystyle X}$, then

${\displaystyle \mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.}$

Let A denote the union ${\textstyle \cup _{i=1}^{n}A_{i}}$ of the sets A1, ..., An. To prove the inclusion–exclusion principle in general, we first verify the identity

${\displaystyle 1_{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop |I|=k}1_{A_{I}}}$

(∗)

for indicator functions, where

${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}.}$

The following function is identically zero

${\displaystyle (1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,=\,0,}$

because: if x is not in A, then all factors are 0 − 0 = 0; and otherwise, if x does belong to some Am, then the corresponding mth factor is 1 − 1 = 0. By expanding the product on the left-hand side, equation (∗) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (∗) over all x in the union of A1, ..., An. To derive the version used in probability, take the expectation in (∗). In general, integrate the equation (∗) with respect to μ. Always use linearity in these derivations.

## Notes

1. ^ a b Roberts & Tesman 2009, pg. 405
2. ^ Mazur 2010, pg. 94
3. ^ van Lint & Wilson 1992, pg. 77
4. ^ van Lint & Wilson 1992, pg. 77
5. ^ Stanley 1986, pg. 64
6. ^ Rota, Gian-Carlo (1964), "On the foundations of combinatoial theory I. Theory of Möbius functions", Zeitschrift für Wahrscheinlichkeitstheorie, 2: 340–368
7. ^ Mazur 2010, pp. 83–4, 88
8. ^ Brualdi 2010, pp. 167–8
9. ^ Cameron 1994, pg. 78
10. ^ Graham, Grötschel & Lovász 1995, pg. 1049
11. ^ van Lint & Wilson 1992, pp. 77-8
12. ^ Björklund, Husfeldt & Koivisto 2009
13. ^ Gross 2008, pp. 211–13
14. ^ Gross 2008, pp. 208–10
15. ^ Mazur 2008, pp.84-5, 90
16. ^ Brualdi 2010, pp. 177–81
17. ^ Brualdi 2010, pp. 282–7
18. ^ Roberts & Tesman 2009, pp.419–20
19. ^ van Lint & Wilson 1992, pg. 73
20. ^ (Fernández, Fröhlich & Alan D. 1992, Proposition 12.6)


text:
# Embedding a cancellative monoid into another in such a way that a prescribed element becomes left-invertible

Let $\mathbb A = (A, +_A)$ be a cancellative, but possibly non-commutative, monoid with identity $0$, and fix an element $x \in A$. Does there always exist a cancellative monoid $\mathbb B = (B, +)$ such that $\mathbb A$ is a submonoid of $\mathbb B$ and $x$ is left-invertible invertible in $\mathbb B$ (see Benjamin Steinberg's comment below)?

It is known from a paper of A. I. Mal'cev [Math. Ann. 113 (1937), No. 1, 686-691] that there exist (finitely generated) cancellative monoids that do not embed into a group, but the question here is about an embeddability condition that looks very much weaker.

• Why do you say left invertible? In a cancellative monoid left invertible elements are right invertible. If yx =1 then xyx=x and so xy =1 by cancellation – Benjamin Steinberg Mar 13 '16 at 16:44
• To my shame, I hadn't thought of it. Let me edit and include your remark. – Salvo Tringali Mar 13 '16 at 16:46
• It seems to me the answer should be no. Take a fg cancellative monoid $M$ not embeddable in a group. Enumerate the elements and invert them one by one. Then the original monoid would embed in the unit group of the direct limit. – Benjamin Steinberg Mar 13 '16 at 16:49

format: plain


text:
# picking the best model

This is sort of homework so I'm not really looking for an answer, just pointers.

I have a dataset with 2,871 sample points from an aerial photograph in a GIS. Each random point was scored as being in forest (tree = 1) or not (tree = 0). Using a digital elevation model (DEM) that gave the height to the nearest meter (Elevation.m) one other variable was derived. The other variable was a factor variable describing if the sample point was more or less east facing (E.vs.W. = east) or west facing (E.vs.W. = west).

ex:

E.vs.W,Elevation.m,tree
west,7.896944379,1
west,6.897992018,1
west,-7.314651138,1
west,-10.88583519,1
west,128.6587367,1
west,102.8423517,1
west,205.0537347,1
west,169.6836871,1
west,201.2179048,1
west,210.6947441,1
...

I'm to "explore the variables and their interactions to predict the presence of a tree. Find the best model while showing how it compares to the other models using ΔAIC."

This is what I have:

dat <- read.csv("Data/treeData.csv")
str(dat)

mod1 <- lm(Elevation.m~tree, data=dat)
mod2 <- lm(Elevation.m~E.vs.W, data=dat)
AIC(mod1,mod2)

plot(Elevation.m~E.vs.W, data=dat)

I guess I'm not sure how to pick the "best model". Am I approaching this correctly?

• You need the homework or self study tag. May 1 '18 at 2:04
• There is know certain way to pick a best model unless you were to try every single one of them. Just pick a handful you have talked about in class and compare their error. Look at the independent variable coefficients to get at the "interactions" bit. I would include all variables in different types of models themselves rather than looking at combinations of variables in just one model (such as the linear model you have shown here).
– user136768
May 1 '18 at 2:07

I don't think you are approaching this correctly - shouldn't your outcome variable be the tree variable? After all, you need to predict the presence of a tree, not elevation!

If your outcome variable is tree, then you'll have to account for the fact that it is a binary variable (i.e., a variable which only takes values such as 0 and 1) and use binary logistic regression to model it as a function of elevation and facing. In other words, you should use the glm() function rather than the lm() function.

The models that you can fit will then look like:

mod1 <- glm(tree ~ Elevation,
data = dat)

mod2 <- glm(tree ~ E.vs.W,
data = dat)

mod3 <- glm(tree ~ Elevation + E.vs.W,


text:
# PDE and Analysis Seminar: Grzegorz Swiderski (Wroclaw)

Date:
Thu, 27/04/201713:00-14:00
Location:
Ross 70
Title: Asymptotics of Christoffel functions in an unbounded setting
Abstract:
Consider a measure $\mu$ supported on the real line with all moments finite.
Let $(p_n : n \geq 0)$ be the corresponding sequence of orthonormal
polynomials. This sequence satisfies the three-term recurrence relation
$a_{n-1} p_{n-1}(x) + b_n p_n(x) a_n p_{n+1}(x) = x p_n(x) \quad (n > 0)$
for some sequences $a$ and $b$.
One defines the $n$th Christoffel function by
$\lambda_n(x) = \left[ \sum_{k=0}^n p_k(x)^2 \right]^{-1}.$
In the talk, under some regularity hypotheses on $a$ and $b$, we show
exact asymptotics of the sequence $(\lambda_n(x) : n \geq 0)$ in the case
when $\textrm{supp}(\mu) = \mathbb{R}$.


text:
# Help Compiling Vectors using Iterations

So I have a nice code that runs properly, which I include below but, in my naiveté, I'm having issues iterating my procedure.

Simply put, I have a function of two real variables $f(x,y)$ and I want to manually parameterize part of its zero set. It has to be manually, because the cases I'm ultimately interested in have many complicated components, of which I only want one specific one.

So I input a point $P_{0}$ which I know on the zero set. I then produce a unit tangent vector to the zero set at $P_{0}$, pick a tiny step-size $h$, multiply this unit vector by $h$ and use a minimization procedure to find a nearby point $P_{1}$ on the curve. I would like to iterate this procedure to get two vectors of the same size: $\{0,h,2h,3h,\ldots \}$ and the corresponding $(x,y)$ values on the curve corresponding to that parameter value. Here is my code so far:

f[x_, y_] = (x^2 + y^2 - 4)*((x - 1)^2 + y^2 - 4);
Dell[a_, b_] = Grad[f[a, b], {a, b}];
V[a_, b_] = (1/Norm[Dell[a, b]])*{Dell[a, b][[2]], -Dell[a, b][[1]]};
P0 = {2, 0};
h = 0.05;
Dis[x_, y_] = Norm[P0 + h*V[P0[[1]], P0[[2]]] - {x, y}];
N[Minimize[{Dis[x, y], f[x, y] == 0}, {x, y}], 10][[2]]

That last line of the code successfully outputs a nearby point on the curve $P_{1}$ which I would now like to use as input to carry out this recipe again, and get the two lists/vectors described above. Can someone perhaps help me with this step? Much appreciated.

You can use NestList to apply your function multiple times, but we need to modify your function for that purpose.

As a first step, since we are not interested in the value of your function at the minimum, but only in the values of its arguments there, I am going to use NArgMin instead of your N@Minimize combination. We also need to redefine the Dis function to accept the value of the previous point as input.

The following uses your previous definitions for all functions and arguments, except Dis, which is redefined as shown below:

Clear[Dis]
Dis[p_] := Norm[p + h*V[Sequence @@ p] - {x, y}]

NestList[
NArgMin[{Dis[#], f[x, y] == 0}, {x, y}] &,
P0, 4
]

(* Out: {{2, 0}, {2.9975, 0.0999225}, {2.99938, 0.0499693}, {3., -0.0000150731}} *)


text:
Question for Moderators of Homework Section

1. Oct 3, 2005

hotvette

Would it be against the philosophy of this forum to post a brief tutorial on a given topic, in this specific case, elementary motion (e.g. free falling object, trajectories, straight line motion, block on an incline w/ and w/o friction)?

The emphasis of the tutorial would be on methodology (i.e. develoment and use of free body diagram to derive the basic equation of motion based on the FDB). The methodology is exactly the same for each of the above problems mentioned above.

In the brief time I've been participating in this great forum (i.e. lots of participation), I've noticed time and time again the same things:

- don't have a clue how to even begin
- I have an equation but I'm not sure how to use it or if it applies
- etc.

My thought is that a basic tutorial on the fundamentals might just by chance get at least some of the students going in the right direction on their own (of course, they'd need to read and try to understand it).

Anyway, it was just an idea I had. I'd be willing to write it if the moderators would be willing to comment, edit, reject altogether, etc. If this is a bad idea, just say so. I won't be offended. Just trying to help where I perceive a need.

2. Oct 3, 2005

Integral

Staff Emeritus
Absolutely not against any policy. Such things have been discussed but have not happened. Post your presentation, we can then all review it. If it comes up to muster, it will be stickied.

This is a great, thank you for the offer, I am looking forward to seeing it. I have noticed and appreciated your posts.

3. Oct 3, 2005

ZapperZ

Staff Emeritus
I don't think it is a bad idea at all. I've been guilty of promising to write such a thing, but never followed through.

You are more than welcome to write it (I'm being presumptious for speaking on behalf of the HW section moderators). However, don't be discouraged if a lot of these people don't read it. A lot of them have managed to ignore the Sticky's in various parts of the forum instructing them on where to post their homework questions and how to post their homework questions.

Zz.

4. Oct 3, 2005

hotvette

Thanks for your comments and encouragement. Gosh, I'm on the hook, now! I'll see what I can come up with. It may take a little time between work, kids, etc.

I realize that many may not read it, but I wouldn't hesitate to reply to a post by saying 'read this (link) first and try it before you ask for help' :rofl:

Doodling for the Tutorial:

The change in velocity (acceleration) with which an object moves
is directly proportional to the magnitude of the force applied to the
object and inversely proportional to the mass of the object.

Mathematically, this can be stated: $$\vec F = m \vec a$$
where F and a are vector quantities.

$$\Sigma F_x = m a_x \ \ or \ \ \Sigma F_x = m \ \frac {dv_x}{dt} \ \ or \ \ \Sigma F_x = m \ \frac{d^2x}{dt^2} \ \ or \ \ \Sigma F_x = m \ \ddot x$$

$$\Sigma F_y = m a_y \ \ or \ \ \Sigma F_y = m \ \frac {dv_y}{dt} \ \ or \ \ \Sigma F_y = m \ \frac{d^2y}{dt^2} \ \ or \ \ \Sigma F_y = m \ \ddot y$$

$$m \ g = m \ \frac{dv_y}{dt}$$
Separating the variables, dividing both sides by m, and
integrating we get:

$$\int g dt = \int dv_y \ \ \Longleftrightarrow \ \ gt \ + \ C_1 = v_y \ + \ C_2 \ \ \Longleftrightarrow \ \ v_y = gt \ + \ C_1 \ - \ C_2$$

$$v_y = g \ t + C_1 - C_2 \Longleftrightarrow g \ t + v_{y0}$$

$$dx/dt = v_x \Longleftrightarrow \int dx = \int v_x \ dt$$

$$v_y = g \ t \ + \ v_{y0} = dy/dt \ \ \Longleftrightarrow \ \ \int dy = \int (gt \ + \ v_{y0}) dt$$

$$y = \frac{1}{2} g t^2 \ + \ v_{y0}t \ + \ y_0$$

$$\Sigma F_y = m a_y: \ \ mg = ma_y \ \ or \ \ g = a_y$$

$$\Theta$$

$$\mu N$$

$$\Sigma F_x = m a_x: \ \ mg \sin(\theta) = ma_x \ \ or \ \ g \sin(\theta) = a_x$$

$$\frac{dv_x}{dt} = g \sin(\theta) \ \ \Longleftrightarrow \ \ v_x = g \sin(\theta) t + v_{x0}$$

Last edited: Oct 4, 2005
5. Oct 3, 2005

ZapperZ

Staff Emeritus
I'm copying this onto my hard drive, and after the 12 million'th time and you are now shouting "READ THE DAMN LINK, WHY DON'T YOU??!!", I'll post this to you as a reminder!

:) :)

Zz.

6. Oct 3, 2005

Moonbear

Staff Emeritus
I think that's what happened to the good intentions of all the others who have suggested the same thing. Seriously, if you're up for it, go for it!

:rofl: :rofl:

7. Oct 4, 2005

hotvette

Draft #1 for Moderator review and comment.

Actually, I just had a thought. Maybe 1 page on the Newton's 2nd law and the integraton thereof - a little more formal than what I have here. Then, 1 pagers after that looking at specific applications.

Last edited: Oct 4, 2005
8. Oct 4, 2005

Tom Mattson

Staff Emeritus
Hotvette, that is really nice! Thanks for doing it.

I've played with the idea of doing something like this, but never did it because of two very discouraging reasons. One, most students who post HW questions here do so because they either don't read their book or can't understand it, which would imply that the same students either won't read or can't understand any summary that I could write. And the second reason is that posted announcements are almost universally ignored by students posting HW questions. Just look at how many students post HW questions without making any attempt to solve the problem on their own, despite my notices that say, "Read this before posting." :grumpy:

Well, I don't mean to be too much of a downer, and this is certainly worth a try. The only thing about your attachment that I would comment on right now is that there is a blank "page 3" that can probably be cropped off, unless it is reserved for future additional material.

Last edited: Oct 4, 2005
9. Oct 4, 2005

Pyrrhus

Yes, the problem with most students in the homework section is that they don't understand the hints or whatnots, because they don't read their book. On the worst case, they have homework, and they want someone to do it for them. I've also notice some students are taken General Physics I, and they don't even know what is a vector! :surprised. It could be either their fault or the college's.

Someone might want to write a tutorial on vector algebra

10. Oct 4, 2005

honestrosewater

(Can we see it too? )

11. Oct 4, 2005

Moonbear

Staff Emeritus
Oh goody, my first chance to use my superpowers! (I didn't even realize it wasn't approved until I saw your note, I'm not used to this yet, heh heh. )

Nice job hotvette. I'm impressed by how quickly you jumped on the idea and ran with it! Fantastic!

12. Oct 4, 2005

hotvette

Draft # 2 for Moderator Review. Work in process - two more pages to come (incline plane, projectile)

Last edited: Oct 5, 2005
13. Oct 4, 2005

Ivan Seeking

Staff Emeritus
Very nice!

14. Oct 4, 2005

saltydog

Good for you Hotvette. The proof in the pudding is to obtain feed-back from students, others who tell you they had problems understanding this concept until they read your explanation.

15. Oct 5, 2005

hotvette

I tried to post draft #3 but it seems there is a 100k limit on file size. I have 6 pages that total 151k in a pdf. Splitting apart won't work - page 5 by itself is 110k in size! What to do?

Gee, I just noticed the homework helper symbol. I'm honored! Is this because of the # of posts I've had or did y'all bestow this upon me?

After some fooling around I managed to get it split into 2 files that are each < 100k. They need some cleaning up, but it's basically done. Appreciate any and all editorial comments. Also, can someone verify that the math is correct?

Fyi, my objective was to have no topic span more than one page to minimize loss of interest.

P.S. I was going to edit an earlier post of mine in this same thread to delete the doodles (equations), but I can't seem to edit it.

Last edited: Oct 5, 2005
16. Oct 5, 2005

Integral

Staff Emeritus
Very nice,
They open and are readable but I get an error when I open them. I am not sure if I can see all of them.
I would like to get this posted so we can get some feedback from the students.

17. Oct 5, 2005

Moonbear

Staff Emeritus
No problem opening them here. Very nicely done hotvette!

And you were awarded the medal by the PF staff for your efforts in homework help. Congrats and thanks!

18. Oct 5, 2005

Dr Transport

I'd like to see the files also, they would not open on my box.......same error as Integral

19. Oct 5, 2005

hotvette

Thanks everyone for your comments. You need Acrobat 6.0 to open them. It's free, so shouldn't be a problem to get it. That's how I was able to get the size down (by restricting it to 6.0 only).

Don't spend too much time on what I've posted. I just cleaned up the examples to make them absolutely identical in format. All I have to do is tweak the Epilog page and I'll post what I consider the final version. Just give me 30-60 minutes. Later.

20. Oct 5, 2005

hotvette

OK everyone, attached is what I consider the final version, unless anyone can suggest additions to the Epilog page (at the end).

P.S. Many thanks to the PF staff for the Homework Helper medal!

Attached Files:

File size:
88.1 KB
Views:
111
• Motion1a.pdf
File size:
79.7 KB
Views:
98
Last edited: Oct 5, 2005
21. Oct 6, 2005

Pyrrhus

I like the presentation of the work, i haven't read it yet, i'll do so when i get time, i'm pretty busy these days.

22. Oct 6, 2005

ZapperZ

Staff Emeritus
Do we post our comments here? If we are, then here's mine. :)

I've had time to look at the first one, but not the 2nd, so this is all I have for now. Most of these comments are "trivial", but for completeness sake and for clarity, I think they should be considered.

1. "The change in velocity (acceleration).... " should be, to be accurate, the time rate of change in velocity. It's a difference between $$\Delta(v)$$ and $$dv/dt$$.

2. In the example of using Newton's 2nd Law under the influence of gravity, we need to be a bit more explicit in explaining how we are able to write

$$mg = m \frac{dv_y}{dt}$$

This equation implicitly assumes that we have already established a coordinate system in which the direction of mg is in the positive direction. There is nothing to prevent someone from writing mg with a minus sign if that person defined the positive direction in the opposite way. It is only after the coordinate system is established can one write the differential equation of motion.

I think this is crucial because in many cases, students are stuck at the very beginning and don't know where to start or how to start. While to most of us, being able to write that equation is almost second nature, it really isn't to most students learning this. I still see many who don't quite understand why they should do it this way.

3. The same comment goes for the free fall example. While a diagram is there, I think it makes sense to be explicit in describing our thinking of how we came up with the differential equation. This is required right in the very beginning, not at the end after it is solved, because this is needed to be able to write the equation properly in the first place.

Zz.

23. Oct 6, 2005

Astronuc

Staff Emeritus
I believe this matter has been discussed in one form or another, e.g. in this thread -

Physics HW FAQ Discussion - https://www.physicsforums.com/showthread.php?t=71931

Perhaps this could be done in a type of Wikibook or like the Physics Blog that Greg put together. I think perhaps the editing should be restricted to Science Advisors, Homework helpers, as well as Super Mentors.

The issue then becomes - how to get new members to check such resources before posting a question. It appears sometimes that people do not read "Read this before posting" nor the "FAQ's" sections.

BTW - hotvette's work looks really good. Nice pdfs!

Last edited: Oct 6, 2005
24. Oct 6, 2005

saltydog

Got a good one for you Hotvette:

Check out "No Idea where to start" in the HW. Tell me what you see happens. Up to you.

25. Oct 6, 2005

Moonbear

Staff Emeritus
Zz, I see your point and understand the reason to change it, however, is there any other way to word it that would be correct? It took me a moment to process the wording there, so I can just imagine a struggling student just glazing over and getting completely stuck at that point. Something, perhaps, like the change in velocity over time or the change in velocity as time passes. I know it's important to convey it's not just that the velocity changes, but how that velocity is changing over a period of time.

I think this is important because it's one of those real fundamentals that the slightest difficulty with it sets the student up for recurring difficulty throughout, but if this concept "clicks" for them, then they are ready to grasp further material. I just remember being taught that stuff the first time with graphs and had no idea how the area under a curve of a graph had anything at all to do with anything in the real world. I understood that a car accelerates, but we weren't taught it that way, so the concepts quickly became mathematical abstractions rather than concrete understanding (i.e., we learned to plug numbers into equations rather than learn to understand why those equations represented something in the physical world).


text:
# Can this function be solved in CVX?

My objective function is \left\| x \right\|^3 + f(y), where x=[x_1; x_2], f(y) is a convex function.
I know \left\| x \right\|^3 is convex, but how can I write \left\| x \right\|^3 in CVX ?

square_pos(norm(x))

I didn’t get your point. As I know, square_pos(norm(x)) expresses \|x\|^2, however, my objective function is \|x\|^3.

You will benefit from reading http://cvxr.com/cvx/doc/funcref.html#new-functions .

help pow_pos

pow_pos Power of positive part.
pow_pos(X,P) = POS(X).^P = MAX(X,0).^P.
Both P and X must be real, and P must be greater than or equal to 1.

Disciplined convex programming information:
pow_pos(X,P) is convex and nondecreasing in X; so when used in CVX
expressions, X must be convex. P must be constant, real, and
greater than or equal to 1.

Thank you, this function works!


text:
# Ncert Solutions For Class 11 Chemistry Chapter 1 Some Basic

1 week ago byjus.com Show details

› Estimated Reading Time: 7 mins

4 days ago learncbse.in Show details

› Estimated Reading Time: 7 mins

1 day ago vedantu.com Show details

› Estimated Reading Time: 8 mins

1 week ago careers360.com Show details

In NCERT Solutions for Class 11 Chemistry chapter 1 Some Basic Concepts of Chemistry, we will discuss questions based on only such concepts and techniques. In this chapter, we deal with topics like the importance of chemistry, different states of matter, atomic and molecular mass, Dalton’s atomic theory, Avogadro Law, the law of conservation ...

2 weeks ago aglasem.com Show details

Aug 25, 2021  · This solution contains questions, answers, images, explanations of the complete chapter 1 titled Some Basic Concepts Of Chemistry of Chemistry taught in Class 11. If you are a student of Class 11 who is using NCERT Textbook to study Chemistry, then you must come across chapter 1 Some Basic Concepts Of Chemistry.

› Book: Chemistry Part I
› Class: 11
› Chapter Name: Some Basic Concepts Of Chemistry
› Subject: Chemistry

2 weeks ago cbsetuts.com Show details

5 days ago learninsta.com Show details

Aug 18, 2021  · Here we have given NCERT Solutions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry. Question 1. Calculate the molecular mass of the following : (i) H2O (ii) CO2 (iii) CH4. Answer: (i) Molecular mass of H 2 O : 2 × 1 + 1 × 16 = 18u. (ii) Molecular mass of CO 2 : 1 × 12 + 2× 16 = 44 u.

2 days ago myncert.com Show details

Jun 13, 2018  · NCERT Solutions Class 11 Chemistry Chapter 1 PDF. Free Download. Chemistry is the branch of science which mainly deals with the study of matter, compounds, elements, atoms, molecules, chemical symbols, reactions and lot more along with their properties, structures, and their transformation. Chemistry also plays an important role in our day to ...

Molecules

1 week ago mytechmint.com Show details

Mar 18, 2022  · Answer: Mass percent of nitric acid in the sample = 69 % [Given] Thus, 100 g of nitric acid contains 69 g of nitric acid by mass. Molar mass of nitric acid (HNO 3) = {1 + 14 + 3 (16)} g mol –1. = 1 + 14 + 48. = 63 g mol –1. ∴ Number of moles in 69 g of HNO 3. Volume of 100g of nitric acid solution.

1 week ago ncertmcq.com Show details

Here we have given NCERT Solutions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry. Question 1. Calculate the molecular mass of the following : (i) H 2 O (ii) CO 2 (iii) CH 4 ... We hope the NCERT Solutions for Class 11 Chemistry at Work Chapter 1 Some Basic Concepts of Chemistry, help you. If you have any query regarding ...

2 weeks ago vedantu.com Show details

4 days ago myeduscience.com Show details

May 22, 2021  · NCERT Solutions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry. NCERT Solutions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry are been solved by our expert teachers . All the solutions given in this page are solved based on CBSE,AHSEC Syllabus and NCERT guidelines. NCERT Exercises Question 1.1

5 days ago solutionsforclass.com Show details

Sep 23, 2021  · NCERT Solutions For Class 11, Chemistry, Chapter 1, Some Basic Concepts Of Chemistry is very important chapter of Class 11 and also for class 12 and many competitive exams. Chapter 1 class 11 chemistry cover basic fundamentals which are helpful in learning and understanding chemistry. Solutions for chapter 1, class 11 given below. add img […]

5 days ago ncertbooksolutions.com Show details

Jul 06, 2021  · The maximum number of molecules are present in. (a) 15 L of H 2 gas at STP. (b) 5 L of N 2 gas at STP. (c) 0.5 g of H 2 gas. (d) 10 g of O 2 gas. Answer. A. Question. The number of water molecules in 250 mL of water is closest to [Given, density of water is 1.0 g mL–1; Avogadro’s number = 6.023 × 1023]

Molecules

1 week ago esaral.com Show details

Aug 12, 2021  · Download NCERT Solutions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry PDF”. Question 1. Calculate the molar mass of the following: Question 2. Calculate the mass percent of different elements present in sodium sulphate $\left (\mathrm {Na}_ {2} \mathrm {SO}_ {4}\right)$. Question 3.

3 days ago cbselabs.com Show details

Free NCERT Solutions for Class 11 Chemistry Chapter 1 Some basic Concepts of Chemistry solved by expert teachers from latest edition books and as per NCERT (CBSE) guidelines.Class 11 Chemistry Some basic Concepts of Chemistry NCERT Solutions and Extra Questions with Solutions to help you to revise complete Syllabus and Score More marks.

1 week ago aglasem.com Show details

Jan 07, 2022  · January 7, 2022. in Extras. Reading Time: 3 mins read. 0. NCERT Book for Class 11 Chemistry Chapter 1 Some Basic Concepts Of Chemistry is available for reading or download on this page. Students who are in Class 11 or preparing for any exam which is based on Class 11 Chemistry can refer NCERT Book for their preparation.

1 week ago aakash.ac.in Show details

NCERT Solutions for Class 11 Chemistry Chapter 1- Some Basic Concepts of Chemistry. This chapter introduces students to the classification of matter based on the nature of their substances which include pure substances and mixtures and the properties of these matters and their measurement. This chapter recalls the International System of Units ...

6 days ago futurestudypoint.com Show details

May 15, 2021  · Study notes of Maths and Science NCERT and CBSE from class 9 to 12. Class 11 NCERT solutions of Physics and Chemistry. Chapter 1 – Some concepts of the chemistry. Chapter 1-Physical World. Q1. Calculate the molar mass of the following. Ans.(i) CH 4 . The molecular mass of carbon is = 12.011 u, the molecular mass of hydrogen = 1.oo8 u

1 week ago panotbook.com Show details

May 27, 2022  · Chemistry is the branch of science that studies the composition, properties, and interaction of matter. Chemists are interested in knowing how chemical transformations occur. Chemistry plays a central role in science and is often intertwined with other branches of science like physics, biology, geology, etc. Chemistry also plays an important ...

1 week ago freencertsolutions.com Show details

Answer: (i) Balancing the given chemical equation, From the equation, 1 mole (28 g) of dinitrogen reacts with 3 mole (6 g) of dihydrogen to give 2 mole (34 g) of ammonia. ⇒ 2.00 × 10 3 g of dinitrogen will react with dihydrogen i.e., 2.00 × 10 3 g of …

1 week ago headwaythemes.com Show details

Some Basic Concepts of Chemistry Q1.11 Chapter 1 NCERT solutions CHEMISTRY Class 11 Class 11th | States of Matter | NCERT Solutions: Q 1 to 15 ... NCERT Solutions for Class 11 Chemistry: Chapter 1 (Some Basic Concepts of Chemistry) are provided in this page for the perusal of Class 11 Chemistry students. These solutions can also be downloaded ...

1 week ago learncbse.in Show details

Topics and Subtopics in NCERT Solutions for Class 11 Chemistry Chapter 12 Organic Chemistry Some Basic Principles and Techniques: Section Name. Topic Name. 12. Organic ChemistrySome Basic Principles and Techniques. 12.1. General Introduction. 12.2. Tetravalence of Carbon: Shapes of Organic Compounds.

3 days ago topperlearning.com Show details

NCERT Solutions for Class 11-science Chemistry CBSE Chapter 1: Get free access to Some Basic Concepts of Chemistry Class 11-science Solutions which includes all the exercises with solved solutions. Visit TopperLearning now!

1 week ago chickenkiller.com Show details

Important Questions for Class 11 Chemistry Chapter 1 Some Basic Concepts of Chemistry Class 11 Important Questions The Solid State Class 11 Important Questions Very Short Answer Type, Long Answer Type, Matching Type Questions etc.

4 days ago instasolv.com Show details

Important Topics for NCERT Solutions for Chapter 1- Some Basic Concepts of Chemistry. The Chapter of NCERT Solutions for Class 11 Chemistry familiarizes you with the topics like molecular weight of compounds, molecular formulae, mass percent and concentration among other things. Related problems are also solved to make you catch the concepts easily.

6 days ago embibe.com Show details

Feb 23, 2022  · There are 14 chapters in NCERT Class 11 Solutions 2022, starting from “Some basic concepts of Chemistry” to “Environmental Chemistry”. Along with the NCERT solutions, students can know the new marking scheme important chapter-wise questions and answers that will benefit their examination.

2 weeks ago youtube.com Show details

May 27, 2022  · In this lecture, Sunil sir has covered Chemistry class 11 chapter 1 i.e Mole concept in one shot for NEET 2022 exam. He has taught each & every topic of the ...

1 day ago cbseboy.in Show details

May 21, 2021  · NCERT Exemplar Class 11 Chemistry Solutions. Chapter 1 Some Basic Concepts of Chemistry; ... This chemistry NCERT Solutions class 11 chapter 7 talks about the concepts of equilibrium in chemical and physical processes and details related to the equilibrium’s dynamic nature. There are also some insights related to the law of mass action, the ...

2 days ago shaalaa.com Show details

NCERT solutions for Chemistry Part 1 and 2 Class 11 chapter 1 (Some Basic Concepts of Chemistry) include all questions with solution and detail explanation. This will clear students doubts about any question and improve application skills while preparing for board exams. The detailed, step-by-step solutions will help you understand the concepts better and clear your …

2 weeks ago youtube.com Show details

NCERT Chemistry Class 11 Chapter 1 Question 1.29 Detailed Answers / SolutionsSome Basic Concepts of ChemistryExercise Solutions NCERT Chemistry Answer Series

2 weeks ago panotbook.com Show details

May 28, 2022  · Organic Chemistry: Some Basic Principles and Techniques NCERT Textbook PDF. 28/05/2022 / English Books PDF / CBSE, Chemistry, NCERT Textbook And Solution PDF / By Kaju. ‘NCERT Solutions for Class 11 Chemistry Chapter 12 ‘ PDF Quick download link is given at the bottom of this article. You can see the PDF demo, size of the PDF, page numbers ...

6 days ago coolgyan.org Show details

NCERT Exemplar Chemistry Class 11 Chapter 1 Some Basic Concepts of Chemistry is essential to study for students to score good marks in Class 11 and entrance examinations. Students are advised to get well versed with this exemplar solutions. NCERT exemplar chemistry Class 11 Chapter 1 has important questions with answers, Class 11 chemistry ...

4 days ago meritnation.com Show details

All questions and answers from the NCERT Book of Class 11 Science Chemistry Chapter 1 are provided here for you for free. You will also love the ad-free experience on Meritnation’s NCERT Solutions. All NCERT Solutions for class Class 11 Science Chemistry are prepared by experts and are 100% accurate.

1 week ago toppersbulletin.com Show details

NCERT Solution for Chemistry Class 11 Chapter 1 – Some Basic Concept of Chemistry. Q2 :Calculate the mass percent of different elements present in sodium sulphate (Na2SO4). Q3 :Determine the empirical formula of an oxide of iron which has 69.9% iron and 30.1% dioxygen by …

4 days ago byjus.com Show details

NCERT Solutions For Class 11 Chemistry Download Chapter Wise PDF for 2021-22. NCERT Solutions for Class 11 Chemistry is a study material which is developed by the faculty at BYJU’S by keeping in mind the understanding capacity of Class 11 students.NCERT Solutions for Class 11 are drafted in a simple and understandable manner to help students ace the …

2 weeks ago ncertsolutions.guru Show details

Sep 07, 2021  · Class 11 Chemistry NCERT Solutions in Hindi Medium. Chapter 1 Some Basic Concepts of Chemistry. रसायन विज्ञान की कुछ मूल अवधारणाएँ. Chapter 2 Structure of The Atom. परमाणु की संरचना. Chapter 3 Classification of …

1 week ago neetprep.com Show details

An electrophile among the following is - 1.OH- 2.NC- 3.R3C- 4. Carbonyl group Organic Chemistry - Some Basic Principles And Techniques Organic Chemistry Practice questions, MCQs, Past Year Questions (PYQs), NCERT Questions, Question Bank, Class 11 and Class 12 Questions, NCERT Exemplar Questions and PDF Questions with answers, solutions, …


text:
# Thread: How to prove differentiable at x is not 0

1. ## How to prove differentiable at x is not 0

Set
f(x) = {x sin(1/x), x not = 0
f(x) = {0, x = 0

and g(x) = xf(x)

Assume we know that f is continuous at 0 but not differentiable there, and that g is differentiable at 0. Both f and g are differentiable at each x not = 0.

(a) Find f'(x) and g'(x) for x not = 0.
(b) Show that g' is not continuous at 0.

I can find the f'(x) does not exist exist at 0 and g'(x) equals to 0, but I do not know how to prove something when says is not at a point, help me please.

2. Originally Posted by 450081592
Set
f(x) = {x sin(1/x), x not = 0
f(x) = {0, x = 0

and g(x) = xf(x)

Assume we know that f is continuous at 0 but not differentiable there, and that g is differentiable at 0. Both f and g are differentiable at each x not = 0.

(a) Find f'(x) and g'(x) for x not = 0.
(b) Show that g' is not continuous at 0.

I can find the f'(x) does not exist exist at 0 and g'(x) equals to 0, but I do not know how to prove something when says is not at a point, help me please.
At any point x apart from x=0 the functions are given by simple formulas, $f(x) = x\sin(1/x)$ and $g(x) = x^2\sin(1/x)$, and you can differentiate them by the usual rules (product rule, chain rule).

3. thanks now I know how to find f'(x) and g'(x) for x not equal to 0, but how do I prove g' is not continuous at 0, I really bad at proving something that is not something. I should prove by contradiction, right?

I have got f'(x) = sin(1/x) - 1/xcos(1/x) g'(x) = 2x sin(1/x)-cos(1/x), can I just show that the limit does not exist on g'(x) when x is approaching to 0?

4. Originally Posted by 450081592
thanks now I know how to find f'(x) and g'(x) for x not equal to 0, but how do I prove g' is not continuous at 0, I really bad at proving something that is not something. I should prove by contradiction, right?

I have got f'(x) = sin(1/x) - 1/xcos(1/x) g'(x) = 2x sin(1/x)-cos(1/x), can I just show that the limit does not exist on g'(x) when x is approaching to 0?
Exactly! The limit at 0 for g(x) doesn't exist because thus g'(x) can't exist where g(x) doesn't have a limit.

5. In particular, if a function is not continuous at x= a, it cannot be differentiable there.

6. Originally Posted by Jameson
Exactly! The limit at 0 for g(x) doesn't exist because thus g'(x) can't exist where g(x) doesn't have a limit.

There's a confusion here, me thinks: it's g'(x) which isn't continuous at x = 0. Of course g is cont. at x=0 since, as shown, it is differentiable there.
Now, as the OP wrote, $g'(x)=2x\sin \frac{1}{x}-\cos \frac{1}{x}$ , and it's easy to see the limit of this when x approaches zero doesn't exists. For example, one can make $x\rightarrow 0$ through the points $x_n=\frac{1}{2n\pi}\,,\,n\in \mathbb{N}$ and then through $y_n=\frac{1}{(2n-1)\pi}\,,\,n\in \mathbb{N}$ , and we get two different results.

Tonio

7. Originally Posted by tonio
There's a confusion here, me thinks: it's g'(x) which isn't continuous at x = 0. Of course g is cont. at x=0 since, as shown, it is differentiable there.
Now, as the OP wrote, $g'(x)=2x\sin \frac{1}{x}-\cos \frac{1}{x}$ , and it's easy to see the limit of this when x approaches zero doesn't exists. For example, one can make $x\rightarrow 0$ through the points $x_n=\frac{1}{2n\pi}\,,\,n\in \mathbb{N}$ and then through $y_n=\frac{1}{(2n-1)\pi}\,,\,n\in \mathbb{N}$ , and we get two different results.

Tonio
I didn't notice the existence of the limit xsin(1/x) or x^2sin(1/x), which both clearly exist. I wrote the limit doesn't exist because I was thinking of the difference quotient but wasn't thinking it through obviously. Thanks for pointing that out.


text:
+1 vote
44 views

How addition of $+3$ and $-3$ in sign magnitude form is $-5?$

0

i am getting -6.

selected by
+1 vote
+3 is ${\color{Red} 0}011$ in sign magnitude where ${\color{Red} 0}$ indicates positive.

-3 is ${\color{Red} 1}011$ in sign magnitude where ${\color{Red} 1}$ indicates negative.

when we add them in sign magnitude,

011 + 011 will give 110(magnitude) and adding ${\color{Red} 0}$ + ${\color{Red} 1}$  we get ${\color{Red} 1}$(sign bit)

=> the number is ${\color{Red} 1}110$ which is -6.
edited by
0

is 1110

is -5 or it is -6?

0
it is -6 coz 6 is 0110 and its when we change its sign bit it becomes -6 i.e. 1110
0

@Satbir

why isn't it 0??

+1 vote
1
2


text:
## Cryptology ePrint Archive: Report 2016/800

Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious

Bar Alon and Eran Omri

Abstract: An $\alpha$-fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than $\alpha$. Cleve [STOC 1986] has shown that if half of the parties can be corrupted, then, no $r$-round coin-tossing protocol is $o(1/r)$-fair. For over two decades the best known $m$-party protocols, tolerating up to $t\geq m/2$ corrupted parties, were only $O(t/\sqrt{r})$-fair. In a surprising result, Moran, Naor, and Segev [TCC 2009] constructed an $r$-round two-party $O(1/r)$-fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel, Omri, and Orlov [Crypto 2010] extended the results of Moran et al.~to the {\em multiparty setting} where strictly fewer than 2/3 of the parties are corrupted. They constructed a $2^{2^k}/r$-fair $r$-round $m$-party protocol, tolerating up to $t=\frac{m+k}{2}$ corrupted parties.

Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $O(\log^3(r)/r)$-fair (almost optimal) three-party coin-tossing protocol. Their work brings forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $t=2m/3$, where $m>3$) were $\theta(1/\sqrt{r})$-fair. We construct an $O(\log^3(r)/r)$-fair $m$-party coin-tossing protocol, tolerating up to $t$ corrupted parties, whenever $m$ is constant and $t<3m/4$.

Category / Keywords: foundations / Keywords: coin-tossing; coin-flipping; protocols; fairness; fair computation; dishonest majority

Original Publication (with major differences): IACR-TCC-2016

Date: received 21 Aug 2016, last revised 23 Aug 2016

Contact author: omrier at gmail com

Available format(s): PDF | BibTeX Citation

Note: A few minor changes were made.

Short URL: ia.cr/2016/800

[ Cryptology ePrint archive ]


text:
# Math Help - Population Growth rate formula

1. ## Population Growth rate formula

Hi,
I know how to find the population growth if a growth rate is given but how do I find the growth rate if only number of years and estimated population given.ie population now = 23600 and after 53 years will exceed 35000

Thanks...Mark

2. Originally Posted by manich44
Hi,
I know how to find the population growth if a growth rate is given but how do I find the growth rate if only number of years and estimated population given.ie population now = 23600 and after 53 years will exceed 35000

Thanks...Mark
Exponential growth is modelled by $A(t) = A_0e^{kt}$

Where

• $A(t)$ = Number at time $t$
• $A_0$ = Number at $t=0$
• $k$ = growth constant $k>0$
• $t$ = time

In your example there is enough information to find $k$. Rearranging the equation to make k the subject:

$k = \frac{1}{t}(ln[A(t)] - ln(A_0))$

The equation at the top is one you should learn as it's rarely given in exams


text:
# ssl_server_name.yaml¶

## Description¶

This file is used to configure aspects of TLS connection handling for both inbound and outbound connections. The configuration is driven by the SNI values provided by the inbound connection. The file consists of a set of configuration items, each identified by an SNI value (fqdn). When an inbound TLS connection is made, the SNI value from the TLS negotiation is matched against the items specified by this file and if there is a match, the values specified in that item override the defaults. This is done during the inbound connection processing and be some outbound properties can be overridden again later, such as via remap.config or plugins.

By default this is named ssl_server_name.yaml. The file can be changed by settting proxy.config.ssl.servername.filename. This file is loaded on start up and by traffic_ctl config reload if the file has been modified since process start.

The configuration file is yaml-based. After parsing the configuration, a list of tables will be the result. Each table is a set of key / value pairs that create a configuration item. This configuration file accepts wildcard entries. To apply an SNI based setting on all the servernames with a common upper level domain name, the user needs to enter the fqdn in the configuration with a *. followed by the common domain name. (*.yahoo.com for e.g.,).

Key Meaning
fqdn Fully Qualified Domain Name. This item is used if the SNI value matches this.
verify_origin_server

One of the values NONE, MODERATE, or STRICT.

By default this is proxy.config.ssl.client.verify.server.

verify_client

One of the values NONE, MODERATE, or STRICT.

By default this is proxy.config.ssl.client.certification_level.

client_cert

The client certificate to use for the outbound connection.

If this is relative it is relative to the path in proxy.config.ssl.server.cert.path. If not set proxy.config.ssl.client.cert.filename is used.

disable_h2

true or false.

If false then HTTP/2 is removed from the valid next protocol list. It is not an error to set this to false for proxy ports on which HTTP/2 is not enabled.

tunnel_route Destination as an FQDN and port, separated by a colon :.

Client verification, via verify_client, correponds to setting proxy.config.ssl.client.certification_level for this connection as noted below.

NONE0
Do not request a client certificate, ignore it if one is provided.
MODERATE - 1
Request a client certificate and do verification if one is provided. The connection is denied if the verification of the client provided certificate fails.
STRICT - 2
Request a client certificate and require one to be provided and verified. If the verification fails the failure is logged to diags.log and the connection is denied.

Upstream (server) verification, via verify_origin_server, is similar to client verification except there is always an upstream certificate. This is equivalent to setting proxy.config.ssl.client.verify.server for this connection.

NONE - 0
Do not verify the upstream server certificate.
MODERATE - 2
Do verification of the upstream certificate but do not enforce. If the verification fails the failure is logged in diags.log but the connection is allowed.
STRICT - 1
Do verification of the upstream certificate. If verification fails, the failure is logged in diags.log and the connection is denied.

If tunnel_route is specified, none of the certificate verification will be done because the TLS negotiation will be tunneled to the upstream target, making those values irrelevant for that configuration item. This option is explained in more detail in SNI Routing.

## Examples¶

Disable HTTP/2 for no-http2.example.com.

- fqdn: no-http2.example.com
disable_h2: true

Require client certificate verification for example.com and any server name ending with .yahoo.com. Therefore, client request for a server name ending with yahoo.com (for e.g., def.yahoo.com, abc.yahoo.com etc.) will cause Traffic Server require and verify the client certificate. By contrast, Traffic Server will allow a client certficate to be provided for example.com and if it is, Traffic Server will require the certificate to be valid.

- fqdn: example.com
verify_client: MODERATE
- fqdn: '*.yahoo.com'
verify_client: STRICT

Disable outbound server certificate verification for trusted.example.com and require a valid client certificate.

- fqdn: trusted.example.com
verify_origin_server: NONE
verify_client: STRICT


text:
Math Calculators, Lessons and Formulas

It is time to solve your math problem

mathportal.org

# Operations on sets calculator

This calculator is an online tool to find find union, intersection, difference and Cartesian product of two sets. It will also generate a step by step explanation for each operation.

Operations on Sets Calculator
0 1 2 3 4 5 6 7 8 9 , del
 Union of sets A and B $~~(A \cap B)$ Intersection of sets A and B $~~(A \cup B)$ Difference of sets A and B $~~(A \setminus B)$ Cartesian product of sets A and B $~~(A \times B)$
Show me an explanation
examples
example 1:
Find the union $\color{blue}{A \cap B}$ of sets $A = \{ 5, 7, 3, 1\}$ and $B = \{2, 5, 9\}$.
example 2:
If $A = \{a, b, c, d \}$ and $B = \{c, d, e, f\}$, find $\color{blue}{A \cup B}$.
example 3:
Find difference $\color{blue}{\left( A \setminus B \right)}$ of sets $A = \{4, 5, 1, 8, 9, 6\}$ and $B = \{5, 7, 6, 8\}$.
example 4:
Find Cartesian product $\color{blue}{\left( A \times B \right)}$ of sets $A = \{1, 2, 3\}$ and $B = \{x, y\}$.

Quick Calculator Search


text:
# Project

Part of the grade (30%) in this course is based on a project to be handed in during the course. The project will consist of two unequal parts, dealing with unconstrained and constrained optimization. The first part will be published in the beginning of February, and the second part at the end of March.

You may work on the project either alone or in groups of up to three students.

The idea is that you are done with part 1 (unconstrained) roughly as we begin with constrained optimization (end of February/beginning of March), and with part 2 (constrained) by the end of this semester (beginning of May).

Tentatively the projects will be weighed as 10% and 20% in the final grade.

## Project 1

The project description is here. We will deal with a least squares type problem which has a simple geometric interpretations, thereby making it very simple to understand and vizualize.

• You can work in groups of 1-3 students
• You can use any programming language, but Python or Matlab is recommended (in particular, vizualization is easy)
• Submit your reports via https://ovsys.math.ntnu.no/
• Only one report per group, please!
• Do not write your names in the report. Please mark them with either student or candidate numbers.
• Please submit your report as PDF and zip all the accompanying code into one file.

## Project 2

The project description is here. Basically we look at the same problem as in project 1, but with further restrictions on the eigenvalues.

• Slater's constraint qualification has been discussed during the lectures, but apparently it is not in N&W. It holds when the constraints $c_i$ are concave for all $i\in \mathcal{I}$, linear for all $i \in \mathcal{E}$, and there is a feasible point $\hat{x}$ such that $c_i(\hat{x}) >0$, for all $i\in \mathcal{I}$. Slater's CQ implies that the cone $\mathring{\mathcal{F}}(x) = \{\, p \mid \nabla c_i(x)^\mathrm{T} p > 0, \forall i \in \mathcal{A}(x) \cap \mathcal{I}, \nabla c_i(x)^\mathrm{T} p = 0, \forall i \in \mathcal{E}\,\}$ is not empty for all feasible $x$: indeed, it must at least contain the direction $\hat{x}-x$. This cone is contained in the radial cone, which is in turn contained in the tangent cone, which in turn is contained in the cone of linearized feasible directions. Further, the closure of $\mathring{\mathcal{F}}(x)$ equals $\mathcal{F}(x)$, the cone of linearized feasible directions. Finally, the tangent cone is already closed, and therefore all the tangent cone must be equal with $\mathcal{F}(x)$. Owing Farkas' lemma this implies the necessity of the KKT conditions for local optimality.


text:
# Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Ernesto Birgin, John Gardenghi, José-Mario Martinez, Sandra Augusta Santos, Philippe Toint

Research output: Working paper

### Abstract

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p\geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most $O(\epsilon^{-(p+1)/p})$ evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for $p=1$ and $p=2$.
Original language English 2015 Namur center for complex systems 8 naXys-05-2015 Published - Jun 2015

### Publication series

Name naXys Technical Reports naXys 05-2015

### Keywords

• Nonlinear optimization
• Complexity theory
• High-order models

### Cite this

Birgin, E., Gardenghi, J., Martinez, J-M., Santos, S. A., & Toint, P. (2015). Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. (naXys Technical Reports; Vol. 05-2015). 2015: Namur center for complex systems.


text:
auctex-devel
[Top][All Lists]

## Re: [AUCTeX-devel] Questions about cleveref.el

 From: Mosè Giordano Subject: Re: [AUCTeX-devel] Questions about cleveref.el Date: Tue, 3 Jan 2017 00:13:54 +0100

Hi Arash,

2016-12-30 11:34 GMT+01:00 Arash Esbati <address@hidden>:
> Hi all,
>
> I've just fixed 2 typos in cleveref.el and 2 things occurred to me if
> you're a C-c RET' centric, RefTeX-plugged-into-AUCTeX user:
>
> 1) This style uses TeX-arg-label' and not TeX-arg-ref'.  It means an
>    extra RET in the "SELECT A REFERENCE FORMAT" window, which is useless
>    since you've already selected a format.

You're right, TeX-arg-ref' should be used here.

> 2) TeX-arg-cleveref-multiple-labels' does not let you use RefTeX to
>    select label(s) which is much more convenient.
>
> Item 1) is fixed easily, 2) should also be doable with a check againt
> reftex-label' and such.  My question is if there was a particular
> reason to implement the code this way?

Can reftex-label' query for more than one label?  I had a similar
problem in biblatex: there are macros taking more than one reference,
but this isn't particularly easy to do with RefTeX, so I defined a
hand-made function (LaTeX-arg-biblatex-cites').

> And I think (font-latex-set-syntactic-keywords)' in the fontification
> part is also not needed.

Because there are no verbatim like macros, right?  I think you're right.

While looking to clevere.el, I remembered that in tex-style.el is
defined a custom option, LaTeX-reftex-ref-style-auto-activate', that
controls whether a RefTeX reference style (for \ref & friends) should
be automatically enabled.  Maybe you could define a similar option (t
by default) for \cite & friends, to be used for example in biblatex.

Bye,
Mosè


text:
Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorTodd_Trimble
• CommentTimeDec 17th 2012

I added a section on strictification of pseudofunctors $C \to Cat$ to pseudofunctor, after seeing Finn and Mike respond to Karol in the stable monoidal derivator thread at the Café. The discussion is fairly sketchy and pedestrian. Also added a few references.

• CommentRowNumber2.
• CommentAuthorMike Shulman
• CommentTimeDec 17th 2012

Looks good, thanks! I made the statement of the theorem a little more precise: it’s not just an equivalence of categories, but an isomorphism.

• CommentRowNumber3.
• CommentAuthorJohn Baez
• CommentTimeDec 23rd 2020

Added theorem saying that every pseudofunctor can be “normalized”.

• CommentRowNumber4.
• CommentAuthorAlec Rhea
• CommentTimeMar 5th 2021

Added definition of composition of pseudofunctors for posterity, changed notation slightly.