Tag Info

New answers tagged

0

${17\choose2}-\left({11\choose2}+{9\choose2}-{3\choose2}\right)$


0

ad C) If the random variables are independent, then $Var \left (\sum_{i=1}^n X_i \right)=Var(X_1)+Var(X_1)+Var(X_1)+\ldots + Var(X_n)$ Here it is $Var(X_1)=Var(X_1)=Var(X_3)=Var(X_3)=Var(X_4) \Rightarrow Var \left (\sum_{i=1}^4 X_i \right) =4\cdot \frac{35}{12}$ And $E(\sum_{i=1}^n X_i)=4\cdot 3.5$ The formula for approximation is $P(S_n\leq S)=\Phi ...


0

Four sizes times four blends = 16 choices before syrups. There is one way to choose without syrups. Multiply this by the 16 combos found above. There are 5 ways to choose one syrup. Multiply this by the 16 combos above. There are 5 times 4 ways to pick 2 syrups. Multiply this by the 16 combos again. Repeat. Add together. The pattern should be clear.


0

First off you have $4 \times 4= 16$ drinks without syrups. Now when you have to choose your syrups, for each of the five syrups you can either say yes or no, which means $2^5=32$ different syrup possibilities. So you have $16 \times 32=512$ different drinks.


0

$4 \text{ (sizes)} \times 4 \text{ (varieties)} \times 2^5 \text{ (with or without each syrup)} = 512$


0

Extend the triangle down one more row. Then extend the sides of the parallelogram until they hit that row, and mark those spots they hit. The bijection should now be clear.


0

Answering A: i) $C(X=4)=\dbinom{4}{4}=1$: $(1,1,1,1)$ ii) $C(X=5)=\dbinom{4}{3}=4$: $(1,1,1,2)$ $(1,1,2,1)$ $(1,2,1,1)$ $(2,1,1,1)$ iii) $C(X=6)=\dbinom{4}{3}+\dbinom{4}{2}=10$: $(1,1,1,3)$ $(1,1,3,1)$ $(1,3,1,1)$ $(3,1,1,1)$ $(1,1,2,2)$ $(1,2,1,2)$ $(1,2,2,1)$ $(2,1,1,2)$ $(2,1,2,1)$ $(2,2,1,1)$ Answering B: The total number of combinations ...


2

In $$(t^2+\dots+t^5)(t^3+\dots+t^6)(t^4+\dots+t^7)$$ you can notice that is $$t^2(1+t+t^2+t^3)\times t^3(1+t+t^2+t^3)\times t^4(1+t+t^2+t^3)=t^9(1+t+t^2+t^3)^3$$ which simplifies a lot the problem as Gerry Myerson answered. Moreover, $$1+t+t^2+t^3=(t+1)(t^2+1)$$ can help.


1

It's also the coefficient of $t^8$ in $(1+t+t^2+t^3)^3$. $$(1+t+t^2+t^3)^3=(1-t^4)^3(1-t)^{-3}=(1-3t^4+3t^8+\dots)(1+3t+6t^2+10t^3+\dots)$$ where the coefficient of $t^r$ in the last bracket is $t+2\choose2$. It shouldn't be too hard for you to pick out the coefficient of $t^8$ now.


0

well, the simplest way to answer it is to see tre problem as «we have a 9-chunk string made of six "10" and three "0"», and indeed you come out with $ 9\choose{3}$. In your other formulation, I think you forgot that the "remaining" zeros are indistinguishable from the one you attached to to 1.


0

I had to write an ugly recursive algorithm in C to calculate the exact median for this game. Please find the first 30 exact median values in the graph at page 62 philpapers.org/archive/ERGTEO.pdf


1

Start off with one pile on the left containing n-m red balls and m green balls, and another pile to on the right with exactly k blue balls. Count the number of ways that the left pile can have its red and green balls arranged (ie n chose m) multiplied by the number of ways (ie 1) that the right pile can have its red balls arranged. Then move 1 green ball ...


0

I don't believe there is a simple closed form. See here for some more information about the sequence. If we let $a_n$ be given by your formula, we have the recurrence $a_n=a_{n-1}+(n-1)a_{n-2}$. There is also the generating function: $$\sum_{n=0}^\infty a_n \frac{x^n}{n!} = e^{x + x^2/2}.$$


