Articles of combinatorics

One-to-One correspondence in Counting

I have a confusion on the one-to-one correspondence in combinatorics. Take the problem: In how many ways may five people be seated in a row of twenty chairs given that no two people may sit next to one another? Take the solution: Solution for Example: Consider some arrangement of the five people as specified, then […]

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n – 1$ corners of that hypercube and highlight all $(n – 2)$ dimensional elements that originate from each of the corners is it possible to cover all the $(n – 2)$ dimensional faces of the cube? Also, is it ever possible to cover all the […]

Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s

Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$’s or $2$’s. The solution is $$ a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1 $$ I’ve thought about this for quite some time and I can’t really understand it. I feel like I’m making up my […]

In how many ways can these people be arranged for a photograph?

Jessie and Casey are getting married. In how many ways can a photographer at their wedding arrange 6 people in a row from a group of 10 people, where the spouses are among these 10 people, if both spouses must be in the picture? My Attempt We are looking at $6$ seats, and $2$ of […]

Proving an Combination formula $ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$

This question already has an answer here: Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$ 11 answers

Is there a name for this type of permutation?

Let $J$ be a permutation of the first $N$ integers (1, 2, …, $N$), so that the permuted sequence reads $(J(1),J(2),…,J(N))$. The function $J$ must of course be a bijection. Additionally, suppose that $J$ is its own inverse: $J(J(i))=i$, and that $J$ has, at most, one fixed point. That is, there is either none or […]

Number of partial functions between two sets

The number of partial functions $A \rightarrow B$ is $(1+|B|)^{|A|}.$ Now either this is a well-known formula, or I just made a mistake in the proof I just wrote. Which is it?

How many numbers from $1$ to $99999$ have a digit-sum of $8$?

How many numbers from $1$ to $99999$ have a digit-sum of $8$? Why is the answer ${8+4\choose 4}$? Does the following method work? Answer is the number of ways to split 8 into 5 digits, i.e. number of ways to insert 4 lines among a row of 8 objects.

Division of items into groups

The book i’m reading says the following : Number of ways in which $(m+n+p)$ items can be distributed into $m$, $n$ and $p$ sized groups is $$\frac{(m+n+p)!}{m!n!p!}$$ I understand this is called the book-keeper’s rule. So, following from this, if m=n=p, then this formula should become $$\frac{(3n)!}{(n!)^3}$$ Generalising, if we have m groups of n […]

How find this $a_{1}+a_{2}+\cdots+a_{500}=b_{1}+b_{2}+\cdots+b_{500}$?

Let $A=\{1^2,2^2,3^2,\cdots,1000^2\}$. How to prove : There exist $A_{1}=\{a_{1},a_{2},a_{3},\cdots,a_{500}\}\subset A$, $A_{2}=\{b_{1},b_{2},\cdots,b_{500}\}\subset A$, such that $A_{1}\bigcup A_{2}=A,A_{1}\bigcap A_{2}=\varnothing$, and $a_{1}+a_{2}+\cdots+a_{500}=b_{1}+b_{2}+\cdots+b_{500}$ ?