Discrete math problem

[south shoal]

I get n possibilities for a, (n-1) possibiliites for b, and 2^(n-2) possibilities for A (since values a and b are fixed)

Is this correct? ChatGPT seems to think its 2^(n-1) but Idk why

[sacred umbra]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules. If there is a conflict amongst multiple helpers feel free to ping “Helper Mod”
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[final current]

ChatGPT may be wrong sometimes

but you're right, there are 2^(n-2) possibilities for A

[south shoal]

Okay great

what if

here is where i get confused

[final current]

you should get the same result, but obtain it in a different manner

[south shoal]

yes that's what i'm confused about

I can do 2^n for A

but then how would I choose a and b?

because the length of A is unknown

[final current]

it depends on the size of A

[south shoal]

and depends

yeah

so how would I put that into one expression

[final current]

if A has size k, how many ways do you have to choose a and b ?

[south shoal]

k choices for a, n-k choices for b

[final current]

yes

so now you sum for all k

[south shoal]

but what is k

[final current]

k can go from 0 to n

[south shoal]

Oh so its like the

k(k+1)/2

[final current]

no, no

[south shoal]

oh

[final current]

well, k(k+1)/2 = Σi≤k i, but it has nothing to do with the current sum

for each k, how many ways are there to choose A of size k, a in A and b not in A ? Call this quantity u(n,k), then the number of such triplets is equal to Σ(0≤k≤n) u(n,k)

[south shoal]

so my answer for any k size is all of it?

Ohh

the number of ways for size k is 2^k * k * (n-k)

how do I get that from sum notation to a normal expression?

[final current]

your expression is not correct, there are no 2^k ways to choose A a subset with k elements among X

[south shoal]

why

Oh

its n choose k

[final current]

yes

[final current]

the point is that both expression count the same thing

[south shoal]

so am i just supposed to leave it in summation notation

[final current]

so you have a combinatorial proof that Σ nCk k (n-k) = n (n-1) 2^(n-2)

the nice expression, you already computed in question 1

[south shoal]

I see now

what combinatorical identity is this?

[final current]

what do you mean ?

[south shoal]

is the identity this ^?

is that what i write down

[final current]

yes

[final current]

you showed that the number of such triples is both equal to n (n-1) 2^(n-2) and Σ nCk k (n-k), hence these two expressions must be equal

[south shoal]

I see

thank you very much, this has been a great help

[final current]

you're welcome

[south shoal]

+close