Hot answers tagged

18

For fun, we do it using a combinatorial argument. Take $128$ different objects. We show that the right-hand side counts the permutations of these objects. Imagine doing the permutation as follows. First decide who will be in the first half (and therefore who will be in the second half). This can be done in $\binom{128}{64}$ ways. Now decide who among the ...


9

The question is straightforward. We have the right hand side equal to $$\frac{128!}{64!^2}\frac{64!^2}{32!^4}\frac{32!^4}{16!^8}\frac{16!^8}{8!^{16}}\frac{8!^{16}}{4!^{32}}\frac{4!^{32}}{2!^{64}}\frac{2!^{64}}{1}=128!$$


6

This is a falling factorial: $$ (n)_k = n^{\underline k} = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\text{ factors}} = \frac{n!}{(n-k)!} $$


5

Divide $128$ items in half, and assign one half a $1$ bit in the first digit and the other a $0$ bit. Then divide each half in half again, and in each half assign one half a $1$ bit in the second digit and the other a $0$ bit. Continue until the halves consist of single elements. Now each element has been assigned a binary number from $0$ to $127$. The left-...


5

It is simple algebraicly. If we plug in the standard formula $\binom{n}{r} = \frac{n!}{r! (n-r)!}$, then we have \begin{align*} &\binom{128}{64} \binom{64}{32}^2 \binom{32}{16}^4 \binom{16}{8}^8 \binom{8}{4}^{16} \binom{4}{2}^{32} \binom{2}{1}^{64} \\[8pt] = {} & \left(\frac{128!}{64!^2}\right) \left(\frac{64!}{32!^2}\right)^2 \left(\frac{32!}{...


4

Add two more black balls, glue a black ball to either side of each white ball, choose $m$ spots for the glued blocks among the resulting $m+n-m+2-2m=n-2m+2$ objects in $\binom{n-2m+2}m$ different ways and remove the two outermost black balls.


3

You missed $\pmatrix{0&1\\1&0}$ in the $n=2$ case, so the correct count in that case is $10$. To find the count for $n=3$, first count the matrices without identical rows: There are $8\cdot7\cdot6$. Then count the matrices without identical rows but with identical columns. Say the first two columns are identical. Then there are four different ...


2

Let $x_0,x_1,\dots,x_m$ represent the number of black balls between the respective white balls. Specifically, $x_0$ is the number of black balls to the left of the first white ball. $x_1$ is the number of black balls between the first and second white ball, etc... $\underbrace{\bullet}_{x_0}\circ\underbrace{\bullet\bullet\bullet}_{x_1}\circ\underbrace{\...


1

If the number of vertices is even, say $2m$, we may label any vertex with an element of $\mathbb{Z}/(2m\mathbb{Z})$ and draw and edge between two vertices iff the difference between their labels lies in $\{1,3,5,\ldots,2m-1\}$. In such a way we have a $m$-regular graph with exactly $m^2$ edges and no triangle, essentially because the sum of three odd ...


1

Analytic properties of generating functions gives all kinds of information about asymptotic analysis of counting patterns. Check out this book for some specific ideas.


1

Make $m$ boxes as shown below (note the "short" last box ) $\boxed{\circ\bullet\bullet}\;\boxed{\circ\bullet\bullet}\;\boxed{\circ\bullet\bullet} ......... \boxed{\circ}$ Total objects have reduced to $n -2(m-1) = n-2m+2$ Place the boxes among them in $\binom{n-2m+2}{m}$ ways with the "short" box last


1

There must be at least two black balls after each of the first $m - 1$ white balls in the row, so the answer is zero unless $n - m \geq 2(m - 1) \implies n \geq 3m - 2$. Method 1: Set aside $2(m - 1) = 2m - 2$ black balls. That leaves us with $m$ white balls and $n - m - (2m - 2) = n - 3m + 2$ black balls to arrange. Choose $m$ of the $m + n - 3m + 2 = ...


1

This isn't a complete answer (no upper bounds), but some more general constructions and remarks that make it too long for a comment. As joriki pointed out, we can assume $n \ge 2k$. The first construction is due to Aravind (see the comment above). Suppose $n = qk + r$, $q \ge 2$ and $1 \le r \le k-1$ (if $r = 0$, then $k | n$, and then we know there can ...



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