# Tag Info

1

$N-1\;\; x's$ of length $2 [1-2\;\;thru\;\; (N-1)-N]$ $N-2\;\; x's$ of length $3 [1-2\;\;thru\;\; (N-2)-N]$ ..... ..... $2\;\; x's$ of length $N-1 [1-(N-1)\;\;thru\;\; (N-1)-N]$ sum $= [1+2+3+........(N-1)] - 1$ You must be knowing the formula for the sum of terms within the brackets $[\;\;\;]$ Added: a combinatorial approach Consider a string of ...

1

For $N$ x in a row, we have $N$ x, we have $N-1$ of 2 x's in a row, N-2 of 3 x's in a row. In general we have $N-k+1$ of $k$ x's in a row. To see why is that so, construct a window of length $k$ and move it.

0

The induction step $$(n+1)(n+1)!+(n+1)!=(n+2)!$$

0

Two answers have already given a winning strategy for $n\gt k$. For $n=k$, in each step we win unless we choose a complete set of $n$ different numbers. The other $n$ numbers are also all different, so whatever subset we pick from them in the following step, it won't contain a pair, and no matter what we know about these numbers, there's no way to prevent ...

0

One way to do it, is to take it "step by step". When counting numbers in base $10$ from $0$ to $(10^n-1)$, you will find that there is a equal number of numbers with at least one digit $k$ for any digit from $1$ to $9$. So if you have all the numbers between $0$ and $(10^n-1)$, including those two, you can calculate how many of them contain at least one ...

0

I suppose the question is to find all positive integers $n$ such that $x^n-2$ has a root in the field $\mathbb{F}_{13}$. One checks that this is exactly the case for $n=1,5,7,11$, where we can assume that $n\le 11$. The Berlekamp algorithm easily shows the existence (or non-existence) of a linear factor; e.g., $x^{11}-2$ has the linear factor $(x+6)$.

0

Select $n=11$, then we have: $x^{11} \equiv 2 \pmod{13} \iff 1 \equiv x^{12} \equiv 2x \pmod{13}$. Obviously as $(13,2)=1$ this equation has solution, namely numbers of the type $x=13k+7$. Furthermore since $13$ is a prime using the Fermat's Little Theorem it's enough to check the cases $n\le 11$. Now use that $2$ isn't a quadratic residue modulo $13$, ...

1

I see why you're unsure how to proceed. There are unstated assumptions in the question. In an ideal world, you'd know exactly what's being asked, but this isn't an ideal world. I can tell you why I'd suspect that there need to be four rowers on each side, though: For most situations it's impractical to have more rowers on one side than the other. The ...

1

I'm assuming that by "arbitrarily permutes the $k$ chosen cards" you mean that the $k$ chosen cards are placed in their original positions but in a different order; i.e. from $\{1, 2, 3, 4, 5, \dotsc\}$, if $\{2, 3, 5\}$ were chosen then a valid placement would be $\{1, 3, 5, 4, 2, \dotsc\}$ but not $\{2, 3, 1, 4, 5\}$. Further, I assume that no card is ...

1

$\textbf{Winnable for } k<n:\quad$ At step $l$, choose the cards in positions $l,l+1,\ldots,l+k$. Comparing the $k-1$ cards you see at positions $l,l+1,\ldots,l+k-1$ with the ones you saw at the previous step, you can conclude which card is at position $l-1$. (Obviously, this only applies from step $2$). After $n+2$ steps you know for certain which cards ...

0

I found very useful material in the following documents. Newman, structure of complex networks http://arxiv.org/abs/cond-mat/0303516 Newman, random graphs as models of networks http://www.santafe.edu/media/workingpapers/02-02-005.pdf Callaway at al. Network Robustness and Fragility: Percolation on Random Graphs ...

1

Hint: If $p^e$ divides $n$, then $\varphi(p^e)=p^{e-1}(p-1)$ divides $\varphi(n)$. Therefore: $p=2$ and $e-1 \le 3$, or $p$ is odd and $e=1$ and $p-1$ divides $8$. This limits the possible candidates for $p^e$. You then need to argue how these candidates can be combined to yield $\varphi(n)=8$.

11

