Articles of combinatorics

N.Alon, J.Spencer Probabilistic methods problem ch. $4$ problem $5$

Let $v_1=(x_1,y_1),…,v_n=(x_n,y_n)$ be $n$ two dimensional vectors where each $x_i$ and each $y_i$ is an integer whose absolute value does not exceed $2^{n/2}/(100 \sqrt{n})$. Show that there are two disjoint sets $I,J \subset \{ 1,2,…,n\}\ $ such that $ \ \ \sum \limits_{i \in I} v_i = \sum \limits_{j \in J} v_j$ I tried to […]

How many one to one and onto functions are there between two finite sets?

Suppose $X$ has $N$ elements and $Y$ has $M$ elements. How many one to one function are there from $X$ to $Y$? How many onto function are there from $X$ to $Y$? The number of one to one functions is $N!$, because the max mapping to $Y$ is $N$. The number of onto functions is […]

Check my answer: A slight modification to the 'hat-check' problem.

Suppose $n$ (hat wearing) people attended a meeting. Afterwards, everyone took a hat at random. On the way home, there is a probability $p$ that a person loses their hat (independent of whether other people did). What’s the probability that nobody got home with their own hat? First of all, I’m not sure if I […]

“Probability” of a map being surjective

What is the probability of randomly putting $n$ elements into $k$ boxes ($k\leq n$) such that there is no empty box? I have two different ideas: I could use the principle of inclusions and exclusions with $A_i=\{\text{box $i$ is empty}\}$: \begin{align}P(\text{no empty boxes})&=1-P\left(\bigcup_{i=1}^k A_i\right)=1-\sum_{i=1}^{k-1} (-1)^{k-1} \binom{k}{i}\left(\frac{k-i}{k}\right)^n\\&=\sum_{i=0}^{k-1}(-1)^k\binom{k}{i}\left(\frac{k-i}{k}\right)^n\end{align} There are $\binom{n+k-1}{k-1}$ different ways of putting $n$ elements […]

What do we call well-founded posets whose elements have a unique height?

What do we call those well-founded posets $P$ with the property that for every $x \in P$, all maximal chains in the lowerset generated by $x$ have the same length? Examples: The set of all finite subsets of a (possibly infinite) set. The set of all finite-dimensional vector subspaces of a (possibly infinite-dimensional) vector space. […]

Number of positive integers $\le n$ with different digits.

An integer $m$ is acceptable iff in it’s decimal representation all digits are different. For example $9876543210$ is the largest acceptable integer. For each $n\in \Bbb N$, $\theta(n)$ is the number of all acceptable positive integers not greater than $n$. Is there a simple formula for $\theta(n)$?

Calculating probability with n choose k

I’m trying to solve a problem two different ways, and I can’d seem to figure out where I’m going wrong. I have 4 buckets (A,B,C,D), and 4 identical marbles. Each marble has an equal chance of being put in any of the 4 buckets, and each is placed independently (each bucket can have 0-4 marbles […]

How many shapes can one make with $n$ square shaped blocks?

How many possible shapes can one make by rearranging $n$ square shaped blocks, with and without allowing rotational symmetry? For example, for $n = 4$, there are seven possible shapes after discounting rotational symmetry, as in Tetris. How does this number change if one of the blocks is coloured – distinguishable from the rest? For […]

Prove that there are two frogs in one square.

A certain chessboard is infinite in size. There is a frog sitting in the center of every square. After a certain time, all the frogs jump such that They may jump to any possible square in the infinite chessboard They may jump and land at the same square again Prove that its possible for all […]

Counting necklaces with a fixed number of each bead

I want to count the number of necklaces, with $n$ beads in total, where the alphabet of beads is $\{1,\ldots,k\}$, and where the number of beads with color $i$ is $n_i$. For example, if $n=4$, and $n_1 = n_2 = 2$, the following necklaces are the only possible $$1122$$ $$1212$$ I have been able to […]