0

Let r.v. $S$ be the sum of $n$ dice, each with $m$ faces $1,...,m.$ The generating function for $S$ is $$\sum_{j=1}^{nm} P(S=j)x^j = \left[\frac xm+\frac {x^2}m+...+\frac{x^m}m \right]^n $$ $$ =\frac{x^n}{m^n}(1-x^m)^n(1-x)^{-n} $$ Binomial expansions: $$(1-x^m)^n=\sum_{k=0}^{nm}{n \choose k}(-1)^kx^{km}$$ $$ (1-x)^{-n}=\sum_{i=0}^{\infty} {-n \choose ...


0

It might be helpful to think of a coordinate system to stay on top of things. 2x3 grid: 02 12 22 32 01 11 21 31 00 10 20 30 The possible paths are: 10 20 30 31 32 10 20 21 31 32 10 20 21 22 32 10 11 21 31 32 10 11 21 22 32 10 11 12 22 32 01 11 21 31 32 01 11 21 22 32 01 11 12 22 32 01 02 12 22 32 10 paths in total.


1

Your sum is correct, and moreover in general: $$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n.$$ So another way of realising your sum is $2^{15}$. A combintorical proof that the size of the power set of an $n$ element set $A$ is $2^n$ (which can also be used to prove the above identity) is as follows. There is a bijection ...


1

This is equivalent to the recurrence stated in the Wikipedia article: $c(n+1,k)=nc(n,k)+c(n,k-1)$. The Combinatorial proof of this recurrence on Wikipedia seems fairly intuitive. So the fact that these two are equal just requires the case $n=1$.


0

Here's the first part to get you started. Fix $i \in \{1, \ldots, n\}$. To choose a subset of size $k$ with largest element $i$, we choose $i$, and then we must choose the remaining $k-1$ elements from $\{1, 2, \ldots, i-1\}$. (If we choose an element in the range $\{i+1, i+2, \ldots, n\}$, then $i$ won't be the largest element!) Can you see where the ...


0

Consider a sequence of three letters, and suppose the first and second letters are stick letters. Then we have 15 options for the first stick letter, and 14 options for the second stick letter (since the stick letters have to be different). We also have 11 options for the last round letter. So, there are $15\cdot14\cdot11$ different arrangements. But, the ...


0

The combinatorial element is not strong in these two problems. Imagine that the $35$ "gems" have engraved ID numbers on them, to make them distinct. Way 1: We want the probability that $2$ fakes were drawn before the second real. This could happen with the following patterns of drawing: (i) RFFR, (ii) FRFR, and (iii) FFRR. We will find the probability of ...


0

Here is the algorithm I believe is correct: Assume M is larger than N for simplicity. We want to make the squares as large as possible, since total area is given (M times N), the larger the area of any particular square, less will be the number of squares required to cover the whole sheet. Since you can't make any square larger than $N^2$, we begin by ...


1

The article you linked to deals with the asymmetric travelling salesman problem. The authors have a subsequent paper which deals with the more usual symmetric TSP: Gutin and Yeo, "The Greedy Algorithm for the Symmetric TSP" (2007). An explicit construction of a graph on which "the greedy algorithm produces the unique worst tour" is given in the proof of ...


5

Note that $$(p+q)^n=\sum_k{n\choose k}p^{n-k}q^k,$$ and $$(p-q)^n=\sum_k(-1)^k{n\choose k}p^{n-k}q^k,$$ hence $$1-(p-q)^n=(p+q)^n-(p-q)^n=2\sum_{k\ \text{odd}}\cdots$$


3

In fact, all the diagonal entries need not be zero. There can be one non-zero entry on the diagonal and the matrix will still be invertible. That is, if $A(i,j) =1, \forall i\ne j$ and $A(1,1) = 1$, $A(i,i) = 0, \forall i\ne 1$, we will have $A$ invertible. So, that gives a lower bound on #1's: $n^2-n+1$. To prove that $A$ is invertible: Consider writing ...


-1

