This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

37
votes
2answers
2k views

Identity for convolution of central binomial coefficients

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
36
votes
4answers
4k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
25
votes
9answers
2k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
32
votes
7answers
5k views

Taking Seats on a Plane

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless Imagine there are a 100 people in line to ...
14
votes
7answers
6k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
10
votes
6answers
5k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ...
8
votes
3answers
724 views

Number of permutations where n ≠ position n

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is ...
5
votes
3answers
3k views

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., ...
12
votes
4answers
1k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
5
votes
3answers
1k views

Enumerating number of solutions to an equation

How do you find the number of solutions like this? $$x_1 + x_2 + x_3 + x_4 = 32$$ where $0 \le x_i \le 10$. What's the generalized approach for it?
8
votes
1answer
1k views

In how many ways can we colour $n$ baskets with $r$ colours?

In how many ways can we colour $n$ baskets using up to $r$ colours such that no two consecutive baskets have the same colour and the first and the last baskets also have different colours? For ...
7
votes
3answers
1k views

Proof of a combinatorial identity: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? ...
7
votes
4answers
660 views

Combinatorial proof

Using notion of derivative of functions from Taylor formula follow that $$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$$ Is there any elementary combinatorial proof of this formula here is my proof for ...
14
votes
2answers
9k views

Combinatorial proof of summation of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible. $$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n ...
20
votes
2answers
2k views

How to reverse the $n$ choose $k$ formula?

If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below: $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$ What if I want to go the ...
12
votes
4answers
6k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.
12
votes
1answer
3k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
4
votes
2answers
2k views

Counting number of moves on a grid

Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right ...
25
votes
2answers
4k views

How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that $\displaystyle \sum_{k=0}^{n} {n ...
5
votes
3answers
324 views

Given n $\in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
5
votes
5answers
6k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
2
votes
3answers
661 views

Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$. ...
31
votes
7answers
16k views

How many triangles

I saw this riddle today, it asks how many triangles are in this picture . I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence. ...
6
votes
2answers
3k views

How do I do Combinatorics / Counting?

If someone could give answers and explain, it would be greatly appreciated. Help required studying for a final. One hundred tickets, numbered 1,2,3,…,100, are sold to 100 different people for a ...
4
votes
3answers
1k views

Demonstrate another way to solve the Inclusion–exclusion principle?

I'm attempting to solving the Inclusion–exclusion principle, which is generally described as follows... $$\begin{align} \left| \bigcup\limits_{i=1}^n A_i \right| = + \left( \sum\limits_{i=0}^n | ...
12
votes
3answers
4k views

Combinations of selecting n objects with k different types

Suppose that I am buying cakes for a party. There are k different types and I intend to buy a total of n cakes. How many different combinations of cakes could I possibly bring to the party?
5
votes
2answers
1k views

Derivation of the Partial Derangement (Rencontres numbers) formula

I'm looking for the method by which the partial derangement formula $D_{n,k}$ was derived. I can determine the values for small values of N empirically, but how the general case formula arose still ...
7
votes
2answers
3k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
2
votes
5answers
1k views

How many ways can $b$ balls be distributed in $c$ containers with no more than $n$ balls in any given container?

I think there are $\binom{b+ c - 1}{c-1}$ ways to distribute $b$ balls in $c$ containers. (Please correct me if that's a mistake.) How does this change if I am not allowed to place more than $n$ balls ...
21
votes
6answers
20k views

Combination of smartphones' pattern password

Have you ever seen this interface? Nowadays, it is used for locking smartphones. If you haven't, here is a short video on it. The rules for creating a pattern is as follows. We must use ...
16
votes
2answers
774 views

What's the General Expression For Probability of a Failed Gift Exchange Draw

My family does a gift exchange every year at Christmas. There are five couples and we draw names from a hat. If a person draws their own name, or the name of their spouse, all the names go back in a ...
5
votes
4answers
245 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
3
votes
2answers
397 views

What is the probability that $x_1+x_2+…+x_n \le n$?

Given that $X_1, X_2...$ are mutually independent random variables. For each $i$ with $1\le i \le n$ the variable $X_i$ is equal to either $0$ or $n+1$ $E(X_i)$ = $1$ also.. if $X_i$ is equal to ...
10
votes
3answers
355 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
5
votes
5answers
25k views

Number of ways of distributing n identical objects among r groups

I came across this formula in a list: The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects I know that standard way ...
2
votes
2answers
922 views

An efficient method for computing the number of submultisets of size n, of a given multiset

There are a number of ways to describe this problem. I shall name a few. Submultisets Let $(M, f)$ be a multiset where $M = {x_1, ... x_k}, |M| = k$ and $f(x_i) = m_i$, i ranging from 0 to k ...
3
votes
6answers
237 views

Probability problem

I have $3$ coins, $1$ coin has $2$ heads (HH), 1 coin has $2$ tails (TT), $1$ coin has $1$ head and $1$ tail (HT). I toss the coin, it fells on my hand, and the side i see is a tail. What's the chance ...
2
votes
5answers
393 views

Finding generating function for the recurrence $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$

I am trying to find generating function for the recurrence: $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$. It looks like this: $a_0 = 1$ $a_1 = {1 \choose 2} + 3$ $a_2 = {2 ...
109
votes
3answers
15k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete ...
15
votes
1answer
608 views

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 ...
19
votes
2answers
2k views

Expected number of rolling a pair of dice to generate all possible sums

A pair of dice is rolled repeatedly until each outcome (2 through 12) has occurred at least once. What is the expected number of rolls necessary for this to occur? Notes: This is not very deep ...
12
votes
2answers
853 views

Is the Ratio of Associative Binary Operations to All Binary Operations on a Set of $n$ Elements Generally Small?

I started thinking about the number of associative (binary) operations on a set with $n$ elements today. Looking online I found this paper which indicates only $113$ of the possible $19,683$ ...
10
votes
2answers
2k views

Circular permutations with indistinguishable objects

Given n distinct objects, there are n! permutations of the objects and n!/n "circular permutations" of the objects (orientation of the circle matters, but there is no starting point, so 1234 and 2341 ...
5
votes
3answers
885 views

The number of subsets of a set of cardinality $n$

Please help with this question. Show that for a finite set $A$ of cardinality $n$, the cardinality of P(A) is $2^n$, where $P(A)$ is the power set of $A$. Thank you in advance for any help that is ...
8
votes
5answers
753 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
7
votes
2answers
545 views

Lines in the plane and recurrence relation

I am trying to solve the following problem from Cohen's Basic Techniques of Combinatorial Theory: A collection of $n$ lines in the plane are are said to be in general position if no two are ...
7
votes
4answers
594 views

Why does this expected value simplify as shown?

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is: ...
5
votes
3answers
2k views

How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?

I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice. I've spent quite ...
9
votes
3answers
2k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
5
votes
2answers
859 views

Number of combinations with repetitions (Constrained)

I would like to calculate the number of integral solutions to the equation $$x_1 + x_2 + \cdots + x_n = k$$ where $$a_1 \le x_1 \le b_1, a_2 \le x_2 \le b_2, a_3 \le x_3 \le b_3$$ and so on. ...