Tag Info

Hot answers tagged

9

This technique is known as the Roots of Unity Filter. See this related question. Note that $(1+x)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}x^k$. Let $\omega = e^{i2\pi/3}$. Then, we have: $(1+1)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}1^k$ $(1+\omega)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^k$ $(1+\omega^2)^{n} = ...


4

Here is a solution (to the problem as originally posted) that needs only 192 squares: Fill in the grid from the top right until you have placed 169 squares, leaving only an L-shaped gnomon of width 1. Then cover the gnomon as shown in the diagram. Distance $AB$ $=\frac14(5\sqrt{17}-9) > 2.9$ Distance $BC$ $=\frac98(\sqrt{17}-1) > 3.5$ So $3 + ...


3

This problem can be solved in general with Stirling numbers of the second kind. For more on general distribution problems see here. In your case you will want to sum $S(6,1) + S(6,2) + S(6,3)$.


3

One way to improve the poker hand counting problem to a more interesting version is: For a time in the 19th century there was a vogue for 65-card decks with five suits of 13 cards each. Calculate the proper ranking of poker hands when playing with such a deck. In particular, does a full house still beat a flush? Or similarly: On the planet ...


3

You can use something known as the Hockeystick Identity: $\displaystyle\sum_{A = 42}^{200}\dbinom{A-1}{A-42} = \sum_{A = 42}^{200}\dbinom{A-1}{41} = \sum_{n = 41}^{199}\dbinom{n}{41} = \dbinom{199+1}{41+1} = \dbinom{200}{42}$. Now, multiply both sides by $6^{42}$. Using WolframAlpha, we get that $\dbinom{200}{42}6^{42} \approx 1.46 \times 10^{76}$. If ...


2

The number of domino tilings of a $2 \times n$ rectangle is counted by Fibonacci numbers. This can be rather easily seen by showing they satisfy the same recursion. The number of Dyck paths (and many related objects) are counted by the Catalan numbers. Again this can seen, with a little more work than the previous example, that they satisfy the same ...


2

For a while I enjoyed passing the time in meetings by counting the number of permutations in each cycle class. Take $n=4$. There are 5 classes of permutations: There are respectively 1, 6, 3, 8, and 6 permutations of these types. One nice thing about this problem is that it has a built-in check: $1+6+3+8+6=24=4!$; if the counts didn't add to 24 ...


2

The number of ways to climb $n$ stairs in jumps of $1$ step and $2$ steps is quite nice, turns out the answer is the $n$th Fibonacci number. Another really nice counting problem is the number of standard tableau of shape $\lambda$, there is a beautiful formula for this known as the hook formula.


1

The number of ways $n$ items can be ordered if ties are permitted: $1,3,13,75,\dots$, OEIS sequence A000670.


1

If $1+\zeta+\zeta^2=0$, try to compute $(1+\zeta^0)^n + (1+\zeta)^n + (1+\zeta^2)^n$. Hint: $\zeta^3=1$, and, if $k$ is not divisible by $3$, $1+\zeta^k+\zeta^{2k}=0$.


1

The answer is $\dfrac{2^n+2\cos(n\pi/3)}3$. To see why, use the third unit roots $$1,\qquad \mathrm j=\mathrm e^{2\mathrm i\pi/3},\qquad\mathrm j^2=\mathrm e^{-2\mathrm i\pi/3},$$ and the fact that, for every $k$, $1+\mathrm j^k+\mathrm j^{2k}$ is zero except when $n$ is a multiple of $3$, and then it is $3$. Thus, $3$ times the sum $S_n$ to compute is ...


1

Here's a method that doesn't (explicitly) involve complex numbers. Let $A_n=\sum_k \binom{n}{3k}$, $B_n=\sum_k \binom{n}{3k+1}$, $C_n=\sum_k \binom{n}{3k+2}$. Then $A_n+B_n+C_n=2^n$ by the binomial theorem. Moreover, Pascal's identity implies the following: $$ \begin{eqnarray} A_n&=&A_{n-1} + C_{n-1} =2^{n-1}-B_{n-1} \\ B_n&=&B_{n-1} + ...


1

I wanted to post this as a comment but it's not letting me, so please go easy on me. Binomial coefficients are listed in Pascal's triangle, which suggests there is a recurrence relation for $\sum_{i = 0}^{\lceil \frac{n}{3} \rceil} \binom{n}{3i}$ and indeed there is. I looked in http://oeis.org/A024493 and found: $a(0) = 1$, $a(1) = 1$, $a(2) = 1$, $a(n) = ...


1

Following up on vadim123's comment, there are $16$ positions from which the black knight can attack $8$ squares, another $16$ from which it can attack $6$ squares, $20$ from which it can attack $4$ squares, $8$ from which it can attack $3$ squares, and $4$ (the corners) from which it can attack just $2$ squares. This gives a total of ...


1

Combinatorial Definition An $(n,k)$ partial permutation is a word of length $k$ made of the numbers in $[n]$ with no repetitions. Alternatively it is an injection $\sigma$ from $[k]$ to $[n]$. We are interested in the set $G_{n,k}$ of $(n,k)$ that satisfy the following condition. If we set $\sigma(0)=n+1$ (prefix the word with $n+1$) then the following ...


1

I'm assuming we have $r\geq p$. In that case, one just needs to choose $r-p$ other items to go with the $p$ required ones, and then permute all $r$ of those in every possible way. That gives us the formula $\binom{n-p}{r-p}\cdot r!$



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