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)

34
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 ...
23
votes
9answers
1k 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. ...
29
votes
7answers
3k 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 ...
28
votes
4answers
3k 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$, ...
7
votes
3answers
583 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 not ...
9
votes
6answers
4k 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 ...
7
votes
1answer
795 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 ...
11
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
898 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?
7
votes
5answers
3k 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= ...
2
votes
3answers
2k 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., ...
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? ...
5
votes
3answers
546 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 ...
19
votes
2answers
1k 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 ...
11
votes
1answer
2k 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 ...
9
votes
4answers
2k views

The generating function for the Fibonacci numbers

$$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\}$. Please HELP. Thanks guys.
2
votes
3answers
582 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$. ...
24
votes
2answers
3k 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 ...
4
votes
2answers
2k 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 ...
11
votes
3answers
3k 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?
4
votes
2answers
1k 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 ...
2
votes
5answers
871 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 ...
4
votes
5answers
5k 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 ...
15
votes
2answers
678 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 ...
15
votes
5answers
12k 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 ...
3
votes
2answers
353 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 ...
4
votes
3answers
663 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 | ...
25
votes
7answers
10k 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. ...
11
votes
3answers
733 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$ ...
11
votes
1answer
6k 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 ...
7
votes
2answers
476 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
5answers
644 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.
6
votes
4answers
518 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: ...
7
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
671 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. ...
4
votes
4answers
15k 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 ...
3
votes
2answers
6k views

Unique ways to keep N balls into K Boxes?

How many unique ways I can keep N balls into K boxes, where each box should atleast contain ...
4
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 ...
3
votes
5answers
219 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
2
votes
1answer
302 views

How can I determine the number of unique hands of size H for a given deck of cards?

I'm working on a card game, which uses a non-standard deck of cards. Since I'm still tweaking the layout of the deck, I've been using variables as follows: Hand size: $H$ Number of suits: $S$ Number ...
3
votes
6answers
187 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 ...
3
votes
1answer
2k views

How can I find the number of the shortest paths between two points on a 2D lattice grid?

How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this? Eg. The shortest path between ...
60
votes
2answers
4k views

More than 99% of groups of order less than 2000 are of order 1024?

In Algebra: Chapter 0, the author made a remark (footnote on page 82), saying that more than 99% of groups of order less than 2000 are of order 1024. Is this for real? How can one deduce this result? ...
82
votes
3answers
11k 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 4-set ...
23
votes
6answers
1k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 1$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta. Note: I put the tag "linear ...
17
votes
2answers
1k 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 ...
9
votes
1answer
418 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 ...
5
votes
4answers
217 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 ...
4
votes
2answers
1k 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
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 ...