Articles of combinatorics

Prove that the combination formula can be reduced to…

Prove that: $$\frac{m!}{k!(m-k)!} = \frac{m}{k}\frac{m-1}{k-1}\cdots\frac{m-k+1}{1}$$ It’s quite obvious when I write down some terms, but I just don’t know how to make a rigorous proof. Any hints or help are appreciated! Thanks.

An Identity Involving Narayana Numbers

Let $N(n,m)$ denote the Narayana number defined by $$N(n,m)=\frac{1}{n}{n\choose m}{n\choose m-1}.$$ Let $$A(n,k,\ell)=\sum_{\substack{i_0+i_1+\cdots+i_k=n\\ j_0+j_1+\cdots+j_k=\ell}}\,\prod_{t=0}^kN(i_t,j_t+1),$$ where the sum ranges over all compositions $(i_0,i_1,\ldots,i_k)$ of $n$ into exactly $k+1$ parts and all weak compositions $(j_0,j_1,\ldots,j_k)$ of $\ell$ into exactly $k+1$ parts. From numerical evidence, I have conjectured that $$A(n,k,\ell)=\frac{k+1}{n}{n\choose \ell}{n\choose \ell+k+1}.$$ This seems like a simple enough […]

Use PIE to count the number of $6$-multisets of $$ in which no digit occurs more than twice.

This is one of a set of several problems in my book I am having difficulty not just solving, but also understanding the provided solutions. The given answer is $462 – 336 + 15 = 141.$ I’ll try and see where the terms of the equality above come from. $[6] = \{1, 2, 3, 4, […]

Probability of collecting all 4 different items while picking 1 random item from the set

a.) There are $4$ distinct items in the set. What is the probability of picking all $4$ items after picking $n\ge4$. b.) How many items do you need to pick to collect all four with a probability of at least $.9$. My answer for part a. (which I think is wrong): The sample space is […]

Numbers fulfilling a certain condition in a range of numbers

A year is a leap year if it is either (i) a multiple of 4 but not a multiple of 100, or (ii) a multiple of 400. For example, 1600 and 1924 were leap years while 2200 will not be. Find the number of leap years between 1000 and 3000 inclusive. I’m not sure what’s […]

Probability that team $A$ has more points than team $B$

Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a $50\%$ chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The […]

Roll 6 dice, find the number of outcomes with 3 distinct numbers.

Suppose you roll six dice, how many outcomes are there with 3 distinct numbers. My attempt: First there are ${6 \choose 3}$ ways to choose these 3 distinct numbers. We consider 3 cases; Case 1: 3 pars of repeated numbers e.g. $223344$. There are ${3\choose 3}$ choices for the values, and for the ordering there […]

Show that ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$

This question already has an answer here: Evaluating even binomial coefficients 5 answers Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$ 7 answers

Number of divisiors of $n$ less than $m$

I’m looking for a closed- or alternative-form of the function that counts the number of divisors of an integer $n$ that are less than some integer $m$ (interested in $m < n$, obviously): $ \sigma_0(n,m) = \sum_{d|n,d<m} 1 $. Or more generally: $ \sigma_x(n,m) = \sum_{d|n,d<m} d^x $. Or any important property of either (like […]

Counting Number of k-tuples

Let $A = \{a_1, \dots, a_n\}$ be a collection of distinct elements and let $S$ denote the collection all $k$-tuples $(a_{i_1}, \dots a_{i_k})$ where $i_1, \dots i_k$ is an increasing sequence of numbers from the set $\{1, \dots n \}$. How can one prove rigorously, and from first principles, that the number of elements in […]