1
vote
0answers
35 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
30 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
108 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
24 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
146 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.
3
votes
1answer
111 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
46 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
95 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
219 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
141 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
209 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
321 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
362 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
2k 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
262 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
931 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
332 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
65 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
621 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
101 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
670 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
126 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
133 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
165 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
334 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
110 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
326 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
198 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
351 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
131 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
468 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 ...