#combinatorial proofs -- Discrete Mathmatics

60 messages · Page 1 of 1 (latest)

main bridge
#

Can you please help me with these two problems? I genuinely dont understand how to solve these theory or algebra-wise... Thank you!

sorry if the tag is wrong lol idk where to put it

image.png image.png
wild voidBOT
#
👋 Welcome to your Help Thread!

Hey @main bridge, Thanks for sharing your math problem with us. While you wait for a Helper to help you, we want to share some vital information with you.

​

● Please take a moment to read the helpee guidelines. This will make sure that your post follows the helpee rules of our community.

​

● Please don't ping <@&775784618955505685>, <@&1283689826742440016>, <@&819616364188139550>, or <@&624327278137966593> for help because their job is to take care of the server's administrative tasks, not to answer queries directly. However, if you have a problem with how a Helper is acting, you can ping a Helper Moderator.

​

● It's always very useful if you can show us the work you've done so far. This makes it easier for our Helpers to find mistakes and help you get to the right answer.

Once you've got your answer and you're all set, you can close this thread by typing +close, and then you can click the Thank buttons to show your Helper some appreciation.
wild voidBOT
open kindle
open kindle
#

Count this situation in 2 ways

#

One way is first picking a leader

#

Then picking the subset of people

#

What quantity does this give

#

The other is picking the group of k people first and then picking the leader

main bridge
#

Omg ok ok ily

#

for questions like the second (espically the left part) is there a way to easily tell what it's actually picking from? all the choose functions really confused me

open kindle
#

You pick a group of k people out of n people how many ways

#

n choose k

#

Out of the k people now you need a leader how many candidates

#

k

#

How many ways to select a k group and assign a leader

#

k \times nCk

#

Now the possible sizes of the group are?

main bridge
#

n?

#

wait no

open kindle
#

1,2,....,n

main bridge
#

oh lol

open kindle
#

So you sum them up

main bridge
#

ok I think i get it?i feel like im asking rlly stupid quesitons tho sorry lol

open kindle
#

Go ahead

#

Ask any questions you want

main bridge
#

with our choose fcn were creating groups of size k. we are then multiplying it by k to pick one leader (how? if k is 2 and n is 3, theres 3 ways to pick a group of 2 people out of 3. then multiplying that by 2 were getting 6. is the 6 the number of ways to pick one leader out of that group? -- and then is summating that the way to figure out the total ways we could pick a leader out of n people in k groups?

open kindle
#

6 is the number of ways to make a group of two people and assign a leader

#

We are doing this for all group sizes

#

So that we account for all possible groups of people that can occur

main bridge
#

oh ok so if n was 3 it would be the number of ways to have a group of 1 person with a leader, 2 people with one a leader, and 3 with one a leader?

open kindle
#

Yeah

#

So 1*C(3,1)+2*C(3,2)+3*C(3,3)

#

Which equals 9?

main bridge
#

OH ok yay

#

thanks man youre actually the goat

open kindle
#

,w 1C(3,1)+2C(3,2)+3*C(3,3)

craggy snowBOT
main bridge
#

lol close enough

open kindle
#

Sorry 12

#

Which checks out with the

#

3*2^(3-1)

main bridge
#

so with 3 ppl u can make 12 groups of 1, 2, and 3 with 1 leader OK

#

for a combinatorial proof id just need to explain that logically

open kindle
#

We just did that

main bridge
#

i cant just do 3*2^3-1 sinc eid have to prove that for all n

open kindle
#

You are counting the following quantity

#

(leader, group)

#

Or more simply

#

Given a set of n elements

#

The following quantity: (x,subset) where x \in subset

#

So naturally you start counting by first fixing a X and counting all the subsets that can happen

#

This gives you n*2^{n-1}

#

Can you see why

main bridge
#

yeah right right right

#

thank you my king

open kindle
wild voidBOT
#

@main bridge

:HelpIcon:| Help Reminder

Hello blaytz, this is a friendly reminder that your help request has been inactive for more than 24 hours. If you no longer need assistance, please consider closing the thread using the +close command. This thread will be automatically closed in 3 days if it remains inactive.

shy cloak