You want a formula like this for fair and different type of dice $$f(x)=\prod_{j}\left(\sum_{i} b\cdot x^{a(j)_i}\right)^{n_j}$$ Where j is a reference to the number of different type of dice and a(j) is a list or function for the different numbers on the sides, b is the frequency for each side (by example a 2 if you have 2 times the same number) and $n_j$ ...


1

It is as easy as P.I.E.. Use the Principle of Inclusion and Exclusion to choose couples to seat together, and count ways to arrange the party in a row treating those couples as a unit times ways to arrange each such unit. Divide by the total ways to arrange 6 persons. $$\frac{{3\choose 1}\cdot 5!\cdot 2!-{3\choose 2}\cdot 4!\cdot 2!^2+{3\choose 3}\cdot ...


2

The change of variable $r\rightarrow m-r$ gives $$ \sum_r (m-r)^3 \begin{Bmatrix} n\\ r \end{Bmatrix} (m)_r $$ Here, the notation $(m)_r$ is for the product $m(m-1)\cdots (m-r+1)$. We have $$(m-r)(m)_r = (m)_{r+1} = m (m-1)_r. $$ Thus $$(m-r)^2 (m)_r = (m-r-1+1)(m-r) (m)_r $$ $$= (m-r-1+1) (m)_{r+1} = (m)_{r+2} + (m)_{r+1}$$ Then $$(m-r)^3 (m)_r = ...


1

$\textbf{Hint:}$ Let $A_i$ be the ways to seat the people so that couple $i$ sits together, for $1\le i\le3$. Then the probability is given by $\displaystyle\frac{\left|A_1\cup A_2\cup A_3\right|}{6!}$, and $\left|A_1\cup A_2\cup A_3\right|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3|$. (Notice that, for example, ...


0

Hint: In order to compute the expectation, use linearity of expectation. In order to compute the variance, compute instead the second moment $\mathbb{E}[X^2]$, where $X=X_1+\cdots+X_{n-k+1}$, and $X_i$ is the event that the $i$th window is error free. The idea here is to use linearity of expectation again: $$\mathbb{E}[X^2] = \sum_i \mathbb{E}[X_i^2] + ...


1

One possible way is this term: $(x+x^2+x^3+x^4...+x^m)^n$ m: number of sides n: number of dices Expand the term above and collect all the summands with $x^k$. The number of permutations with the sum k is the coefficient $c_k$, of $c_k \cdot x^k$ Example: m=3 n=2 $(x+x^2+x^3)^2=x^2+2 x^3+\color{blue}{3 x^4}+2 x^5+x^6$ There are 3 permutations with ...


0

The most obvious flaw in your reasoning is that it overcounts arrangements for which more than one couple sits together. For simplicity of notation, let the couples be $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, where the females are the odd values and the males are the even values. Then the arrangement $(1,2,3,4,5,6)$ is counted numerous times depending on whether ...


1

Since $$\sum_{j=0}^{v}\binom{n+j}{j+1}=-1+\binom{n+1+v}{n}$$ we have: ...


0

The formula in the last answer (of Yuval Filmus) seems to be wrong: for m=4,n=9,S=6 one gets a nonzero result while it's impossible to have a sum of 6 with 9 dices! The wanted formula i guess is the one corresponding to the coefficient "c" at http://mathworld.wolfram.com/Dice.html


19

This is an interesting exercise in partial summation. For first, we have: $$\begin{eqnarray*}\sum_{j=1}^{n}H_j &=& n H_n-\sum_{j=1}^{n-1} \frac{j}{j+1} = n H_n - (n-1)+\sum_{j=1}^{n-1}\frac{1}{j+1}\\&=& n H_n-n+1+(H_n-1) = (n+1)H_n-n\tag{1}\end{eqnarray*} $$ hence: $$\begin{eqnarray*}\color{red}{\sum_{j=1}^n H_j^2} &=& ...


0

You may look at [Poset Topology] and the related lecture notes by Michelle L. Wachs.


2

The best way is to count the total number that begin with a or c, as you did, and subtract the number of "bad" strings, the ones that have no b. These bad strings are easy to count, using the same kind of reasoning as the one you used to get $\frac{4^8}{2}$ for the total number of strings that begin with a or c. I would count in the following marginally ...


1

I would agree with genisage that the counting proof is better here! But if you're really in search of the binomial theorem proof, here is a method. Consider $(1 + 1 + x)^n$. What is the coefficient on the $x^k$? Well, if we look at this as $(2 + x)^n$, the binomial theorem says the $k$th term is ${n \choose k} 2^{n - k} x^k$, and hence the coefficient ...


0

Here is the idea. Suppose without loss of generality that $N = \{1,\ldots,n\}$, and let $p_1,\ldots,p_n \in \{1,\ldots,k\}$ be a partition of $N$ into non-empty parts. We assume that different parts appear in increasing order, that is, the first part appearing is number $1$, the second part appearing is number $2$, and so on (so, for example, a list starting ...


0

There are $52!$ to sort the deck of cards. The sorted deck is divided into 4 equal-sized stacks (the players' 'hands'). However, each stack can be sorted in $13!$ ways, each of which is considered equivalent. So there are in fact only $\dfrac{52!}{13!^4}$ distinct ways to deal the cards. Alternatively, you can deal cards from the deck to player 1 in ...


1

Once we know which $13$ cards the first player gets, there are not $52$ cards remaining that could have been dealt to the second player. There are only $39.$ After we have looked at the cards dealt to the second player, only $26$ remain that might be in the third player's hand. And once we have looked at those, we know exactly which cards the fourth player ...


0

It will be something like: You can choose $13$ cards out of $52$ cards for one person, then $13$ for other from the remaining $39$ and so on: $$\binom{52}{13}\binom{39}{13}\binom{26}{13}\binom{13}{13}=\frac{52}{(13!)^4}\approx5.36\times10^{28}$$ Your assumption assumes that there are always $52$ cards remaining: $$\binom{51}{13}^4$$


1

The answer is not $\binom{52}{13}^4$ because the various people do not get cards from a fresh deck: If South has the Ace of $\spadesuit$, then West cannot have it. Your formula would be correct if after dealing $13$ cards to South, we threw away the rest of the deck, and got a fresh deck for the deal to West, and continued in this way for the other two ...


0

A common notation for the collection of all size-$k$ subsets of $S$ is given by the symbol $S_k$.


0

We can first choose the 2 letters, which can be done in $\binom{4}{2}=6$ ways. There are $2\cdot2\cdot2\cdot2=16$ words that can be made with these two letters, but we must subtract the two words that only use one letter, so this gives $16-2=14$ possible words; and therefore there are $6\cdot14=84$ possibilities.


1

I have absolutely no clue how to show that using the binomial theorem. But there's really only one good way to show things are equal in combinatorics, and that's to phrase the same question in two different ways. For this one, I thought of picking a soccer team. Let's say they're allowed to bring as many people as they want out of $n$ applicants, but only ...


0

$\textbf{1)}$ If we choose the marbles one at a time, we get $\displaystyle\frac{x}{x+y}\frac{x-1}{x+y-1}\frac{x-2}{x+y-2}\cdots\frac{1}{y+1}=\frac{x!y!}{(x+y)!}$. We could also think of this as drawing $x$ marbles from the bag all at once. There are $\binom{x+y}{x}$ ways to do this, and only one way which will give all blue marbles; so the probability is ...


1

The key seems to be in the sentence (from the linked-to solution) that precedes what you quoted: For the purposes of solving this problem we treat obtaining a 2 or 3 as an equivalent result. In other words, they are reducing things to the coin-tossing model.


0

In order for a statement about the arbitrary values $x$ and $y$ to be true, it must be true for all possible values of $x$ and $y$ within the bounds allowed by the statement. In your case, we can assume $x \ge 0$ and $y \ge 0,$ since we don't believe there could be $-1$ blue marbles in the bag. But aside from that, $x$ could be a small positive integer ...


1

There are $\binom{20}{9}$ possibilities if there are no restrictions. Under the restriction that no math class is chosen there are $\binom{15}{9}$ possibilities. Consequently there are $\binom{20}{9}-\binom{15}{9}$ possibilities under the restriction that at least one math class is chosen.



Top 50 recent answers are included