# Tag Info

1

Although formulas are very useful, it is helpful to do a full analysis each time. There is a total of $2^9-1$ ways to choose a non-empty subset of our group. Pity about not counting the empty set: I would prefer the performance. Call a choice of jugglers bad if it is all male. The same analysis shows there are $2^5-1$ bad choices. Thus the number of good ...

1

It should be the number of nonempty sets you can build with 9 elements, $\sum{9 \choose k}$ which is $2^9 - 1$ MINUS the number of nonempty sets you can build with 5 elements which would correspond to the number of sets in which there are no female jugglers, which would be $\sum{5 \choose k}$, which equals $2^5-1$ Your teacher is correct because the two ...

1

$$\underbrace{(2^9 - 1)}_{\text{non-empty subsets}} - \underbrace{(2^5 - 1)}_{\text{non-empty sets of men only}} = 2^9 - 2^5$$

1

Answer. $\binom{p}{n}$. Every such map is fully characterized by its range, and its range is a subset of $N_p^*$ consisting of $n$ elements. There are $\binom{p}{n}$ such subsets.

0

To print all subsets of $S$ of length $m$, call $f(S, 0, 0, m)$, where $f$ is defined in pseudo-code as: function f(S, i, j, m) { if(i == n) { if(j == m) Print R return } f(S, i + 1, j, m) R[j] = S[i] f(S, i + 1, j + 1, m) } and $R$ is a global array.

1

If this would not be a necklace then the number of ways to order them would be $\frac{7!}{3!4!}$. But now we may rotate and we have $7$ kind of rotations. So the total becomes $\frac{7!}{3!4!7}=\frac{6!}{3!4!}$. With the same reasoning we get that in general we have $\frac{(n-1)!}{r_1!r_2!...r_k!}$

7

$$T_{n+1}=\sum_{r=1}^{n+1}T_r - \sum_{r=1}^{n}T_r = \frac{1}{2}(n+1)(n+2)(n+3)$$ So, \begin{align} \sum_{n=1}^{m}\frac{1}{T_r} = \sum_{n=1}^{m}\frac{2}{n(n+1)(n+2)} &= \sum_{n=1}^{m}\frac{2(n+1)^2-2n(n+2)}{n(n+1)(n+2)} \\ &= \sum_{n=1}^{m}\frac{2(n+1)^2}{n(n+1)(n+2)} -\sum_{n=1}^{m}\frac{2n(n+2)}{n(n+1)(n+2)} \\ &= ... 0 All the part of the arrays have as generating function 1+x+x^2+x^3+...=\frac{1}{1-x}. So the total generating function is (\frac{1}{1-x})^{k+1}=\frac{1}{(1-x)^{k+1}}. Then notice k-th derivative of \frac{1}{1-x} equals k!\frac{1}{(1-x)^{k+1}} . Therefor \frac{1}{k!}\left(\frac{1}{1-x}\right)^\text{k-th derivative}=\frac{1}{(1-x)^{k+1}} On the ... 0 a liar tells that both his neighbours are liars. Thereforeign at least 1 neighbour of each liar is truthful. Therefore no three successive boys can be liars. Each truth teller's both neighbour are liars, so no two successive boys are truthful. Suppose there are k truth tellers. Around the table, between every pair of successive truth teller there are k gaps. ... 2 If there are \le 6 truth tellers, then there exist 3 liars sitting together by pigeon-hole principle. Now the one in the middle of these three is telling the truth when he/she says "my neighbours are liars", a contradiction! 1 No three consecutive boys can be liars, or else the middle one would not say both his neighbours are liars. So very boy either tells the truth or has a neighbour that tells the truth. If there were at most 6 truth tellers, that would account at most for those 6, plus their 12 neighbours; their might be overlap, but in any case this cannot cover all ... 2 Series are absolutely convergent, so we can expand using Cauchy products:\begin{align}\cos^2 x&=\left(\sum_{n=0}^\infty(-1)^n\frac{x^{2n}}{(2n)!}\right)^2=\sum_{n=0}^\infty\sum_{k=0}^n(-1)^{n-k}\frac{x^{2n-2k}}{(2n-2k)!}(-1)^k\frac{x^{2k}}{(2k)!}\\&=\sum_{n=0}^\infty x^{2n}\sum_{k=0}^n\frac{(-1)^n}{(2n-2k)!(2k)!}=1+\sum_{n=1}^\infty ...

5

