# Tag Info

0

Answer The answer is the coefficient of $y^S$ in the polynomial $A(y)=\prod_{i=1}^{n}{(\sum_{j=0}^{L_i}{y^j})}$. Reasoning Define $f(S)$ to be the number of integer solutions to your problem that sum to $S$ and meet the other constraints. Then the ordinary generating function for $f(S)$ is: $$A(y)=\sum_{j=0}^{\infty}{f(j)y^j}$$ Define $g_i(S)$ to be the ...

3

For each topping you can decide to use it or not to use it. So for each topping you have $2$ ways. Thus in total you have $2^{12}$ ways.

3

For each topping you can choose to include it or not include it. This results in $2^{12}=4096$ different kinds of hot dogs.

1

Color all the points in $A$ red and color all the rest of the points blue. By Van der Waerden's Theorem, if $N = W(2, n)$, then one of these colors must have an arithmetic progression of length $n$.

0

Your guess is not quite correct after the first two terms. It should be $^5P_5$ + $^5P_4$ + $^5P_3$ + $^5P2$ + $^5P1$ +$^5P_0$ Generalizing for n terms, $\sum _0^n {^n P_k}$, or if you so prefer, $\sum_0^n{n\choose k}\cdot k!$

5

The number of permutations of every subset of a set of size $n$ is $\lfloor n!e\rfloor$. This is because $$\sum_{k=0}^n\underbrace{\binom{n}{k}}_{\substack{\text{number of}\\\text{subsets of}\\\text{size k}}}\underbrace{k!\vphantom{\binom{n}{k}}}_{\substack{\text{number of}\\\text{permutations}\\\text{on a subset}\\\text{of size k}}} ... 0 No, you have 5! permutations of 5 elements, but for 3 elements there are 5 \cdot 4 \cdot 3=\frac {5!}{(5-2)!} permutations. You have five choices for the first one, four choices (because you have used one) for the second and three for the third. Another way to look at it is that you have 5 \choose 3 ways to select the three elements and then 3! ... 0 This is called the number of partitions of a set, or Bell numbers. 1 Yes, the correct answer is 400. Here is one way to view the problem which may help demonstrate why this is the true. Imagine a 20 \times 20 grid where the each column is labeled from 1 to 20 and each row is (separately) labeled from 1 to 20. Picking the first number from 1-20 amounts to picking a column from the grid. Likewise, picking a second number ... 0 True, provided (a,b) is different from (b,a) that is, order matters. Otherwise, if order does not matter ie (a,b) is the same as (b,a) then from the square that you used to calculate your answer, you have to remove nearly half of it and you are left with 210 different combinations. 0 Another way to realize this is to let z mean "zero", o mean "one" and to use the binomial theorem:$$(z+o)^n = \sum_{k=0}^{n} \left(\begin{array}{c}n\\k\end{array}\right)z^ko^{n-k} = \sum_{k=0}^{n}\frac{n!}{k!(n-k)!} z^ko^{n-k}$$the exponents arithmetically will become the numbers of z and o picked and the coefficients will be the ... 1 Try to see it for a little r like 3. In this case you have (a_1,a_2,a_3)=(a_1,a_3)(a_1,a_2). A permutation of r elements in general is a bijection of the set \{1,...,r\} to itself. In our particular the permutation (a_1,a_2,a_3) is a function such that a_i\longmapsto a_{i+1} and a_3\longmapsto a_1. So$$ a_1\longmapsto a_2\\ a_2\longmapsto ...

1

