Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially 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.
6,914
questions
17
votes
4
answers
72k
views
Sum of $k {n \choose k}$ is $n2^{n-1}$
Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.
As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $.
I tried solving this by induction but, in the ...
- 1,324
47
votes
6
answers
78k
views
Expected Value of a Binomial distribution?
If $\mathrm P(X=k)=\binom nkp^k(1-p)^{n-k}$ for a binomial distribution, then from the definition of the expected value
$$\mathrm E(X) = \sum^n_{k=0}k\mathrm P(X=k)=\sum^n_{k=0}k\binom nkp^k(1-p)^{n-k}...
user31280
39
votes
7
answers
67k
views
In how many ways can a number be expressed as a sum of consecutive numbers? [duplicate]
All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ...
- 581
22
votes
16
answers
4k
views
How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$
How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?
I tried using the Snake oil technique but I guess I am applying it incorrectly. With the ...
- 5,528
22
votes
1
answer
3k
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 ...
- 1,041
18
votes
2
answers
14k
views
Inductive Proof for Vandermonde's Identity?
I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical ...
user41419
18
votes
6
answers
26k
views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove that
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
- 2,783
12
votes
5
answers
4k
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 ...
- 6,763
7
votes
1
answer
4k
views
What's the explicit formula for Permutations of Subsets of a Multiset? [duplicate]
What is the number of permutations of subsets of the multiset $S$ with cardinality $n$? A sample problem would be to find the number of ways you can construct "words" with three of the ...
- 138
5
votes
3
answers
3k
views
Give a combinatorial proof: $ n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} $
Find a combinatorial argument for the following binomial identity:
$$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} .$$
Algebraic proofs can be found at Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \...
- 216
5
votes
6
answers
7k
views
Number of occurrences of k consecutive 1's in a binary string of length n (containing only 1's and 0's)
Say a sequence $\{X_1, X_2,\ldots ,X_n\}$ is given, where $X_p$ is either one or zero ($0 < p < n$). How can I determine the number of strings, which do contain at least one occurrence of ...
- 153
20
votes
2
answers
8k
views
Number of monomials of certain degree
Wikipedia says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
- 201
10
votes
2
answers
2k
views
Different Coloring of regular n-gon
By using Burnside's lemma, I want to find the number of different coloring of vertices of a regular n-gon, with X colors.
By "different" I mean : up to rigid motions.
I've seen some partial results, ...
- 234
10
votes
2
answers
10k
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,684
5
votes
2
answers
3k
views
Coupon Collector Problem with Batched Selections
I am trying to solve a variation on the coupon collector's problem.
In this scenario, someone is selecting coupons at random with replacement from n different possible coupons. However, the person is ...
- 51