Considering that the sequence in which he visits these $n$ cities, is $$a_1, a_2, \dots, a_n$$ then $a_i \neq i$. This is a derangement, whose formula is given by $$!n=\left[\frac{n!}{e}\right]$$ where $[x]$ is the nearest integer function and $!n$ is the number of derangements for an sequence with $n$ elements. This sequence also appears in the Online ...

3

Hint look up dearrangements. $D_n=N!(1-1\frac{1}{2!}...+\frac{(-1)^n}{n!})$

1

You have to assume that there are no lines through more than 2 points except for the line $L$ containing the 4. So for each of the points on $L$ we have 6 lines to the other points. That is 24 lines plus $L$, giving 25. We then have lines between the other 6 points. There are ${6\choose 2}=15$ pairs of points each of which gives a line, so a grand total of ...

7

First idea: if you want the number of something from $42523$ through $93107$, it may be easier to count the ones from $0$ through $93107$ and subtract the ones from $0$ through $42522$. Let $N(n)$ be the number of numbers up to $n$ that contain at least one $7$. You want $N(93107)-N(43522)$. It helps to prefix the numbers with zero so all numbers have ...

0

Since $7$ is prime, there are no periods other than $1$ and $7$. There are $2$ arrangements with period $1$, so the remaining $2^7-2$ arrangements have period $7$. Thus there are $$2+\frac{2^7-2}7=20$$ rotationally inequivalent arrangements. The orbits under the full symmetry group including reflections can be counted using Burnside's lemma. The ...

0

I will assume that you only bet to one pair of outcomes for each combination. Let's say you want to risk a quantity x of your capital in a strategy involving every possible double combination within a set of games. The formula to calculate the number of possible combinations can be derived from geometry, for it is like finding the number of sides and ...

2

The formula $\frac{n!}{k!l!m!}$ is the total number of possible codes. For question 1, you want $\frac{n!}{k!l!m!}$ > 27. And you also need to satisfy n = k+l+m. And clearly, $\frac{4!}{k!l!m!}$ will not work for all possible k,l,m. We can try n = 5, and see that $\frac{5!}{1!2!2!} = 30 > 27$. Hence, the minimum possible n is 5. For question 2, we have ...

3

We're trying to count factorizations $126=abc$ with $a\le b\le c$. Note that, except for $1\cdot1\cdot126$ and $3\cdot3\cdot14$, the rest have $a\lt b\lt c$, since $3$ is the only repeated prime factor of $126$. Let $m$ denote the number with $a\lt b\lt c$, so the number we want to find is $m+2$. If we remove the condition $a\le b\le c$, the number of ...

1