There is no need for complicated Cauchy products. We will simply use $\Big(f^2(x)\Big)'=2f(x)f'(x)$. $$\sin(x)=\sum_0^\infty(-1)^{n}\frac{x^{2n+1}}{(2n+1)!}\iff\sin'(x)=\sum_0^\infty(-1)^{n}\frac{x^{2n}}{(2n)!}=\cos(x)$$ $$\cos(x)=1+\sum_1^\infty(-1)^{n}\frac{x^{2n}}{(2n)!}\iff\cos'(x)=\sum_1^\infty(-1)^{n}\frac{x^{2n-1}}{(2n-1)!}=-\sin(x)$$ Now, ...

1

I would proceed like this. What is the probability that the four friends are assigned to the big group? Call them A,B,C,D and assume that A is assigned first, then B, then C, then D, then the rest of the $100$ people. The probability A is assigned to the big group is $\frac{40}{100}$. Given that she has been assigned to the big group, the probability B is ...

0

I think that this answer is right so I wanted to share it with you. with the probability $p$ I put elements for $A_{i}$ and with $1-p$ for $B_{i}$ and for $A_{i}$ we do it $k$ times and for $B_{i}$ we do it $l$ times,so it happens with the probability $p^{k}(1-p)^{l}$,and because $1 \leq i \leq h$ so by the rule of sum in probability we have $$... 0 Good question! For one thing, any power series$$f(x) = \sum_n a_n (x-a)^n$$may be converted into a power series based around 0 by taking$$g(x) = f(x+a) = \sum_n a_n x^n.$$and power series of this form are more convenient to work with. For example, we frequently want to multiply generating functions, but how should we interpret a product of power ... 0 Ok a lot question let's answer the first! Given a Set A=\{a,b,c,d\} all subsets with n=3 elements are:$$ \{a,b,c\}, \{a,b,d\}, \{a,c,d\}, \{b,c,d\} $$To generate this list you can use this (in c), given |A|=\#A=m # Counter Array int count[n]; int j; # Initialise Array for(; j < n; j++){ count[j] = j; } # Now Iterate throught ... 0 Use generating functions, e.g. define F(z) = \sum_{n \ge 0} f(n) z^n. Then you have:$$ \sum_{n \ge 0} f(r + n) z^n = \frac{F(z) - f(0) - f(1) z - \cdots f(r - 1)z^{r - 1}}{z^r} $$Set up your recurrence like:$$ a_k f(n + k) + a_{k - 1} f(n + k - 1) + \cdots + a_0 f(n) = 0 $$Multiply by z^n, sum over n \ge 0, and recognize the above:$$ a_k ...

1

Use generating functions. I.e., in your case for: \begin{align} \text{Red:} & 1 + z + z^2 + z^3 + z^4 + z^5 \\ \text{Blue:} & 1 + z + z^2 \\ \text{Green:} & 1 + z + z^2 + z^3 \end{align} Then the generating function of the number of posibilities is just: $$(1 + z + z^2 + z^3 + z^4 + z^5) \cdot (1 + z + z^2) \cdot (1 + z + z^2 + z^3)$$ Some ...

3

Suppose for simplification that the polyomial has $n$ distinct roots. First, considering $F(n) = (f(n+k), \ldots , f(n))$ you can make the problem go to the space $\Bbb R^{k+1}$ and assume that the relation is $$F(n) = AF(n-1)$$ where $A$ has the form of a companion matrix. The characteristic polynomial of $A$ is the polynomial giving the characteristic ...

3

It is possible to find the parity from the formula $$\sum_{i=0}^n (-1)^i \frac{n!}{i!}=\sum_{i=0}^n (-1)^i n(n-1)\cdots(i+1).$$ Working modulo $2$: If $n$ is even, then there is one non-zero contribution to the sum is when $i=n$, so we have an odd number. If $n$ is odd, then there are two non-zero contributions to the sum, when $i=n$ and when $i=n-1$, so ...

1

Hint: Pigeons are the remainders when you divide $\pm a_i$ by $2014$. Holes are the possible remainders. How many pigeons and holes are there? And what happens if two pigeons are in the same hole?

1

We will show that if condition is violated then there cannot be more than 1008 numbers.Lets say x is the residue of some $a_i$ then no other number can have x as residue or -x as residue. Also it will reduce the set by 2 unless and until x=-x which is true for x=1007,0.So the set which violates the above condition can have at most 2012/2+2=1008 elements

4

Generally, derangements come in pairs: the inverse of a derangement is a derangement. The exceptions are the fixed-point-free involutions, i.e., the permutations in which every cycle is a $2$-cycle. Thus the parity of the number of derangements is the same as the parity of the number of fixed-point-free involutions. If $n$ is odd, there are no ...

