Articles of combinatorics

Simplification of $\binom{50}{0}\binom{50}{1}+\binom{50}{1}\binom{50}{2}+\cdots+\binom{50}{49}\binom{50}{50}$

$$\binom{50}{0}\binom{50}{1}+\binom{50}{1}\binom{50}{2}+\cdots+\binom{50}{49}\binom{50}{50}$$ The above sequence amounts to one of the following options: $\binom{100}{50}$ $\binom{100}{51}$ $\binom{50}{25}$ $\binom{50}{25}^2$

From a bag containing $10$ pairs of socks, how many must a person pull out to ensure that they get at least $2$ matching pairs of socks?

There are $10$ pairs of socks in bag. What is the minimum number of socks that a person should pull out from the bag to ensure that they get at least $2$ matching pairs of socks.

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we’re given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise disjoint. I’m wondering how we can show 3-dimensional matching $\le_p$ exact cover. Given an instance of the 3-dimensional […]

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7 \times 1$ […]

Counting number of sequences under cyclic permutation

If I have say $2$ A matrices, $2$ B matrices and $1$ C matrix then I would like to know how many distinct traces of products of all of them can be formed. Assume that $A$, $B$ and $C$ don’t commute with each other. Like $AABBC$, $CAABB$ and $BCAAB$ are distinct products which will have […]

Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?

For example , I am trying to count combinations like [1,6,14,21,27] because the minimum difference between two sequential integers in the combination is 5 and the maximum distance is 8, but I don’t want to count combinations like [2,4,9,16,25] because the smallest difference between the sorted numbers is 2 (too small) or combinations like [5,30,35,41,48] […]

An identity for Bernoulli numbers

Denote by $B_n$ the Bernoulli sequence (defined by the exponential generating function $\frac{x}{e^x-1}=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n$). As we know $$ \sum^{n}_{j=0}\binom{n}{j}B_j=B_n\; ; \; n\geq 2 $$ what about $\sum^{n}_{j=0}(-1)^j\binom{n}{j}B_j$, and as a more general case $$ \sum^{n}_{j=0}\frac{(-1)^{j+1-k}}{j+1}\binom{n}{j}\binom{j+1}{k}B_{j+1-k} $$ where $k$ is a given integer such that $1\leq k\leq n+1$ (is there any similar identity?). Note that putting $k=1$ […]

Universal algorithm to estimate probability of drawing certain combination of coloured balls

I am writing AI for a board game and would be happy for some guidance in creating the function to calculate probabilities. So, there’s a pool of N coloured balls. Up to 7 colours, the quantity of balls in each colour is given (zero or more). We are about to draw M balls from there. […]

Number of subsets of a set $S$ of n elements , is $2^n$

This question already has an answer here: The number of subsets of a set of cardinality $n$ 3 answers Count subsets of an i-set in two ways 2 answers

Give a Combinatorial proof to show $\sum_{i=1}^{n}{iC(n,i)}=n2^{n-1}$

I am completely lost on how to achieve this. I have no idea where to start, nor do I know what to use to find to prove this problem. Can someone help me with this?