This is a classic scenario where the underlying poset has the subsets of $[m]$ (where $n/2=m$) as nodes, order is by set inclusion, and the Mobius function on the nodes is the usual $(-1)^q$ with $q$ the number of elements. Therefore we can just plug these data into the usual inclusion-exclusion formula to get $$\sum_{q=0}^m {m\choose q} (-1)^q ... 1 This makes a lot of sense, and I doubt that there's a significantly easier way of solving this. You basically followed the usual derivation of the number of derangements, and the result in that case, where there's greater symmetry, can't be simplified, so it would be surprising if it could be simplified in this case. The only simplification I see is that you ... 1 (I made a mistake in the first version of this answer, it should be fixed now) (As pointed out by @DougM there was also a mistake in the second version, that is also fixed now) 126 is so small that it's probably faster to just list the ways, but here's a very detailed argument. Any factor is a product of some of the prime factors, so as you have those, ... -2 As you said, prime factors of 126 are 126=2*3*3*7 Then in order to make it as a product of 3 positive integer factors, you need to pick two out of four from these prime numbers and multiply them to get an integer, leaving the other two as prime. But since number 3 repeat twice, you need to divide by 2! So there are \frac{4C2}{2!} = 3 ways 1 Suppose we seek to evaluate$$S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}.$$This is$$S(N) = \sum_{n=N}^\infty \frac{t^n}{n!} \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n.$$Now introduce$$(1+j)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((1+j)z) \; dz.$$We ... 1 But you have to choose 1 number out of 34(=40-6) numbers not correctly. Therefore the probability to choose 5 out of 6 numbers correctly is$$\large{\frac{{6\choose 5} {34 \choose 1} }{40 \choose 6}}$$3 Here's an outline of the proof: Show that there are 14 primes under \sqrt{2015}. Let R be a set of 14 composite coprime numbers under 2015. It is well-known that any composite number has a prime factor under its square root, so in this case, each of these composite numbers has one of the prime factors under \sqrt {2015}. Now, using that ... 1 The number of derangements of n items is \left[\dfrac{n!}{e}\right] where [x] is rounding to the nearest integer to x so you are trying to solve \left[\dfrac{5!}{e}\right]\left[\dfrac{(n-5)!}{e}\right] = 11660 or (n-5)!\approx e^2 \dfrac{11660}{120} \approx 717.97 and since 6!=720 this means n-5=6 and thus n=11 0 Yes, because the two events are complementary. There's really nothing else to say. 0 So we want to estimate:$$\frac{63!}{19!44!} $$We do this by doing a geometric average approximation, replacing each factorial by it's geometric average, and the following approximations 9.5^{19} \approx 9^{20} and since it's a matter of life and death we expose we know the 10% and 5% interest tables by heart (useful since 22 = 20\cdot 1.1 and 31.5 = ... 3 Let M be a set with cardinality m, and let$$ N:= \Bigl\{ \{a_1^1\};\{a_1^2;a_2^2\};\{a_1^3;a_2^3;a_3^3\} \dots \{a_1^n;a_2^n; \dots;a_n^n\}\Bigr\}, $$where a_{n_1}^{n_2} = a_{n_3}^{n_4} \iff (n_1 = n_3 \wedge n_2 = n_4). (We can see that |N| =n). Of course S_k(1) = 1^k is the number of functions from a set of cardinality k to the set of ... 0 Use averages between two equally displaced factors: \frac {63 \times 62 ... \times 54 ...\times 45}{19 \times 18 \times ... \times 9 ...\times 1} \approx \frac {54^{19}}{9^{19}} = 6^{19} Based on formula (N+n)\times(N-n)= N^2-n^2, n^2 "small" to N^2, which is good enough for numerator and not so good for denominator, so because of easier ... 0 With pen and paper, Stirling's approximation:$$ \begin{align} {63 \choose 19} &= \frac{63!}{19! 44!} \\ &\doteq \frac{\sqrt{2\pi 63}}{\sqrt{2\pi 19}\sqrt{2\pi 44}} \left( \frac{63}{e}\right)^{63} \left( \frac{e}{19}\right)^{19} \left( \frac{e}{44}\right)^{44} \\ &\doteq \sqrt{\frac{60}{2 \cdot 3 \cdot 20 \cdot 50}} \cdot ...

0

Here you go! ${63\choose19} = 6.13116E+15$ ${63\choose19} = \frac{63!}{19!44!}$ $$= \frac{63^{63}}{19^{19}.44^{44}}$$$$\approx \frac{60^{60}}{20^{20}.40^{40}}$$$$\approx \frac{3^{60}}{2^{40}}$$$$\approx 16.3^{32}$$$$\approx 9^{16}$$$$\approx 10^{16}$$ This uses Sterling's approximation for factorial (n)

0

