Tag Info

0

I realize I'm late but here's an asymptotic approach: Since $\binom{n}{k} < \frac{n^k}{k!}$, the LHS is upper-bounded by $\log \frac{n^k}{k!} = n \log k + \sum_{j=1}^{k} \log j$. The second sum can be approximated using Euler-Maclaurin formula, but just a corresponding integral will do: $$\sum_{j=1}^{k} \log j < 1 +\int_{1}^{k} \log x dx = k \log k ... 1 This is a simple way Consider 20 unlabelled counters (C). Take away 3, now 17 are left, and there are 18 gaps (including ends) where we can insert back the 3 to comply with non-consecutive stipulation. Now serially number the counters. _C_C_C_C_C_C_C_C_C_C_C_C_C_C_C_C_C_$$\text{thus there can be}\;\; {18\choose3} = 816\;\; \text{such subsets}$$1 Your idea is very close to correct. A quadrilateral is formed by 4 points, where at most 2 may be colinear. Thus, we have$$ \underbrace{^{25} C_4}_{\text{ choose four points}} - \underbrace{^{7} C_4}_{\text{ subtract out ways to pick four colinear points}} - \underbrace{^{7} C_3 \cdot ^{18} C_1 }_{\text{ subtract out ways to pick three colinear ...

2

We can represent the 3 integers by 3 dots, and then let $x_i$ for $1\le i\le 4$ be the number of integers in the 4 gaps created by the dots. Then $x_1+x_2+x_3+x_4=17$ where $x_1, x_4\ge0$ and $x_2, x_3\ge1$; so if we let $y_i=x_i$ for $i=1,4$ and $y_i=x_i-1$ for $i=2,3$, we get $y_1+y_2+y_3+y_4=15$ where $y_i\ge0$ for each $i$, and this equation has ...

0

It's probably easier to count how many actually have two consecutive integers and subtract that from the total number of three element subsets. First we note that there are $18$ subsets with all elements consecutive. Now we wish count the number of three element subsets such that exactly two elements are consecutive. First, let's count the number of these ...

0

The reader may be surprised to learn that this can be solved with cycle indices. Suppose we seek to evaluate $$\sum_{1\le q_1 \lt q_2 \lt \cdots \lt q_k \le n} (q_1+q_2+\cdots+q_k).$$ Using the cycle index $Z(P_k)$ of the unlabeled set operator $\mathfrak{P}_{=k}$ this is $$\left. \frac{d}{dz} Z(P_k)(z+z^2+\cdots+z^n)\right|_{z=1}.$$ The OGF of the ...

0

In your calculation of $7^5$ you are in effect assuming that the first ticket is a $7$; $7^5$ is then the number of ways to choose the remaining $5$ tickets so that none of them is greater than $7$. Since any of the six tickets might end up being the only one to show a $7$, you might try multiplying your count by $7$ to get $7^6$. However, you would then be ...

0

Suppose we seek to evaluate $$S_m(n) = \sum_{p=0}^n {n\choose p} (-1)^p \frac{1}{m+p+1}$$ where $m$ is an integer not equal to $-1,-2,\ldots, -n-1$ where the fraction is undefined. Observe that with $$f(z) = \frac{(-1)^n n!}{z+m+1} \prod_{q=0}^n \frac{1}{z-q}$$ this is $$S_m(n) = \sum_{p=0}^n \mathrm{Res}_{z=p} f(z).$$ the reason being that ...

0

Addressing your Q1, the difference between the answer you gave and the answer that the book gives is that your solution assumes that a specific selection is 7. That is, $\frac{7^5}{10^6}$ is the probability that a fixed ticket is 7 and the other five take values from 1 to 7 while the books solution just assumes that at least one of the tickets is 7. Q2 The ...

4

HINT: For (a), you have $$\binom{k}2+k(n-k)+\binom{n-k}2=\frac{k!}{2!(k-2)!}+k(n-k)+\frac{(n-k)!}{2!(n-k-2)!}\;.$$ Start by doing a lot of cancellation: \begin{align*} \frac{n!}{(n-2)!}&=n(n-1)\\ \frac{k!}{(k-2)!}&=k(k-1)\;,\text{ and }\\ \frac{(n-k)!}{(n-k-2)!}&=(n-k)(n-k-1)\;. \end{align*} Once you’ve done that, the algebra becomes very ...

1

Part (b) is also straightforward. The LHS measures how many ways there are to choose 2 balls from n. This is the same as counting the ways to choose 2 from the first k, or 2 from the last n-k, or one in the first k and one in the last n-k.

2

Part (a) is straightforward: \begin{align*} \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2} &= \frac{k!}{(k-2)!2!} + k(n-k) + \frac{(n-k)!}{2!(n-k-2)!} \\ &= \frac{k(k-1)}{2} + k(n-k) + \frac{(n-k)(n-k-1)}{2} \\ &= \frac{k^2-k+2nk-2k^2 + n^2 - 2nk - n + k^2 + k}{2} \\ &= \frac{n(n-1)}{2} = \dbinom{n}{2}. \end{align*}

0

Community wiki answer based on the comments so that the question an be marked as answered: For each colour, consider the set of buckets in which it is represented. We want to pick $K$ different representative buckets for the $K$ different colours. The assumptions of Hall's theorem are fulfilled: Since every bucket contains at most $N$ counters, any $j$ ...

2

Your questions have mostly already been answered in the comments; I compiled the answers from the various sources provided and added a computer search. Your system $$\binom{n}{k+1}=2\binom{n}{k}$$ $$\binom{n}{k+2}=3\binom{n}{k}$$ is a special case of an arithmetic progression of three consecutive binomial coefficients. In the answer to Generalized Case: ...

1

It is not correct. Note that there are $\binom{3}{1}$ ways from $(3,2)$ to $(4,4)$.

1

A proof goes by using generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and take your recurrence with initial values $a_0$ through $a_{k - 1}$. Shift indices to get: \begin{align} a_{n + k} = c_1 a_{n + k - 1} + \dotsb + c_k a_n \end{align} Multiply by $z^n$, sum over $n \ge 0$ and get: \begin{align} \sum_{n \ge 0} a_{n + k} z^n = c_1 ... 2 I'm getting a different answer forP(14S+4D)$and$P(15S+2D+1T)$. I'll explain my reasoning for the first one. The second is similar.$P(14S+4D)$: The idea is we have to count the ways to choose the days for$14S$and$4D$, then, for each such choice, count the ways we can arrange the$22people to have those chosen days. One way to do this is a ... 2 For two digits numbers the answer would be $$\binom{2}{1}*10^1 - \binom{2}{1}*10^0 = 20 - 1 = 19$$ For three digits numbers the answer would be $$\binom{3}{1}*10^2 - \binom{3}{2}*10^1 + \binom{3}{3}*10^0 = 300 - 30 +1 = 271$$ ... For six digits numbers the answer would be \eqalign{ \binom{6}{1}*10^5 - \binom{6}{2}*10^4 + \binom{6}{3}*10^3 ... 0 Community wiki answer so the question can be marked as answered: As noted in a comment, this is right. 0 Community wiki answer so the question can be marked as answered: The cross-posted question at MO has been answered; the result is (a+b−2)\binom{a+b−2}{a−1}\;. 0 Community wiki answer so the question can be marked as answered: As noted in the comments, your calculations are correct. Ideally, you should have mentioned that the students choose their majors independently uniformly at random. 0 Community wiki answer so the question can be marked as answered: As has been pointed out in comments, this calculation (as corrected) is correct. 1 You can only obtain a probability as the quotient of the number of favourable outcomes over the total number of outcomes if all outcomes are equiprobable. The way you're trying to count, there's no reason to expect the outcomes to be equiprobable, as they involve different numbers of draws. The equiprobable outcomes that you'd need in order to do it this ... -1 There are many such tetrahedra. First note that the third follows from the first by the standard formula for the area (well, almost, since there is a factor \dfrac 12 but this cancels if enough coordinates are even). One can then consider terahedra with vertices of the form (0,0,0), (m,0,0), (0,n,0) and (0,0,p) for suitable integers m, n and ... -2 I think the question should be - Find the probability that a total of n "red" balls are withdrawn. Then let p = r/(r+b) and q = 1 - p = b/(r+b), and let X be the number of red ball. So X has a binomial distribution. Thus \begin{align} \ P(X=n)= \binom{r+b}{n} p^{n}q^{r+b-n} \\ =\frac{(r+b)!}{n!(r+b-n)!} p^{n}q^{r+b-n} \end{align} 0 Hmm, what I think that I see is the following. If we collect the \frac 1{n!} into the expression containing the Stirling numbers, then, if k is infinite we get a well known matrix (I adapted your indices n,m to "r" for row and "c" for column; S_{2:r,c} are the Stirlingnumbers second kind of row and column) S = \left\{ { S_{2:r,c} \cdot \frac ... 1 We just need to show that for every subset\{i_1,i_2,\cdots,i_m\}\subset\{1,2,\cdots,n\}$we can construct a probability space$\Omega$such that all the independent conditions satisfies except $$\mathrm{Pr}[A_{i_1}\cap A_{i_2}\cdots\cap A_{i_m}]=\mathrm{Pr}[A_{i_1}]\times\mathrm{Pr}[A_{i_2}]\cdots\times\mathrm{Pr}[A_{i_m}].\qquad (1)$$ Denote$I=[0,1], ...

1

You need to first choose which k dishes will go to the top level, in ${n+k\choose k}$ ways. The balance n dishes automatically get assigned to the bottom level. You then need to apply the permutation formula for arrangements in a circle (which has already been quoted by you, to both levels, thus $$(k-1)!(n-1)!{n+k\choose k}$$

0

The annealing approach was a bit over my head, but I was able to come up with a solution that seems to work well for the numbers I'm working with and that may be within reach of others who find this post. The key was to use a random shuffle of the list rather than trying to walk through the permutations systematically, which becomes impossible for numbers ...

2

You can't have $2$ for the second digit in your $4$ digit number. The highest number you could form, provided you had the digits required is 1199. Any $4$ digits number with 2 for second digit is more than that upper limit. So, your choice(in 4 digit number) for: first digit: $1$ (you can have $1$ only) second digit: $1$ (you can have $0$ only) third ...

1

The province can use up to $10^5$ license plates. To see that this many license plates can be used, fix some residue $r$ modulo $10$ and consider all license plates whose digit sum has remainder $r$ modulo $10$. Any two of them differ in at least two digits, since changing one digit changes the remainder. To see that not more license plates than this can ...

1

In short we have to calculate the number of integer solutions of the Diophantine equation $$1000x+100y+10z+w=2010$$ with the conditions $0\leq x,y,z,w \leq 99$. We have $0\leq x\leq 2$ which gives the three equations $$(1)……100y+10z+w=2010$$ $$(2)……100y+10z+w=1010$$ $$(3)……100y+10z+w=10$$ The equation (3) gives just two solutions $(2,0,1,0)$ and ...

7

As with many problems of this general sort, the trick is finding the right invariant. Assign a weight of $2^{-n}$ to each bead sitting on a grid point that lies on the line $x+y=n$; the initial weight of the configuration is $4\cdot2^0=4$, and it’s easily checked that each move preserves the total weight. After $n$ moves each bead lies on one of the lines ...

1

This is a comment, not a solution, but recall the identity $(*)$ $\binom{n}{m} {m \choose k}={n \choose k}{n-k \choose m-k}$ and letting $n=8, m=5$ we can see that Brian's counterexample to your original claim is of this form as $k=3$ and since ${5 \choose 2}={5 \choose 3}$, $k=2$ is equivalent, thus we may interchange the products on either resulting $rhs$ ...

1

Hint: take $X_1,\ldots,X_{n-1}$ as independent random variables with a Bernoulli distribution with $p=\frac{1}{2}$ and define $X_n$ as: $$X_n = X_1+\ldots +X_{n-1}\pmod{2}.$$

4

The generating function for these representations is $$\frac{x^{100\cdot1000}-1}{x^{1000}-1}\cdot\frac{x^{100\cdot100}-1}{x^{100}-1}\cdot\frac{x^{100\cdot10}-1}{x^{10}-1}\cdot\frac{x^{100}-1}{x-1}=\frac{x^{100000}-1}{x^{10}-1}\cdot\frac{x^{10000}-1}{x-1}\;,$$ which is also the generating function for representations of the form $a_1\cdot10+a_0$ with ...

0

Here's a solution that's not particularly elegant but gives the right answer (checked by brute force). First express each coefficient uniquely as $b_i\cdot 10 + a_i$. $2010 = b_3 \cdot 10^4 + a_3 \cdot 10^3 + b_2 \cdot 10^3 + a_2 \cdot 10^2 + b_1 \cdot 10^2 + a_1 \cdot 10 + b_0 \cdot 10 + a_0$. We must have $b_3 = 0, a_0 = 0$, so $201 = (a_3 + b_2) \cdot ... 2 It's easier to start from the other end. We observe first that$a_0$can be any multiple of$10$from$0$through$90$. There are, of course, ten such values. Then$a_1$can be any one- or two-digit value equivalent to$11-(a_0/10) \bmod 10$. Again, there are ten such values. The choices of$a_2$are much more limited by the fact that the target sum is ... 4 This is essentially Problem #7 from Tournament of the Towns, Fall 2011, Junior A-Level and Problem #2 from USAMO 2012. Tournament of the Towns, Fall 2011, Junior A-Level, Problem #7. Each vertex of a regular 45-gon is red, yellow or green, and there are 15 vertices of each colour. Prove that we can choose three vertices of each color so that the three ... 6 I don't have any good ideas to answer the follow up question, but it's worth noting there are infinitely many solutions to that equation outside of the two possibilities mentioned in the original question. For example, if$m=\binom{n}{k}$for some$1<k<n-1$, then$\binom{n}{k}\binom{m}{0}=m=\binom{n}{0}\binom{m}{1}$. EDIT: Okay, so the OP wants ... 12 $$\binom51\binom83=280=\binom52\binom82$$ 0 $$\frac{11!}{4!4!2!} -1$$ since$\frac{11!}{4!4!2!}$is the total number of permutations of the letters from the word MISSISSIPPI. Since, the word itself is not a rearrangement of itself, that's why a "-1" 0 Assume$(X,Y,Z)$be a partition of$S$. Let$A=X\cup Y$,$B=Y\cup Z$It can be checked that except the partition$(\phi,S,\phi)$, all other partitions satisfy all the conditions. The answer should be obvious now. 1 Hint: Note that the last two requirements together imply that$A,B$are not both equal to$S,$so by the first requirement at least one of them must be a proper subset of$S.$Since order doesn't matter, then we may assume without loss of generality that$A\subsetneq S.$How many such$A$are there? Given such an$A,$what must be the relationship between ... 2 Suppose that we have$n$groups, of sizes$a_1$to$a_n$. Except when$n$is smallish, the following formula for the number$N$of ways to choose a pair of people from different groups is more efficient: $$N=\frac{1}{2}\left((a_1+\cdots +a_n)^2 -(a_1^2+\cdots +a_n^2)\right).$$ To see that the formula does the job, expand$(a_1+\cdots +a_n)^2$. 1 Number of even degree vertices could be anything but the number of odd degree vertices must be an even number. 3 The standard approach is to arrange the$10$BS students in$10!$ways amongst themselves and then insert the$7$MS students in the 11 gaps before after and between them in$\binom {11}{7}$ways and finally multiply by the number of arrangements of the MS stidents amongst themselves in the chosen gaps. multiply the results. 3 Number of ways to select from 10 non-identical objects: 0 - 10 objects:$2^{10},\;\text {which can also be derived as}\;{10\choose 0} + {10\choose 1} + ...{10\choose 10}$1 - 10 objects:$2^{10} - {10\choose 0} = 2^{10} - 1$2 - 10 objects:$2^{10} - 1 - {10\choose 1} = 2^{10} - 11\$

3

At SageMath I got an answer in seconds: k=var('k') x=sum(binomial(6700,k)*binomial(3300,1000-k)/binomial(10000,1000) for k in range(570,771)) print(x) print(float(x)) ...

4

Typing in the following input into WolframAlpha: Sum[Binomial[6700,k]Binomial[3300,1000-k]/Binomial[10000,1000],{k,570,770}] yields an exact result followed by the approximate decimal value, which to 50 digits is $$0.99999999999855767906391784086205133574169750988724.$$ The same input in Mathematica will yield the same result as above, although you ...

Top 50 recent answers are included