Articles of combinatorics

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can’t understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., $[x]$ is the integer nearest to $x$). This equation that I wrote comes from solving the following recursion, but I don’t understand how exactly did the author calculate this recursion […]

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s – total $kn$ cards.

Find the number of arrangements of $k \mbox{ }1’$s, $k \mbox{ }2’$s, $\cdots, k \mbox{ }n’$s – total $kn$ cards – so that no same numbers appear consecutively. For $k=2$ we can compute it by using the PIE, and it is $$\frac{1}{2^n} \sum_{i=0}^n (-1)^i \binom{n}{i} (2n-i)! 2^i$$

Restricted Compositions

Number Composition studies the number ways of compositing a number. I wanna know the number of compositions of $m$ with $n$ parts with the size of the max part equal to or less than $k$. Is there a closed form for this problem?

Can this be counted with stars and bars method?

If I have a $w \times h$ matrix where each value is an integer $1 \lt n \lt 20$, how can I count the number of distinct configurations, where $2$ configurations are “distinct” if there is no way to reshuffle the rows and columns that would produce the same matrix? for example these are equal […]

Consecutive birthdays probability

Let $n$ be a number of people. At least two of them may be born on the same day of the year with probability: $$1-\prod_{i=0}^{n-1} \frac{365-i}{365}$$ But what is the probability that at least two of them are born on two consecutive days of the year (considering December 31st and January 1st also consecutive)? It […]

Why there are $11$ non-isomorphic graphs of order $4$?

I’m new to graph theory and I don’t plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can’t see why. I know that the most naive approach is that I can use brute force and draw four vertices and then […]

How many integer solutions to a linear combination, with restrictions?

I’ve already done a few problems such as this, other problems where I’m supposed to find the number of combinations or permutations, subject to certain restrictions. Here’s been my basic strategy: Find $A$ = the number of total solutions (combinations) were there no restrictions. Find $B$ = the number of illegal solutions (solutions that violate […]

What combinatorial quantity the tetration of two natural numbers represents?

Tetration is a generalization of exponentiation in arithmetic and a part of a series of other generalized notions, Hyperoperators. Consider $m\uparrow n$ denotes the tetration of $m$ and $n$. i.e. $$\underbrace{m^{m^{m^{.^{.^{.^{m}}}}}}}_{n-times}$$ Note that one can find a combinatorial description of each one of operators sum, multiplication and exponentiation as follows: $m+n$ is the size of […]

Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$

I can’t figure out an algebraic proof for the following identity: $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$ Combinatorical solution: We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total. Or we could just choose $k$ from the union.

Stars and bars with restriction of size between bars via generating functions.

I would like to know a way to solve the problem. How can we divide n identical marbles into k distinct with each pile having at most w marbles. I have seen a solution due to Brian Scott on the problem using inclusion-exclusion but I would like one via generating functions. In particular how can […]