Articles of combinatorics

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$ […]

Solution to a recurrence relation

Set $F_k(x) := \sum_{n\geq k} S(n,k)x^n$. Prove that $$F_1(x) = \frac{x}{1-x}, \space \space \space F_2(x) = \frac{x^2}{(1-x)(1-2x)} $$ Furthermore, show that the function $F_k(x)$ satisfy the recurrence relation $$F_k(x) = \frac{x}{1-kx}F_{k-1}(x)$$ and solve this recurrence. Any ideas how to approach this problem?

Counting Set Partitions with Constraints

I’m trying to count set partitions under the following constraints: The number of partitions on $n$ elements where the largest cell(s) have exactly $k$ elements All cells have at least two elements Starting here, I’m able to get the number of partitions where the maximum size cell size is exactly $k$ for values of $k […]

Make up a reasonable definition for the bipartite complement of a bipartite graph

I am shooting from the hip here and seeing what sticks. I tried this definition below which I am not sure works. If it doesn’t, please, suggest more accurate definitions. The reason I need this is that I want to be able to replace the degrees in $(4,3,3,3,3,3,3,2,2)$ (which is a degree sequence of a […]