Articles of combinatorics

Counting chair arrangements with multiple gaps

This question asked how many ways there are to seat $m$ people in a line of $n$ chairs so that no two sit next to each other. I was wondering about a generalization: how many ways are there to place $m$ people in $n$ chairs so that each of them are separated by at least […]

A binary sequence graph

Define a graph $H(n, 2)$ as follows. Each vertex corresponds to a length $n$ binary sequence and two vertices are adjacent if and only if they differ in exactly two positions. I want to find three things. (1) The number of vertices (2) The degree of each vertex in this graph (3) The number of […]

Number of positive integral solutions to $x+y+z+w=20$ with $x<y<z<w$ and $x,y,z,w\geq1\;?$

What is the number of positive unequal integral solution of the equation $x+y+z+w=20$, if $\,x<y<z<w\,$ and $\,x,y,z,w\ge1\;?$ How to solve this question?

Find a closed formula for $\sum_{n=1}^\infty nx^{n-1}$

This question already has an answer here: Evaluate $\sum_{n=1}^\infty nx^{n-1}$ 2 answers

Proving binomial coefficients identity: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$

This question already has an answer here: Proving a combinatorics equality: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$ 2 answers

Proof related to Fibonacci sequence

Could anyone help me with this problem? $$ \sum_{j=0}^{n}\binom{n}{j}F_{n+1-j}= F_{2n+1} $$ I used induction and was able to get to this: $$ 2\sum_{j=0}^{n}\binom{n}{j}F_{n-j}= F_{2n} $$ However I still do not know how to prove the second equality. Really appreciate any help

Rubik's cube and counting

Inspired by this question, I formulate the following: Suppose I have a $3\times3\times3$ Rubik’s cube, call each small square on the surface a piece, there are then $3*3*6 = 54$ pieces. Enumerate the 54 pieces by $[54]:=\{1,2,\cdots,54\}$. Given a permutation $\sigma$ of $[54]$, for every $k\in [54]$ we replace the piece numbered by $k$ with […]

Permutation isomorphic subgroups of $S_n$ are conjugate

Consider $G,H \leq S_n$ and their natural action on $[n] = \{1,\ldots,n\}.$ We say that $G$ and $H$ are permutation isomorphic if there is a bijection $\varphi:[n] \mapsto [n]$ and group isomorphism $f:G \mapsto H$ so that $$\varphi(g(o)) = f(g) (\varphi(o))$$ or in the standard notation involving group actions $\varphi(o^g) = \varphi(o)^{f(g)}.$ I would like […]

Generating function: Probability regarding coin toss

If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of six (or more) consecutive heads occur? Wasn’t sure how to approach this and am quite positive my generating function is incorrect. My attempted work: Consider $e_H,e_T$ s.t $e_H$ denotes the number of times our coin lands […]

Prove that $\binom{m+n}{m}=\sum\limits_{i=0}^m \binom{m}{i}\binom{n}{i}$

I need to proof this following equality : $$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$ This is what I did combinatoric proof: Left : subset with $m$ members from $m+n$ Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$ […]