Articles of combinatorics

Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?

Can this identity be derived from the binomial theorem? $$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$ I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it by $4$ in order to get $2^{n-2}$.

A difference between a roller coaster and a ferris wheel.

A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. In how many ways can the ride begin? What if a certain two people want to sit in different cars? Every person can pick a seat. So there is 20! […]

Solving a combintorical problem using generating function

In how many ways $n$ balls can be divided into groups where each group may contain only one ball or two. Each ball can be a singleton, or coupled with one of the $n-1$ options. Hence, $a_0 = 1$ $a_1 = 1$ $a_n = a_{n-1} + (n-1)a_{n-2}$ The correspond generating function: $$F(x) = 1 + […]

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I’m trying to find the largest number $n \in \left\{1,\, \ldots,\, 75 \right\}$ such that this statement is true: There is a collection […]

License plate consisting of 4 letters and 4 numbers

While doing homework today, the following question popped into my head: Can you easily calculate the amount of unique license plates consisting of 4 letters and 4 numbers in any order? It doesn’t seem to be easily possibly; $$ 26^3 * 10^3 * 8! $$ would include repeats (such as AAA123 and AAA123; As are […]

Number of isomorphism classes of a tree on n vertices

I’m currently trying to solve this problem: “Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$.” I’m pretty stumped to be honest. I know of Cayley’s formula; there are $n^{n-2}$ trees on n labelled vertices, so I’m guessing that this may come in handy. One idea I had […]

Prove the number of red sides are always larger than $\frac{n^{2}-2n}{2}$

Every sides and diagonals of a polygon (n-sided) are colored by red or blue. If there are no triangle that all it’s sides are colored by blue, prove the number of red sides are always larger than $\frac{n^{2}-2n}{4}$ My idea is define the number of red sides and blue sides are x,y and use Pigeonhole […]

Two opposite cells have same color for arbitrary-sized board

We color the cells a $4n\times 4n$ board ($n\geq 1$) in black and white. What is the maximum number of “rectangles”, i.e. four cells that together form a rectangle with sides parallel to the sides of the board, such that the two cells in the opposite corner have one color and the other two cells […]

Counting permutations of binary string where all ones within some distance?

Given a binary string consisting of $O$ ones and $Z$ zeros, I’d like to count the number of permutations of that string where all of the ones are within a window (consecutive positions) of length $L$. For example, with 5 ones and 6 zeros, there are 81 permutations where the ones are all within $l=7$ […]

Derivative of a product $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2 +…+z^{i-1}}{i} $

If $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2 +…+z^{i-1}}{i} $ would i) $P_{x_n}'(z)=\sum_{i=1}^n(\prod_{j\neq i}\frac{1+z+…+z^{j-1}}{j})(\frac{1+2z+3z^2+…(i-1)z^{i-2}}{i})$ or ii) $P_{x_n}'(z)=\sum_{i=1}^n(\prod_{j = i}\frac{1+z+…+z^{j-1}}{i})(\frac{1+2z+3z^2+…(i-1)z^{i-2}}{i})$ I’m trying to make sense of my lectures notes, any help would be appreciated. I have worked it out as i) because using the product rule, the choose term differentiated in the product to be the i’th term, so it […]