Sequence is Cauchy Bernoulli's Inequality shows that the sequence is monotonically increasing. \begin{align} \left.\left(1+\frac p{n+1}\right)^{n+1}\middle/\left(1+\frac pn\right)^n\right. &=\frac{n+p}{n}\left(\frac{n+p+1}{n+1}\frac{n}{n+p}\right)^{n+1}\\ &=\frac{n+p}{n}\left(1-\frac{p}{(n+1)(n+p)}\right)^{n+1}\\ ... 1 This shows the estimate needed in Winther's answer. It is too complicated to be a comment, though that is what it really it. Define \ln(1+x) =\int_1^{1+x} \frac{dt}{t} . Since, for 1 \le t \le 1+x \frac{1}{1+x} \le \frac{1}{t} \le 1, \frac{x}{1+x} \le \ln(1+x) =\int_1^{1+x} \frac{dt}{t} \le x , so that \frac{x}{1+x}-x \le \ln(1+x)-x \le 0  or, ... 1 (a_1, a_2, \dots, a_r) = (a_1, a_r)(a_1, a_{r-1})\dots(a_1, a_3)(a_1, a_2) $$2 Note that$$ (a_1\,a_2\,\ldots\, a_n)(a_n\,a_{n+1})=(a_1\,a_2\,\ldots\,a_n\,a_{n+1})$$0 Probability: How likely something can happen. Permutation: Def: The number of possibilities for choosing an ordered set of r objects (a permutation) from a total of n objects. Definition: _nP_r(n,r) = n! / (n-r)! Assume there are three persons namely A, B and C in the park. But there is only two seats available for them. Then possible ways of ... 0 Proving directly that a_{n} = (1 + (p/n))^{n} is a Cauchy sequence seems difficult especially when one wants to use only algebraical manipulations. On the other hand by Binomial theorem it is easy to see that a_{n} is increasing if p > 0. We will consider this simplified case when p > 0. On the contrary assume that a_{n} is not Cauchy. Then ... 0 Since you wanted a graph-theoretic solution, I will provide one. Assume the board is n-by-n and at most n−1 squares are removed. Let R be the set of rows and C be the set of columns. The edges of the bipartite graph G with bipartite sets R and C are in the form \{r,c\}, where r\in R and c\in C such that the square corresponding to the ... 1 Let we set:$$q_m(x)=(1-x)^m\sum_{k=0}^{m}\binom{2m+1}{2k+1}\left(\frac{x}{x-1}\right)^k .$$Since:$$\sum_{k=0}^{m}\binom{2m+1}{2k+1}w^{2k+1} = \frac{1}{2}\left(\left(1+w\right)^{2m+1}-\left(1-w\right)^{2m+1}\right)$$we have:$$ q_m(x)=(1-x)^m ...

0

Not quite—the number of ways to divide $15$ distinct objects into three distinct groups is $$\binom{15}{5, 5, 5} = \binom{15}{10} \binom{10}{5} = 90810720$$

1

Here is a sketch of proving that $f(n)$ is Cauchy. Whenever we want to bound $|f(a)-f(b)|$ then the mean value theorem is usually our best friend. The mean value theorem says that for a differentiable function $f$ we have $$|f(n) - f(m)| = |f'(c)||n-m| \text{ for some } c\in(n,m)$$ For this case $f(x) = \left(1+\frac{a}{x}\right)^x$. We first need to ...

1

One approach using L'Hospital to show $$\lim\limits_{x\to\infty}\left(1+\frac{a}{x}\right)^x=\exp(a).$$ This will prove that the sequence is a cauchy sequence. Let $$F(x)=x\ln\left(1+\frac{a}{x}\right)=\frac{\ln\left(1+\frac{a}{x}\right)}{\frac{1}{x}}.$$ We have $\lim\limits_{x\to\infty}\ln\left(1+\frac{a}{x}\right)=0=\lim\limits_{x\to\infty}\frac{1}{x}$, ...

2

There is no general formula for an $m\times n$ grid, but there is a recursive approach that allows to compute the number $C(m,n)$ of different ways to cover the grid with simple cycles for any $m,n$. First note that once you have covered the grid, it suffices to know the horizontal lines, in order to determine all the cycles. So you can assign to each ...

0

