Tag Info

4

There is a book called "Proofs that Really Count: The Art of Combinatorial Proof" by Arthur T. Benjamin and Jennifer J. Quinn, which might be of interest to you.

4

Jack D'Aurizio's answer works very well, but I see another way to solve it using chromatic polynomials. I understand that this is not the way your book wants you to solve it, but I'm posting it here for future reference: Draw a graph with five vertices with edges connecting the vertices that cannot receive the same color. (The edges are AC, AD, BD, BE, and ...

3

If a single colour appears more than once, it must appear at two consecutive vertices and nowhere else, hence the possible colourings fulfilling the constraints are: $T_0$: $ABCDE$; $T_1$: $AABCD$ and cyclic shifts; $T_2$: $AABBC$ and cyclic shifts. There are $7\cdot 6\cdot 5\cdot 4\cdot 3 = 2520$ colourings in $T_0$, $5\cdot(7\cdot 6\cdot 5\cdot ... 3 Let$A_i$denote the number of times number$i$appears (each number is equally likely to appear) and$\mathcal{A}$be the set of all possible combinations of$a\equiv(a_1,\dots,a_K)$s.t.$\sum_{k=1}^Ka_k=N$and each$a_k\ge 0$. Then for$a\in \mathcal{A}$... 2 There are$7$ways to color vertex$A$, split in two cases: Case$1$:$D$and$C$have the same color, there are$6$ways to pick that color, after this, vertices$E$and$B$must be distinct and must not have the color of$D$and$C$, there are$6\cdot 5$ways to do this,$7\cdot6\cdot6\cdot5=1260$total. Case$2$:$D$and$C$have different colors, ... 2 There are indeed$24$ways to return to$(0,0)$if we move in all four directions, but we can also get there moving only north and south or only east and west. Each possibility gives us$\binom{4}{2}=6$options. Hence there are$24+12=36$ways to return to$(0,0)$in$4$moves. On the other hand there are$4^4$possible movement sequences. Final answer is ... 2 By saying we are "arranging" the books on a shelf, the order usually matters. So my calculations assume that the order of the books matters. To do this, first we choose the math books, which can be done in${7 \choose 3}$ways. Then we choose the history books, which can be done in${4 \choose 2}$ways. Then we choose the fiction books, which can be done in ... 2 In how many ways can two distinct subsets of the set A of k (k≥3) elements be selected so that they have exactly two common elements? Choose two elements for intersection: $$\binom k2=\frac{k(k-1)}2$$ Rest two elements have 3 choices:$A-B,B-A,(A\cup B)'$and minus for one case where all go to$(A\cup B)'$because then$A=B$: $$3^{k-2}-1$$ Since we ... 2 You are assuming that all the elements of$A$have to be in one subset or the other, which is not required. After you put the two elements in both$P$and$Q$, each element can go in$P$, in$Q$, or neither independently. That gives a factor$3$for each of the$k-2$remaining elements. You divide by$2$because you are double counting-each assignment of ... 2 I believe the bounty should go to Tad, who developed the mathematical approach. I tried to improve on it but couldn't, so instead I coded it a whole lot faster :-). Here's the code. It uses a special bit encoding for efficient arithmetic with vectors over$\mathbb F_3$. On my MacBook, it takes half a minute to test a candidate with$31$weighings and two ... 1 The problem states that "Given that a maximum of 3 substitutes may be used". This means that from your$2*5*5*3$you need to subtract the number of possible teams with all 4 substitutes used. If all 4 substitutes are used, there are 4 ways to choose the other 3 defenders out of 4 non-substitutes, 4 ways to choose the other 3 midfielders out of the 4 ... 1 You can also use Inclusion–exclusion principle. Without the restriction$x_i\neq 3$you have $$\binom{10+5-1}{10}$$ solutions. Now you need to check how many bad cases you have. Denote the set of all solutions with$x_i=3$by$A_i$. Your bad cases are $$A_1\cup A_2\cup A_3\cup A_4\cup A_5.$$ Can you take it from here? 1 Let's begin by rewriting the formula with a shift from$n$and$m$to$n+1$and$m+1$, so that the expression to prove is $${n\choose m} = {n+1\choose m+1}-{n+1\choose m+2}+{n+1\choose m+3}-\cdots+(-1)^{n-m}{n+1\choose n+1}$$ Now picture a class with$n$students and a teacher. Each term on the right is of the form${n+1\choose k}$, which counts the ... 1 Let$v_1,\ldots,v_n$be the variables and$\phi(v_1,\ldots,v_n)$an expression in these using only$\land$and$\lor$as connectives. Then we can rewrite this as $$\phi(v_1,\ldots,v_n)\iff v_n\land\phi_1(v_1,\ldots,v_{n-1})\lor \phi_2(v_1,\ldots,v_{n-1})$$ so that we can represent an expression in$n$variables as a pair of expressions in$n-1$variables. ... 1 You are really asking how many different boolean functions of$n$variables can be constructed using$\land$and$\lor$. Assuming you don't allow empty expressions (always true or always false), this is OEIS sequence A007153. 1 Going north at the first step, there is 9 possible paths NSNS, NSEW, NSSN, NSWE, NEWS, NESW, NWES, NWSE, NNSS So in total there is 4*9 = 36 possible paths to get back at the origin after 4 hop 1 I can get rid of the explicit appeal to probability by showing combinatorially that$f\upharpoonright\big(\Bbb Q\cap(0,1]\big)$is monotone non-decreasing and then extending the result to$f\upharpoonright[0,1]$by continuity. Note, though, that at bottom it’s really the same basic argument. Let$c$be an integer greater than$1$, and let$g\le c$be a ... 1 I don't know if this counts as an elegant solution in your book, but I think it's cute. Let's say the "frequency state" of a deck is the number of cards of each face value remaining. A full deck, for example, has the frequency state "4 aces, 4 twos, 4 threes...," while an empty deck has the frequency state "0 aces, 0 twos, 0 threes...." There are$5^{13}$... 1 Each point has probability$1-(1-1/N)^N$of being drawn. (This goes to$1-1/\mathrm e$for$N\to\infty$.) Thus by linearity of expectation, the expected number of points drawn is$N\left(1-(1-1/N)^N\right)\$.

Only top voted, non community-wiki answers of a minimum length are eligible