I got distracted by DeanK22's question.

We define a committee as a nonempty set of people.
We then create the roles which can be taken by committee members of president and secretary.

These are not necessarily distinct people. So we can have 1 person on a committee on their own, as both the president and secretary.

EDIT: I probably should have said "How many ways to pick a committee from a set of people size n..."

Reply 1383

SimonM

Here's a harder question to dispatch using the calculus method:

\displaystyle \sum_{k=1}^n \binom{n}{k} \binom{k}{i}

Reply 1384

Aurel-Aqua

SimonM

Here's a harder question to dispatch using the calculus method:

\displaystyle \sum_{k=1}^n \binom{n}{k} \binom{k}{i}

i = ?

Reply 1385

SimonM

Aurel-Aqua

i = ?

i is a positive integer, bruv, cos i izn't lurnin english.

(Damn I wanted to say 'I am')

Reply 1386

Aurel-Aqua

SimonM

i is a positive integer, bruv, cos i izn't lurnin english.

(Damn I wanted to say 'I am')

I'm not sure about definitions: what is

\binom{3}{4}

equal to?

Reply 1387

Oh I Really Don't Care

Aurel-Aqua

I'm not sure about definitions: what is

\binom{3}{4}

equal to?

Is =

Unparseable latex formula:

\displlaystyle \frac{n!}{r!(n-r)!} so with 3 and 4; \frac{3!}{4!(4-3)!}

is how you pick objects that many ways with that anmount of objects3

Reply 1388

Aurel-Aqua

DeanK22

Is =

Unparseable latex formula:

\displlaystyle \frac{n!}{r!(n-r)!} so with 3 and 4; \frac{3!}{4!(4-3)!}

is how you pick objects that many ways with that anmount of objects3

Nevermind my question, it's equal to zero according to Wikipedia. By the way, (n-r) for n = 3, r = 4 is (3-4), not (4-3).

Reply 1389

Oh I Really Don't Care

Aurel-Aqua

Nevermind my question, it's equal to zero according to Wikipedia. By the way, (n-r) for n = 3, r = 4 is (3-4), not (4-3).

typo

Reply 1390

Aurel-Aqua

SimonM

Here's a harder question to dispatch using the calculus method:

\displaystyle \sum_{k=1}^n \binom{n}{k} \binom{k}{i}

I don't see where calculus comes in. We could simply use the fact that:

\displaystyle (1+(1+x))^n = \sum_{k=0}^n \binom{n}{k} \sum_{r=0}^k \binom{k}{r}x^{r} = \sum_{k=0}^n \binom{n}{r} 2^{n-r}x^r

.

Equating coefficients,

\displaystyle 2^{n-r}x^r = \sum_{k=0}^n \binom{n}{k}\binom{k}{r}x^r

.

But since

\displaystyle \binom{n}{0}\binom{0}{r} = 0

, the k = 0 term disappears and thus

\displaystyle \sum_{k=1}^n \binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}

Reply 1391

SimonM

Fairy nuff. Now can you do that using combinatorics?

\binom{3}{4} = 0

Since my last one backfired, how about

\displaystyle \sum_{k=1}^{n} k^5 \binom{n}{k}

Reply 1392

Aurel-Aqua

SimonM

Fairy nuff. Now can you do that using combinatorics?

No.

SimonM

\displaystyle \sum_{k=1}^{n} k^5 \binom{n}{k}

Define

\displaystyle S_{n,r}(x) = \sum_{k=r}^n\frac{k!}{(k-r)!}\binom{n}{k}x^{k-r} = \frac{\mathrm{d}^r}{\mathrm{d} x^r} (1+x)^n = \frac{n!}{(n-r)!}(1+x)^{n-r}

.

Define

\displaystyle Q_{n,r}(x) = \sum_{k=0}^n k^r\binom{n}{r}x^r

.

Then we write

S_{n,5}(x)

in terms of lower Qs, and then those Qs in terms of lower S-es, and so on. For example:

S_{n,5}(x) = Q_{n,5}-10Q_{n,4}+35Q_{n,3}-50Q_{n,2}+24Q_{n,1}

After a few substitutions that took me well over an hour, I found that

Q_{n,5}(x) = S_{n,5}(x)+10S_{n,4}(x)+25S_{n,3}(x)+15S_{n,2}(x)+S_{n,1}(x)

.

Expressing by the original definitions, we get:

\displaystyle \sum_{k=1}^{n} k^5 \binom{n}{k} = S_{n,5}(1) = 2^{n-5}(n^5+10n^4+15n^3-10n^2)

.
I tested this for n = 1, n = 2 and n = 3 to be true.

Are there any theorems related to this?

Simon, now it's your turn to write up a combinatorial argument / complete it for this beautiful 5th degree polynomial.

Reply 1393

SimonM

Aurel-Aqua

Are there any theorems related to this?

I doubt it although considering Newton sums might be the most relevant bit of theory

Simon, now it's your turn to write up a combinatorial argument / complete it for this beautiful 5th degree polynomial.

I will after University Challenge

What a final!

Anyway.

We are counting the number of ways to choose a committee from n people, with 5 executive positions.

Summing by increasing the size of our committee, for a committee of size k, there are

\displaystyle \binom{n}{k}

ways to choose a committee and

\displaystyle k^5

ways to arrange them into our executive positions. This is precisely our sum.

Assume we have one dictator, there is n ways to choose our Hitler, and

\displaystyle 2^{n-1}

ways to choose the rest of the committee. This gives us

\displaystyle n 2^{n-1}

Two brave leaders, there is

\displaystyle n \times (n-1)

ways to choose them, so the first guy gets the most jobs (be that 3 or 4). There are

\displaystyle \binom{5}{3} + \binom{5}{4}

ways to choose his jobs. And there is

\displaystyle 2^{n-2}

ways to choose the rest of the committee. This gives us

\displaystyle n \times (n-1) 15 \times 2^{n-2}

Three brave leaders, 3,1,1 or 2,2,1. There is

\displaystyle n \times \binom{n-1}{2}

ways to choose the people so that one person gets the most (or least) jobs. There is then

\displaystyle \binom{5}{3}

ways to allocate his job. There is then 2 ways to allocate the remaining jobs. If the top is spilt evenly, there is

\displaystyle \binom{5}{2} \binom{3}{2}

ways to choose which jobs go to whom, and the remaining person takes what he is given. The remaining committee can be made up in

\displaystyle 2^{n-3}

ways. This gives us

\displaystyle n \times \binom{n-1}{2} \left ( \binom{5}{3} \times 2 + \binom{5}{2} \binom{3}{2} \right ) \times 2^{n-3}

Four brave leaders, one person gets two jobs (micro-Hitler) and the rest get a job each, there are

\displaystyle n \times (n-1) \times (n-2) \times (n-3)

ways to choose them, (with ordering). There is

\displaystyle \binom{5}{2}

ways to choose micro-Hitler's jobs. The remaining people are ordered, so they take their jobs as they're given. The remaining committe can be formed in