# Tag Info

1

This is called a derangement. It's hard to solve numerically exactly. From http://en.wikipedia.org/wiki/Derangement as n approaches infinity, permutation(n) divided by derangement(n) is 1/e

0

If carry is not allowed, better bound would be $5* 9^{\lceil log_{10}^n\rceil - 1}$ + some delta. But, what happens when carry is there in addition?

1

Since there are $9$ judges, there is no case of a tie (equal number of votes for and against). Thus, the number of ways that "for" gets a majority is equal to the number of ways that "against" gets a majority, and therefore, each must be half of the total number of ways to vote. The total number of ways to vote is, of course, $2^9 = 512$ (as there are nine ...

1

Got it . So There are 9 judges in total and 6 are voting for the decision of lower court and 3 are voting against . So in how many ways the decision can be reversed . It can by 5 votes for or 6,7,8 and the whole 9 to get majority so , 9C9+9C8+9C7+9C6+9C5 =1+9+36+84+126 =256 is the answer

0

You are almost there! Let $S$ be a subgroup of $S_4$ of order $8$. The orbit of $S$ under the conjugation of $S_4$ has size $24/|Stab(S)|$. Now note that the stabilizer of $S$ for this action is $N(S)$, the normalizer of $S$ in $S_4$ (i.e., the biggest subgroup of $S_4$ in which $S$ is normal). In particular $N(S)$ has size $8$ or $24$ since it contains $S$, ...

0

For each part $A_i$, you can independently choose one of the parts $B_j$, and then you have $|B_j|$ choices for each of the $|A_i|$ elements. Thus in total you have $$\prod_{i=1}^n\sum_{j=1}^m\left|B_j\right|^{\left|A_i\right|}$$ choices.

0

Indeed.   We consider what would happen were we not to stop after drawing the last red candy. The probability that the last of sixty candies drawn is one of the thirty green candies is $\tfrac{30}{60}$.   Ignoring the green candies, the probability that the last of the thirty other candies drawn is one of the twenty blue is $\tfrac{20}{30}$. ...

0

We want to use Hall’s theorem to guarantee a complete matching, and then show that the complete matching is actually a perfect matching. Let us show the conditions for Hall’s theorem. Since the graph is regular and edges go from $X$ to $Y$. Without loss of generality consider $X$ . Let $A \subseteq X$ be an arbitrary subset, and denote by the set of ...

2

Suppose we seek to evaluate $$\sum_{k=0}^n \frac{n!}{k!} (n-k) n^k = n! n^n \sum_{k=0}^n \frac{n-k}{k!} n^{k-n}.$$ Introduce $$n^{k-n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^k}{z^{n+1}} \frac{1}{1-z/n} \; dz.$$ Observe that this integral provides an Iverson bracket, as it vanishes when $k\gt n.$ Therefore we may extend $k$ to infinity. We get ...

0

As you have noted, there are $|S| \cdot k$ edges leaving $S$. Suppose the neighborhood set $N(S)$ of $S$ is smaller than $S$. Then there are $|N(S)| \cdot k < |S| \cdot k$ edges leaving $N(S)$, a contradiction.

0

The following is almost certainly overkill, but what the heck. If you think of picking red, blue, and green as corresponding to taking steps in the $x$, $y$, and $z$ directions on a three-dimensional lattice, each way of drawing candies corresponds to a path from $(0,0,0)$ to $(10,20,30)$ of steps that go one unit in a positive direction each. In the ...

1

I came across following solution but curious to see how others approach this problem: Let $T_r$, $T_b$ and $T_g$ be the "draw number" of last red, blue and green candies drawn respectively. So the required probability here is $P(T_r<T_b \cap T_r< T_g)$ Now the event $T_r<T_b \cap T_r< T_g$ can be achieved in two different and independent ways, ...

5

One way is to rewrite the L.H.S. as a telescoping sum: $\displaystyle\sum_{k=0}^{n}\left(\frac{n!~n^{k+1}}{k!}-\frac{n!~n^k}{(k-1)!}\right)$.

3

Can you show $$\sum_{k=0}^m\frac{n!}{k!}(n-k)n^k=\frac{n!}{m!}n^{m+1}$$

0

So you would like to prove that $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1} .$ There so many ways for proving this identity. One method is the following: Let's count the number of ways to choose $k+1$ elements from an $n+1$ set. By definition, the left hand side of the equation is the number of ways to choose $k+1$ from $n+1$. Since $1 ≤ k+1 ≤ n$, we ...