This is related to necklace polynomials. Let $a_{kn}$ count the number of aperiodic strings of $n$ letters from an alphabet of $k$ letters. For each $d\mid N$, an aperiodic string of length $d$ gives rise to a string of length $N$ with period $d$, so the total number $k^n$ of strings of length $N$ with arbitrary period can be written as $$k^N=\sum_{d\mid ... 7 In the numerator we have 63!/(63-19)!\approx(63-9)^{19}=54^{19}\approx50^{20}=100^{20}/2^{20}\approx10^{34}. In the denominator we have 19!\approx\left(\frac{1+19}2\right)^{19}=10^{19}. So the quotient is roughly 10^{15}. I'm not sure I could have done that in two minutes under the threat of death, though. 2 It's not the order you pick the couples in, it's what the final pairing is. So in the case n=3, picking 12,34,56 is the same as picking 34,12,56 or any other combination of 12,34 and 56, just as long as you pick those couples. 31 Two minutes is a lot of calculations, I'd write the 19 numbers in the numerator and the 19 numbers in the denominator, and cancel whatever can be cancelled in under a minute. You get:$$ 3^3\times5^2\times7^2\times23\times29\times31\times47\times53\times59\times61$$We approximate this as:$$20\times 20 \times 50 \times 20 \times 20 \times 20 \times 50 ...

2

It seems to be The Art of Combinatorics, Volume IV: Arrangements and Methods by Douglas B. West; see here: http://www.math.illinois.edu/~dwest/. “Four advanced graduate textbooks and research references on classical and modern combinatorics. Preliminary versions available by special arrangement for use in specialized graduate courses; not available for ...

3

You correctly found that there are $3^5$ functions from a set with five elements to a set with three elements. However, this counts functions with fewer than three elements in the range. We must exclude those functions. To do so, we can use the Inclusion-Exclusion Principle. There are $\binom{3}{1}$ ways of excluding one element in the codomain from the ...

3

Hint on c) The "onto"-function will induce a partition of its domain (as any function) and this partition (actually the fibres of the function) will - because it is onto - have exactly $3$ elements. So to be found is in the first place how many such partitions exist. A fixed partition gives room for $3\times2\times1=6$ functions. So you end up with: ...

0

In short, although I am 100% sure this is in your textbook (and, to be honest, if you don't know that it is in your textbook and your test is tommorow, I don't have high hopes for you...): If you are picking $k$ items out of $n$ and: order matters and you are not replacing the items: $n\cdot (n-1)\cdots (n-k+1)$ order matters and you are replacing the ...

1

Answering the title: The number of $6$-letter strings is $(21+5)^6$ The number of $6$-letter strings with no vowels is $21^6$ The number of $6$-letter strings with at least one vowel is $(21+5)^6-21^6$ Answering the body: The number of $6$-different-letter combinations is $\binom{21+5}{6}$ The number of $6$-different-letter combinations with no ...

1

2 cans of tomatoes, 3 of peas and 1 of beans $Y$ is the number of cans opened until the 2 cans of tomatoes are open.   We measure the probability of selecting 1 from 2 tomato cans and $y-2$ from the 4 others in some arrangement out of the ways to select $y-1$ from $6$ cans, times the conditioned probability of selecting the 1 tomato can from the ...

1

Clearly, the stopping criterion is that the second can of tomatoes is opened. If there are three cans of peas, then it is entirely possible that all three cans could be opened before the second can of tomatoes is opened, since the final can that is selected could be the second tomato can. The most direct way to compute the joint distribution is to consider ...

1

Label the kids, say 1, 2, 3 and 4. (3) I would use inclusion / exclusion. (4) 10 ways to pick 1 out of 10 candies for kid 1, 9 ways to pick 1 out of the rest 9 for kid 2, etc. The result would be $10 \times 9 \times 8 \times 7$ (5) The number of ways to choose 4 out of 10 items is $$\binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 ... 1 The candy bars are identical, all 10 of them must be given out, and each kid gets 0 or more. You are correct that the number of ways of distributing the candy bars to four children is the number of solutions of the equation$$x_1 + x_2 + x_3 + x_4 = 10$$in the non-negative integers. The candy bars are identical, it's allowed to give out fewer ... 1 Yeah, Chebyshev does the trick. What you want to show is that when flipping 2m coins the probability of getting a number of heads less than \sqrt{m} apart from the expected number of heads is less than \frac{1}{2}. By Chebyshev the probability the outcome is more than \sigma k units apart from the expected value is less than \frac{1}{k^2} ( ... 2 Since the balloons are identical, what matters is how many balloons each child receives. Let x_k be the number of balloons distributed to the kth child. Then we must determine the number of solutions of the equation$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 48 in the positive integers. A particular solution corresponds to the placement of six ...

0

Let 0 denote balloons and 1 denote children. Then we would have 48 0's and 7 1's. The question becomes how many ways are there to insert these 1's into the 0's. The number of 0's separated by 1's is the number of balloons for each child. For example: If there are 4 children and 10 balloons, and we have a sequence like this: 0000110001000 That means 4 ...

Top 50 recent answers are included