5
votes
6answers
185 views

The physical meaning of ${n \choose k} = {n \choose n-k}$.

They say that $${n \choose k}={n \choose n-k}.$$ Can someone explain its physical meaning? Among many problems that use this proof, here is an example: The english alphabet has $26$ letters ...
2
votes
1answer
99 views

How does this amount change if we add to it?

We can iterate over the naturals, with zero included. Here the focus is on the numbers from $0$ to $2^s - 1$, inclusive, in binary. So we have the numbers as: $$0000, 0001, 0010, \dots 1111 \text{ ...
1
vote
3answers
39 views

explanation for a combinatorial identity involving the binomial coefficient

I am looking for an intuitive explanation for the identity: $$\binom{n}{h}\binom{n-h}{k} = \binom{n}{k}\binom{n-k}{h}$$ Thanks!
0
votes
4answers
127 views

Maximizing the Magnitude of the Resultant Vector

Given a set of $n$ two-dimensional unit vectors: $\left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$, I want to find the coefficients $\left\{ \alpha_1, \dots, \alpha_n \right\}$, $0 \leq \alpha_i ...
1
vote
1answer
32 views

Intuition for this explicit formula for the number of ways of putting N labeled balls in K unlabeled boxes?

In its article on "Stirling numbers of the second kind", Wikipedia gives this formula for $S(n, k)$ -- the number of ways of putting $n$ distinct balls into $k$ boxes (where the boxes aren't ...
8
votes
6answers
167 views

Why, conceptually, is it that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$? [duplicate]

Why, conceptually, is it that $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}?$$ I know how to prove that this is true, but I don't understand conceptually why it makes sense.
4
votes
1answer
133 views

Intuition behind the Jacobi triple product

Jacobi's triple product identity states that: $\displaystyle \sum_{n = -\infty}^{\infty}z^{n}q^{n^{2}} = \prod_{n = 1}^{\infty}(1 - q^{2n})(1 + zq^{2n - 1})(1 + z^{-1}q^{2n - 1})$ I've seen a messy ...
1
vote
1answer
49 views

derangements basic practice question 2

This is not HW just a practice question from the text. Q.. (NOTE: I find that both part a and b say the same thing but the answers are different) Ten women attend a business luncheon. Each women ...
1
vote
1answer
101 views

Derangements basic practice question

practice questions not Homework I have problems with this questions that I have answers for but cant understand how the answer was derived. Q.1. In how many ways can the integer $1,2,3,...10$ be ...
8
votes
1answer
244 views

Why is the Derangement Probability so Close to $\frac{1}{e}$?

A derangement is a permutation of $\sigma$ of $\{1,2,3,\dots,n\}$ such that $\sigma(i) \neq i$ for every $i$. A common application of inclusion/exclusion in undergraduate combinatorics and ...
2
votes
1answer
148 views

Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
3
votes
5answers
221 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
-1
votes
1answer
348 views

Multiply two large numbers in under 1000 instructions using reduced ISA with only 7 registers [closed]

Is it possible to multiply two large (15 bit) numbers efficiently (in under 1000 instructions) using the following ISA: ...
3
votes
1answer
405 views

Labeled/unlabeled balls in unlabeled boxes

I was hoping I could receive some clarification into the the four cases: Placing labeled balls in unlabeled boxes with repetition. Placing labeled balls in unlabeled boxes without repetition. ...
2
votes
2answers
3k views

How many ways are there to choose 10 objects from 6 distinct types when…

(a) the objects are ordered and repetition is not allowed? (b) the objects are ordered and repetition is allowed? (c) the objects are unordered and repetition is not allowed? (d) the objects are ...
2
votes
4answers
294 views

Variance of binomial distribution

Why for $X\sim B(n,p)$ is $Var(X)=np(1-p)$? $Var(X)=\sum x_i^2 p_i -(\sum x_i p_i)^2=\sum_{r=0}^n r^2 \binom{n}{r}p^r(1-p)^{n-r}+( \sum_{r=0}^n r \binom{n}{r}p^r(1-p)^{n-r} )^2$ In my ...
0
votes
6answers
1k views

Combinatorial proofs: having a difficult time understanding how to write them out

Can someone explain how combinatorial proofs work? I've included an example questions that's been giving me a hard time. Any insight on the topic would be great. $$\sum_{k=1}^{n}k{n \choose k} = ...
0
votes
1answer
359 views

Multiple choice questions on relations and some of their properties

I'm confused about these 3 selected problems. I have the solutions for each, if necessary, but I'm much more interested in understanding the material. If anyone can offer a clear, concise, and ...
1
vote
1answer
69 views

Upcoming exam! Any good sources to learn about counting techniques and discrete probability?

If anyone has a free, online source to contribute for a certain topic/topics, please share! I'm not really looking for an intense theoretical grasp of these topics, just an intuitive understanding of ...
1
vote
3answers
700 views

Trouble understanding equivalence relations and equivalence classes…anyone care to explain?

What exactly are equivalence relations and equivalence classes? The latter is giving me the most trouble; I've tried to read multiple sources online but it just keeps going over my head. Example ...
1
vote
1answer
103 views

Suppose you flip a weighted coin…

Suppose you flip a weighted coin that is $3$ times more likely to come up heads. What is the probability that, if you flip the coin $3$ times, you will get an even number of heads? Can someone help ...
0
votes
1answer
763 views

How many strings of six lowercase letters contain the letters a and b in consecutive positions…

How many strings of six lowercase letters contain the letters a and b in consecutive positions with a preceding b, with all letters distinct? Can someone give me a general method for thinking about ...
3
votes
1answer
142 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
8
votes
3answers
140 views

Seemingly similar but different probability games

Burger King is currently running its "family food" game in which each piece can be modeled as a scratch off game where exactly one of three slots is a winner and you may only scratch one slot as your ...
2
votes
0answers
169 views

Ways to think about the binomial coefficient

Just to sharpen my intuition in combinatorics, I ask you of ways to think about interesting combinatorical quantities and expressions like the binomial coefficient, for example, for the binomial ...
4
votes
2answers
1k views

How is Leibniz's rule for the derivative of a product related to the binomial formula? [duplicate]

Possible Duplicate: “Binomial theorem”-like identities The binomial formula describes the expansion of the $n$th power of the sum $(a+b)$: $$(a+b)^n = \sum_{k = 0}^n {n\choose ...
3
votes
1answer
356 views

Combinatorial interpretation of Delannoy numbers formula

The Delannoy number $D(a,b)$ can be defined as the numbers of paths on $\mathbb Z^2$ from $(0,0)$ to $(a,b)$ using only steps $(0,1)$, $(1,0)$ and $(1,1)$. It is straightforward to see that they ...
2
votes
1answer
113 views

How does this image prove the identity $1+2+3+4\cdots + (n-1) = \binom{n}{2}$? [duplicate]

Possible Duplicate: Proof for formula for sum of sequence 1+2+3+…+n? Proof without words: $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $ How ...
2
votes
3answers
338 views

How many different combinations of $X$ sweaters can we buy if we have $Y$ colors to choose from?

How many different combinations of $X$ sweaters can we buy if we have $Y$ colors to choose from? According to my teacher the right way to think about this problem is to think of partitioning ...
1
vote
2answers
205 views

Factorials and Combinations

I understand that $$n! = n (n-1) (n-2)\cdots 2 \cdot 1.$$ My book says this can also be written as $$n (n-1)!$$ Without telling me why My question is How and why is that? Why can't we leave it as it ...
4
votes
1answer
352 views

Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements

Let $X$ be the set of natural numbers $k_i$, $k_i \geq 1$, with the property that at least one of the equations $p_i = $6$ k_i \pm 1$ gives the $i$-th prime number (disregarding $2$ and $3$), and ...
3
votes
1answer
133 views

Looking for an article on general principles of discrete mathematics

In his article 2 cultures Timothy Gowers states that the structure in combinatorics is there in the form of somewhat vague general statements that allow proofs to be condensed in the mind, and ...
4
votes
2answers
190 views

Counting and Ordering of Numbers

Are there differences between 'counting' and 'ordering'? As such, the whole of rational number is countable, or they order-able too? In what cases counting and ordering are same or not?
8
votes
0answers
472 views

Combinatorial reasoning for the identity $\left ( \sum_{i=1}^n i \right )^2 = \left ( \sum_{i=1}^n i^3 \right ) $ [duplicate]

Possible Duplicate: Intuitive explanation for the identity $\sum\limits_{k=1}^n {k^3} = \left(\sum\limits_{k=1}^n k\right)^2$ There is the interesting identity: $$\left ( \sum_{i=1}^n i ...