1

If you choose a permutation of the $8$ letters at random, focus only on the $6$ positions containing a letter from $\{A,B,C,F,G,H\}$, and consider the subset of the $3$ of those positions that contain $A,B,C$, then any one of the $\binom63=20$ possible subsets is equally likely to occur. In order for $A,B,C$ to all come before each of $F,G,H$ in the the ...

2

There is a general rule - the mex rule - for computing Grundy values (or equivalent Nim heaps) in Nim-like impartial games. The moves you have available are take one stick or take two sticks. These lead to smaller positions whose values you already know. List those values and find the first number from $\{0, 1, 2, 3\dots \}$ which you cannot reach. This ...

1

First, there are $3!$ ways to arrange $\{A,B,C\}$, and $3!$ ways to arrange $\{F,G,H\}$, and we know that the former are to the left of the latter. The last two letters, $D$ and $E$, are entirely free to occupy the seven spaces surrounding the six letters that are already placed. These free letters could share any of $7$ spaces, or they could occupy any of ...

0

There's a nice simplification: define a related triple $(d_1, d_2, d_3)$ by \left\{ \begin{align} d_1 &= e_1 - 10 \\ d_2 &= e_2 - 1 \\ d_3 &= e_3 - 20 \end{align} \right. Then you have the system of equations and inequalities: \begin{align} d_1 + d_2 + d_3 &= 16 \\ 0 \le d_1 &\le 15 \\ 0 \le d_2 &\le 14 \\ 0 \le d_3 &\le ... 0 Using the lower bounds, write e_1 = 9 + f_1, similarly e_2 = f_2 and e_3 = 19 + f_3. Then you want positive-integer solutions to f_1 + f_2 + f_3 = 19 with f_1 \le 16, f_2 \le 15, and f_3 \le 26. The last of these is redundant (as f_3 \le 19-2 in any case), so drop it. The number of positive-integer solutions to f_1 + f_2 + f_3 = 19 is ... 2 For one pile, the 0 positions are the multiples of (2+1), and the G-values must all be 0,1 or 2, so G(n)=(n \mod 3). The Nim addition theory then dictates the G values for the game with several piles. 0 If non-transitive means "never transitive for any triple", that is impossible for a complete tournament (irreflexive, never-symmetric relation) with 4 or more players. The question sounds like an exercise of rediscovering that fact. If partial tournaments are allowed then it can be done with any number of players, just partition them into 3 categories ... 0 Hint: The problem is a natural for using a division into cases. Without loss of generality we may assume that the 4-game card is in the left pocket, and the 5-game card in the right pocket. Either (i) there are 4 credits left on the 4-card or (ii) 4 left on the 5-card. Event (i) has probability \frac{1}{2^5}, since she must have gone to ... 0 As explained in the wiki link given, your example is a size n=9 bracelet over k=4 colours. As a necklace it has N_k(n)=\frac{\sum _d^{\text{Divisors}[n]} \phi (d) k^{n/d}}{n} so 29144 different constellations. As a bracelet, it has B_k(n)=\text{If}\left[\text{EvenQ}[n],\frac{1}{4} (k+1) k^{n/2},\frac{1}{2} k^{\frac{n}{2}+\frac{1}{2}}\right]+N_k(n)/2 so ... 0 Your denominator looks all right. Let's define a random variable X such that X = "the number of shared numbers between 2 randomly chosen sets of the numbers 1-12." This helps us considerably when solving the problem: you are trying to solve for the Probability of X=n \implies P(X=n). Before continuing, it is worth seeing exactly what values X can take ... 0 As numerator you'll get{12 \choose n}{12-n\choose 5-n}{12-5\choose 5-n}$$(combinations you get the same n numbers)(of the remaining 12-n you have to pick 5-n)(of the remaining 12-n-(5-n)=12-5 he has to pick 5-n numbers) 2 Go backward : If from a position, you can reach a node in the kernel, it is not in the kernel. And if a node is not in the kernel, you can reach a node in the kernel from it. So 40,39,38,37 are not in the kernel (by adding 5, you reach 41+) but 35 is (because you can only go to 37,38 and 40 that are not). Go on like that ! 1 Hint: Since the order does not matter you should use Combinations. Case 1.$$\dbinom{90+x}{60}=\frac{(90+x)!}{60!(90+x-60)!}$$Case 2.$$\dbinom{50+x}{30}=\frac{(50+x)!}{30!(50+x-30)!}$$9 Consider the ordered pair, such that \{(x,y)\,|\,x,y\in\{a,b,c,d\}\}. The following relation satisfies those conditions:$$\{(a,b) ,(b,c), (c,d), (d,a)\}$$Clearly, this relation is not reflexive since there is no ordered pair with same members i.e. (x,x). This relation is anti-symmetric since for instance, there is no ordered pair (b,a). This ... 1 For the first step Every n_i can have a value 1,2,.. so the generating function for this n_i is \sum_r rx^r. So look at$$ (\sum_r rx^r)^k $$If you look to the coefficient of x^n then you have n_1+...+n_k=n because of the exponents and as coefficients it has$$ \sum_{n_1+...n_k=n}n_1\cdot...\cdot n_k $$I hope this makes it understandable. 1 Take a good look at the inner sum. The only k-dependent term is {m\choose k}r^k, and we are basically asked to find a closed form for what is obviously a partial expansion of (r+1)^m. But it is known, and has already been asked before on this site quite a few times, that such a form does not exist, not even for the simple case r=1. In other words, ... 3 You could use probability generating functions (PGFs) to model the situation. The PGF for rolling the first die is \frac{1}{6}(z^{1}+\dots+z^{6}) . The exponents label the pips of the die, the coefficients give the number of occurrences of an event, weighted with the probability \frac{1}{6} for each occurrence. To model the roll(s) of the second die z ... 0$$\frac{{2^{k}\choose b}}{{2^{k-1}\choose b}} \frac{2^{k}}{2^{k}-b} (2^{k})! = \frac{\frac{2^{k}!}{b!(2^{k}-b)!}}{\frac{2^{k-1}!}{b!(2^{k-1}-b)!}} \frac{2^{k}}{2^{k}-b} (2^{k})!=\frac{{2^k\choose 2^{k-1}}}{{ 2^{k}-b \choose 2^{k-1}-b }} \frac{2^{k}}{2^{k}-b} (2^{k})! $$NB this was posted before the modification of the original question. 0 For two pairs The digits which we have two of can be chosen in \binom{10}{2} ways. For each way of doing this, there are \binom{8}{1} ways to choose the loney digit. Once the digits have been chosen, the pair of largest equal digits can be placed in \binom{5}{2} ways. For each of these, the other pair can be placed in \binom{3}{2} ways. And, if we ... 1 \displaystyle n^4+5n^2+9\equiv n^4-1\pmod5 So, we need \displaystyle n^4\equiv1\pmod5\implies (n,5)=1 Now using Fermat's Little Theorem,$$n^4\equiv1\pmod5\text{ for } (n,5)=1$$So, we need to find the number of positive integers n\not>2013 those are relatively prime with 5 Now as 5 is prime, either (n,5)=1 or 5|n Can you calculate how ... 4 Consider rotating the table through all possible positions. Then every person has every card in front of them once, and so the total number of correct matches is 15. Since it is given that in one position there are no correct matches, the 15 correct matches must be distributed over 14 positions of the table. By the pigeonhole principle, there must ... 2 Let p(n) be the probability A wins the n-th game. We assume that what you have written is correct, that the loser of the previous game serves first, and that the person who serves first in a game has probability p of winning the game. For any n\ge 2, the event "A wins the n-th game" can happen in two disjoint ways: (i) A won the previous game, and ... 0 Let n be the number of questions. We are choosing 40 questions with replacement, so all n^{40} strings of 40 questions are equally likely. The number of sequences of 40 different questions is n(n-1)(n-2)\cdots (n-39). so the probability that all the questions are different is$$\frac{n(n-1)(n-2)\cdots (n-39)}{n^{40}}.\tag{1} We want to make ...

2

@Azoodish; I had Mathematica run it off since I could not do anything with it even with r = 1. For r = 1. $-2^{m-1} \left(H_m+2^{m+1} \Phi (2,1,m+1)+i \pi \right)$ $H_m$ is the mth Harmonic number. The other one is the LerchPhi function which is defined here: http://mathworld.wolfram.com/LerchTranscendent.html I know, not that useful, but at least you ...

0

As long as you're working on these types of problems in Wilf's book, you might also want to read a truly wonderful article by Noonan and Zeilberger on the Goulden-Jackson cluster method. It generalizes the above problem to avoid any collection of words (not just $k$ 1's in a row), and the method is no more complex than your calculation.

1

HINT: Since you can solve the regular form substitute $a_i = b_i -1$ where $b_i \in \mathbb N$. It is in the 'regular' form now. What similar thing can you do to deal with the $a_i \le 4$ constraint?

Top 50 recent answers are included