3

The assertion is false. Choose $P_1,...,P_4$ to be the four corners $(\pm 1,\pm 1)$, and set $P_5=(1/2,1/2)$ and $P_6=-P_5$. Then $$M= min\{d(P_{\sigma(1)}, P_{\sigma(2)})+d(P_{\sigma(1)},P_{\sigma(3)})+d(P_{\sigma(2)},P_{\sigma(3)}),\sigma\in S_6\}=3\sqrt{2}.$$ Now set $P_5'=P_5+\varepsilon(1,1)$ and $P_6'=-P_5'$. Then, for small $\varepsilon>0$, we have ...

2

Note that for any three positive integers $a,b,c$, if $2^k\leqslant b<a<c<2^{k+1}$ for some $k\in\mathbb{Z}_{>0}$, then $$bc<ac<a\cdot 2^{k+1}=2a\cdot 2^k\leqslant 2a\cdot a=2a^2,$$ and $$bc>ba\geqslant 2^ka=\frac{1}{2}\cdot 2^{k+1}a>\frac{1}{2}\cdot a\cdot a=\frac{1}{2}a^2.$$ Thus, $2^k\leqslant b<a<c<2^{k+1}$ for some ...

1

Let set $S$ be the set of integers from $1$ to $2046$, we split $S$ to $S_i$s like this: $$S_1=\{1,2,3\}\\S_i=\{s\in\mathbb{Z}\,|\,2^{i}\le s\lt2^{i+1}\}\quad (2\le i\lt10)\\ S_{10}=\{1024,1025,\dots,2046\}$$ So we have $10$ sets in total, by Pigeonhole principle there's a set which has at least $\lceil\frac{21}{10}\rceil=3$ elements from those $21$ chosen ...

6

