Articles of combinatorics

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

How many ways are there to arrange the letters in the word “mississippi” such that all “p” precede all “i”?

How many ways are there to arrange the letters in the word “mississippi” such that all “p” precedes all “i”? My possible solution: Consider: p p _ _ _ _ _ _ _ _ _ so 9! ways to arrange words(?) follwed by: p _ p _ _ _ _ _ _ _ _ where […]

Counting number of $k$-sequences

I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression. Formally I call a k-sequence $x_1<x_2<\cdots< x_k$ a weak arithmetic progression (WAP) if $\exists d\in \mathbb{N}$ such that $x_{i+1}-x_i\in\{1,d\}$. Now given two natural numbers $n\ge k\ge 1$, I wish to count the number of WAP’s […]

Number of non-negative solutions of an equation with restrictions

Q: Find the number of non-negative solutions of the equation $$r_1+r_2+r_3+\ldots +r_{2n+1}=R$$ when $0 \le r_i \le \min(N,R)$ and $0\le R\le (2n+1)N$. My Attempt: I tried the stars and bars method but it did not work properly. If the upper-bound for $r_i$ was not there, then the answer would have been $\binom{2n+1+R-1}{R}=\binom{2n+R}{R}$. But how do […]