This is my attempt. Since the block is of size $c$, there is only one number which is divisible by $c$. Since $b<c$, there is "at least one" number (can be 1 or more) which is divisible by $b$. Again $a<b$, So for every block $b$ you choose (by dividing the $c$ block into many partitions so that each partition contains exactly one number divisible by ...

1

\begin{align}\prod_{i=1}^{k-1}{\left (1-\frac{i}{n+1} \right )} &= \prod_{i=1}^{k-1}{\left (1-\frac{i}{n} + \frac{i}{n^2} \right )} + O \left (\frac1{n^3} \right )\\ &= \prod_{i=1}^{k-1}{\left (1-\frac{i}{n} \right )} + \sum_{j=1}^{k-1}\frac{j}{n^2} \prod_{i=1,i \ne j}^{k-1}{\left (1-\frac{i}{n} \right )}+ O \left (\frac1{n^3} \right )\\ ... 1 We have\prod_{i=1}^{k-1}\,\left(1-\frac{i}{n+1}\right)-\prod_{i=1}^{k-1}\,\left(1-\frac{i}{n}\right)=\left(\prod_{i=1}^{k-2}\,\left(1-\frac{i}{n}\right)\right)\left(\left(1+\frac{1}{n}\right)^{-(k-1)}-\left(1-\frac{k-1}{n}\right)\right)\,.$$For large n\in\mathbb{N}, \prod_{i=1}^{k-2}\,\left(1-\frac{i}{n}\right)=1+O\left(\frac{1}{n}\right) and ... 1 Notice that a_0=q(0), a_1=q'(0), a_2={1\over2}q''(0) and so on. It should be easy to evaluate the a_k this way. 0 So really my question is: How do you know we have to treat the 9 people as spaces, rather than the k spaces that must be selected? In other words, how do you know that n=9 instead of n=3, and how do you know that k=3 instead of k=9. I get these two mixed up. Here's the answer of @drhab. Think of the persons as spaces. There are 9 of them and at ... 0 I chose a fitness function f such that f(students) = average(happiness(students)) + minimum(happiness(students)) 1 Ok. Unless I made a mistake the good news are that this always holds. The bad news is that it holds even without the assumption that Q is not a permutation. But we can also make the observation that if the restriction of Q is not injective then the total imbalance increases. See below what exactly I mean by this. Observe the following: the numbers ... 0 It's simply \binom{m+n}m=\binom{m+n}n: once you choose n positions for the first word, the entire meshed string is completely determined. 0 A and B sitting next to each other on same side gives us 2(6!), A and B sitting next to each other on different side gives us another 2(6!) therefore total no of arrangements where A and B not sitting next to each other =2(7!)-2(6!)-2(6!) =7200 1 If the side matters, then one side can choose 5 heroes from the entire pool. After that, the other then chooses 5 heroes from the remaining pool. So you get$${N \choose 5} {N-5 \choose 5}.$$If the side doesn't matter, then divide that by 2. (In League of Legends there is reason to believe it matters, because the most popular map Summoner's Rift is not ... 1 Here's your mistake:$$ \sum_{v=0}^n (-1)^v \binom{n}{v} \sum_{k=1}^r \binom{r}{k} (n-v)^{r-k} = \sum_{v=0}^n (-1)^v \binom{n}{v} [(n-v+1)^r-(n-v)^r], $$because in the binomial formula the index runs from zero to r while here it starts at k=1, so you have to subtract the k=0 term. 0 gt6989b's comment goes most of the way towards solving your problem. The number of paths from i to j of length m is (X^m)_{ij}, so the number of paths from i to j of length at most m is \left(\sum_{k=0}^mX^k\right)_{ij}. In your case, all these entries should be positive for m=5, so you want$$ ...

0

If we exclude $\frac 12$ the corner squares and $\frac14$ of the border squares from the count, say the whole of the left column, our count will be correct, and the Pr equation will be: $$\frac {4n(n-1)}{n^2(n^2-1)} = \frac{4}{n(n+1)}< \frac{1}{2015}$$

6

We give a proof of the strict inequality $$\frac{1 + p(1) + p(2) + \cdots + p(n-1)}{p(n)} < \sqrt{2n}.$$ The square root arises by first proving an upper bound $(k-1)/2 + (n/k)$ for any integer $k \geq 1$, and then minimizing over $k$; this kind of thing is seen often in analysis, but isn't a common tactic in the inequalities that appear in competition ...

1

You are correct for all numbers with repetition and for the number with distinct (not distinguishable) digits. Your last is correct if you require exactly one pair of matching digits. $5 \choose 2$ locates the pair of digits, there are $9$ choices for the paired digit the $8,7,6$ for the other three.

2

I'll use functions $A(n), B(n)$ as defined in the question. A string beginning with $A$ must be followed by a second $A$ and then by any valid string of length $n-2$ beginning with either $A$ or $B$. A string beginning with $B$ must be either (i) followed by a second $B$ and then by any valid string of length $n-2$ beginning with $B$, so we keep an odd ...

3

You are on the right track, but a simple way is to notice that both $$a(n) = \sum_{t\mid n}d^3(t), \qquad b(n)=\left(\sum_{t\mid n}d(t)\right)^2$$ are multiplicative functions, so, in order to prove $a(n)=b(n)$, it is enough to prove: $$a(p^k) = b(p^k)$$ that is equivalent to the well-known identity: $$\sum_{j=0}^{k}(j+1)^3 = ... 0 For small n, a depth-first search using a list or set of "already seen" subsequences does the trick. 1$$\begin{eqnarray*}\sum_{j=3}^{n}\binom{n}{j}\frac{(j-1)!}{n^j}&=&\int_{0}^{+\infty}\left(\sum_{j=3}^{n}\binom{n}{j}\frac{x^{j-1}}{n^j}\right)e^{-x}\,dx\\&=&\frac{1}{2}\left(-3+\frac{1}{n}\right)+\int_{0}^{+\infty}\left(\left(1+\frac{x}{n}\right)^n-1\right)\frac{e^{-x}}{x}\,dx\end{eqnarray*}$$hence by approximating ... 0 There are (n-1)n ways for your chosen squares to be adjacent horizontally, and the same number of ways to be adjacent vertically. There are n^2(n^2-1)/2 ways to choose the two squares. Taking n=89 gives a probability of 1/2002.5 and n=90 gives 1/2047.5. So, you did get the correct answer. The argument you made works only for squares away from ... 2 The reason your argument doesn't work is that the corner and edge squares of the grid are NOT adjacent to 4 squares each. Edge squares are adjacent to 3, and corners are adjacent to 2. Instead, a good strategy would be: (1) count the number of PAIRS of squares that are adjacent (horizontally or vertically); (2) count the number of total pairs of ... 1 Hint: Start with A is simple, for then we need to have another A, and we append a good string of length n-2. Start with B is more complicated. (i) If we have an A next, then we need another, then a good string of length n-3. (ii) If we have a B next, then \dots. Added: We expand on the hint. Let F(n) be the number of good strings of length n. ... 0 Every part of the problem has been answered correctly but IV. Hint for IV: Let's calculate the answer for different question at first. Suppose we have 4 balls and want to select 5 ball (returning after every draw). What is the probability that all of the balls have been chosen at least once? The answer not surprisingly is \frac{4!*4}{4^5}. And here ... 1 A way you can think about these probabilities is microstate counting: you can effectively consider every possible scenario, and then count that ones that will work. You're drawing one of 5 balls each time, so the total number of possible combinations will be 5^5 = 3125. For the first part, you want each ball to be different: that means the balls you ... 0 Note that we have 5 possibilities for each pick. So we get a total of 5^5=3125 possibilities. For (I), the number of picks is the number of ways to order 5 balls. This is 5!=120. Hence the probability is \frac{120}{3125}=\frac{24}{625}. For (II), note that this means that we do not pick all five balls, so using the complement rule and the answer to ... 1 The second time you have a chance of \frac 45 not choose what you chose first. The third time you have a chance of \frac 35 not to choose what you chose the first and the second time ... So your chance to chose 5 different balls is$$\frac{4\cdot3\cdot2}{5^4}=\frac{24}{625}.

Top 50 recent answers are included