Let the 21 numbers be $x_1<x_2<\ldots <x_{21}$. It is not possible to have $x_{k+2}\ge 2x_k+1$ (or equivalently $x_{k+2}+1\ge 2(x_k+1)$) for all $k$ as that would lead to $2047 \ge x_{21}+1\ge 2^{10}(x_1+1)\ge 2^{11}=2048$. Thus we find $k$ such that $x_{k+2}\le 2x_k$. With $b:=x_k$, $a:=x_{k+1}$, $c:=x_{k+2}\le 2b$, we have $$bc\le ... 0 If we assume the pears are cut into halves and the bananas into quarters and read "1/2" as "at least 1/2" and "3/4" as "at least 3/4" and that the divisions are uniform and independent, the probability would be$$ \frac{9}{10} \times \frac{9}{12} = \frac{27}{40} = 0.675 . $$2$$n\binom{l}{a_1,\ldots,a_n}\\=\binom{l}{a_1,a_2,\ldots,a_{n-1},a_n}+\binom{l}{a_2,a_3\ldots,a_{n},a_1}+\ldots+\binom{l}{a_n,a_1,\ldots,a_{n-2},a_{n-1}}$$but the last sum is less than the sum of any multinomial coefficient \binom{l}{x_1,x_2,\ldots,x_{n-1},x_n} with x_1+x_2+\ldots+x_{n-1}+x_n=n, hence it is less than n^l. The same argument gives the ... 0 The result is false. Try the subset \{1,2,12,24,48,92,96,100\}. Mathematica: DuplicateFreeQ[Map[Total[Subsets[{1, 2, 12, 24, 48, 92, 96, 100}]]]] gives True. 0 I'm going to provide an answer using basic probability rules and the Binomial distribution. Let n be the number of children in a family. Let B be the number of boys among the n children in a family - obviously, B\leq n, and I assume that$$ B\sim \textrm{Binomial}(n,p) $$where p is the probability of a male child. Now, I will use M and F to ... 2 The chance that a particular number is not drawn at all is (\frac{99}{100})^{100}. The chance that a particular number is drawn exactly once is \binom{100}{1}\frac{1}{100}(\frac{99}{100})^{99}. Now you can find the chance that a particular number is multiply drawn. (Interestingly, this never differs by much from \frac14 which is the answer for just ... 3 I would do the problem exactly the way you did it. Here is an alternative approach to confirm your answer. We can line up the five students in 5! ways, leaving spaces between them and at the ends of the row in which to insert the teachers. There are six such spaces, four between successive students and two at the ends of the row. We can insert the ... 2 Students S_1,\dots,S_5, teachers T_1,T_2,T_3. Suppose we put S_1 into a particular seat. Then there are 4!=24 ways of choosing the anticlockwise order for the remaining students. There are two 5 possible positions for the teachers. We can choose which of them to leave unoccupied in {5\choose2}=10 ways, then place the teachers in the others in ... 3 Umm your answer is greater than the total possible 7 digit numbers even though you are not using all the possibilities .... I think the correct way would be to use exclusion i.e all numbers that you can generate using those numbers - all possible numbers you generate that begin with 0. Therefore, numbers that can be generated using 0,1,1,5,6,6,6 without ... 5 There are 7 symbols, that can be arranged in 7! many ways. However, the three 6's and 2 1's can be interchanged, so we have \frac{7!}{3! 2!} = 420 many such sequences. But I think 0 at the start is forbidden , so we have to substract all sequences that start with 0, of which there are \frac{6!}{3! 2!} = 60. That leaves 360 numbers. 4 There are 6 possible positions for the 0 (not the first). For each of these there are then 6 possible locations for the 5, so a total of 36 so far. There are now {5\choose2}=10 possible choices for the positions of the two 1s. The number is then completely determined, because the three 6s must go into the remaining positions. So in total there are 360 ... 2 Let G be a graph with exactly one perfect matching M, 2n vertices and m edges. Let v and w be two vertices that are endpoints of an edge of M and let d(v)=t. A neighbor u of v different from w is endpoint of an edge e_u of M and w may not have an edge to the other endpoint of e_u or we find an alternating 4-cycle, which would ... 4 Use induction. Check the base cases. Let's look at the partitions of 2n+1. Every partition of 2n+1 includes odd number of 1s. If a partition contains 2k+1 1s, all the other terms in it are even. This kind of partitions can be identified with partitions of n-k by dividing the even numbers by 2. So, q(2n+1)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1, ... 2 Here is a formal way (though not much different than yours)... Add up the following: The amount of numbers of the form \underbrace{2,3,4,5,6}_{5\text{ options}}|\underbrace{0,2,3,4,5,6}_{6\text{ options}}|\underbrace{0}_{1\text{ option}} The amount of numbers of the form \underbrace{2,3,4,5,6}_{5\text{ options}}|\underbrace{0,2,3,4,5,6}_{6\text{ ... 4 A proper calculation is that you have 13 ways to choose the three of a kind, 4 ways to choose which three of that rank you have, 12 ways to choose the rank of the pair, and {4 \choose 2}=6 ways to choose the two cards of the pair. Multiplying gives 3744 hands. Your approach has several errors. You have 52 choices for the first card, as we ... 1 Let f be the function from \Omega_n^k to \Omega_n^{n-k} defined by f: A \mapsto A^c, where A^c is the complement of A in \Omega_n. (Recall that the complement of a set X in a universe U is defined to be the set of all elements in U which are not in X.) It can be shown that the function f is one-to-one and onto. Hence, the cardinality ... 1 If you work out the answer manually, you get x=-6.46. You could try the method of generating functions to obtain a formula. 0 If m = 1, we have a set \{1,2\} and there's only 1 unordered pair we can form. If m = 2, we have a set \{1,2,3,4\} and there are 3 pairings we can form, namely,$$\{\{1,2\}, \{3,4\}\}\{\{1,3\}, \{2,4\}\}\{\{1,4\}, \{2,3\}\}For a general m, we have a set \{1,2,\dots,2m\} and the number of pairings we can form is the number of ... 1 Line up the m boxes in some order from left to right. We choose two of the 2m objects to place in the first box, choose two of the remaining 2m - 2 boxes in the second box, choose two of the remaining 2m - 4 boxes in the third box, and so forth until we place the final two objects in the mth box. We can do this in \begin{align*} ... 0 The wrong point in your think is that the number of ways to paired 2m objects is not \frac{(2m)!}{2!(m-2)!}, this number is for chose a pair of 2m objects. In fact, the number of ways to paired 2m objects is: Put all 2m on a row, that is (2m)! ways. Now, each 2 objects, makes a pair, but how the order of the pairs doesn't mater we divided by ... 1 Let k be the number of ways to pair up the objects. If we want to pair them up and then assign the pairs to m boxes, we can do this in 2 steps: 1) Pair them up, which can be done in k ways. 2) Assign the m pairs to the boxes, which can be done in m! ways. Therefore \displaystyle k(m!)=\frac{(2m)!}{2^m},\; so \displaystyle ... 1 Here’s a hint: let n = 5. What’s the relation between these pairs of subsets? \begin{align*} \Omega^1 &\leftrightarrow \Omega^{5-1} \\ \hline \{1\} &\leftrightarrow \{2, 3, 4, 5\} \\ \{2\} &\leftrightarrow \{1, 3, 4, 5\} \\ \{3\} &\leftrightarrow \{1, 2, 4, 5\} \\ \{4\} &\leftrightarrow \{1, 2, 3, 5\} \\ \{5\} &\leftrightarrow \{1, ... 0 The number of ways that 2m objects can be grouped into m boxes where each box contains 2 objects is: \binom{2m}{2_{b1}, 2_{b2} ... 2_{bm}} = \frac{(2m)!}{2_{b1}!2_{b2}! ... 2_{bm}!} = \frac{(2m)!}{2^m} $$where b1 is the first box, and bm is the last box. 2 We divide by m! because the arrangement (order and which boxes they are put into) matters. We can arrange the boxes in m! ways and we would have a different arrangement. So we have to divide by m! from the previous answer. 1 There are 3m/2 adjacent faces, and m must be an even number. Else you would have a face that is adjacent to only one tetrahedra and then z wouldn't be an interior point. 2 I will assume that the question means that no digit appears more than three times. As Austin Mohr points out, the question is badly phrased. Since the leading digit cannot be zero, there are 9 \cdot 10^5 = 900,000 six digit positive integers. Like Soke, I will exclude those in which a digit appears four or more times. We consider cases. Case 1: The ... 0 This is a partial answer, which shows that it's not possible for even N. Assume that it is possible for some even number N = 2m\geq10. Without loss of generality we can assume that$$ a_1+...+a_9 = n_1, $$where n_1 is an integer. Consider the sum of a_1,...,a_7 and one of the other numbers, which we call a_{10}. Since a_1+...+a_9 is an ... 1 This is neatly handled using exponential generating functions. Assuming first that we are allowed to have 0 as the first digit (e.g. we're talking about license plates or lock combinations): each of 10 digits can occur up to 3 times, and the order of the symbols matters. The answer is$$\left[\frac{x^6}{6!}\right] ...

8

A start: Here it is easier to count the complementary number: the number of 6 digit positive integers with four or more of one digit repeated. This reduces to only four cases: (4, 1, 1), (4, 2), (5, 1), (6). The rest: (6) is simply $9$. These are $(111111, 222222, \dots, 999999)$. (5, 1) is a little trickier. First there are $9 * 8$ ways to choose two ...

2

The total number of permutations of 1-8 is $8!$. Of these $7!$ fix any one given even number, $6!$ fix two, $5!$ fix three and $4!$ fix all four. So by inclusion-exclusion the number fixing none is $8!-4\cdot7!+6\cdot6!-4\cdot5!+4!=24024$.

3

Let $S$ be the set of all permutations of $\{1, 2, . . . , 8\}$. Let $A_1$ be the set of all permutations in $S$ which has $2$ in it natural position; $A_2$ be the set of all permutations in $S$ which has $4$ in it natural position; $A_3$ be the set of all permutations in $S$ which has $6$ in it natural position and $A_4$ be the set of all permutations in ...

3

Lemma 1. If in a square matrix we replace the first row with the sum between the first and second row, its determinant stays the same. Lemma 2. If $\frac{p_n}{q_n}$ and $\frac{p_{n+1}}{q_{n+1}}$ are two consecutive convergents of the continued fraction of $\alpha$, $$\det\begin{pmatrix}p_n & p_{n+1} \\ q_n & q_{n+1}\end{pmatrix}\in\{-1,+1\}$$ From ...

Top 50 recent answers are included