Combinatorics

Can anyone help me find a literature mentioning the following formula. I formulated it a long time ago and I am not sure if someone had thought of it before me.

\(_kC_r=\sum_{n=1}^{k-r+1} (_{k-n}C_{r-1})\) for \(k\geq r\geq 2\)

#Combinatorics #Summation #Jrfrago #Unknownformula

Note by Roman Frago
6 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

@Kishlaya Jaiswal

Have you read this formula ever before ? I'm pretty sure only you can help Mr. Frago out :)

A Former Brilliant Member - 6 years, 3 months ago

Log in to reply

Yep, it's indeed the Hockey-Stick Formula

I've mentioned clearly about it in my article, so you may wish to read it.

Yeah, now I've got a nice topic for a new wiki.

Kishlaya Jaiswal - 6 years, 3 months ago

Log in to reply

I see , so that's why I was able to link it with you :)

I had just used it once as an identity , more like just a formula . I am wondering what else can be there to it !!

I'll be eagerly waiting for your wiki :)

P.S. Congrats on your getting 200 Friends !!

A Former Brilliant Member - 6 years, 3 months ago

Log in to reply

@A Former Brilliant Member – @Kishlaya Jaiswal,@Ronak Agarwal ,@Pranjal Jain ,@Deepanshu Gupta ,@megh choksi ,@Sudeep Salgia ,@Sandeep Bhardwaj sir ,@Raghav Vaidyanathan ,@Akshay Bodhare and everyone on Brilliant .

Did you guys see the Chemistry questions that I have posted recently ? If so , can you give me a feedback on it's level and pretty much anything else you would like to tell me ?

I just wanted Chemistry to be as popular on Brilliant as are Maths and Physics .

Please give a honest feedback , I won't mind if you criticize me .

Last but not the least , the king of Brilliant @Calvin Lin sir , even your comment will be invaluable :)

A Former Brilliant Member - 6 years, 3 months ago

Log in to reply

@A Former Brilliant Member – I think posting organic reactions won't be good idea. Though I just saw a glimpse of it and I don't think I saw any reaction in your set except that Qualitative Analysis.

Pranjal Jain - 6 years, 3 months ago

Log in to reply

@Pranjal Jain – Ok , so I won't be posting any more Organic Chem questions .

I understand why you have said that , thanks for replying :)

A Former Brilliant Member - 6 years, 3 months ago

It's different from the Hockey-Stick formula.

Roman Frago - 6 years, 3 months ago

Log in to reply

@Roman Frago – Nope ,it is indeed (just a little bit of manipulations and sir, you'll clearly see the identity). Allow me to explain

∑n=1k−r+1(k−nr−1)=(k−1r−1)+(k−2r−1)+…+(r−1r−1)\begin{aligned} \sum_{n=1}^{k-r+1} {k-n \choose r-1} & = & {k-1 \choose r-1} + {k-2 \choose r-1} + \ldots + {r-1 \choose r-1} \end{aligned}

Setting r−1=tr-1=t, and then writing the reverse expression, gives ∑n=1k−t(k−nt)=∑n=0k−t−1(t+n−1t)=(tt)+(t+1t)+…+(k−2t)+(k−1t)=(kt+1)=(kr)\begin{aligned} \sum_{n=1}^{k-t} {k-n \choose t} & = & \sum_{n=0}^{k-t-1} {t+n-1 \choose t} \\ & = & {t \choose t} + {t+1 \choose t} + \ldots + {k-2 \choose t} + {k-1 \choose t} \\ & = & {k \choose t+1} \\ & = & {k \choose r} \end{aligned}

which follows directly from Hockey Stick Identity

Thanks.

Kishlaya Jaiswal - 6 years, 3 months ago

Log in to reply

@Kishlaya Jaiswal – You can even workout the complete proof of your above stated identity just by considering the expansions of

(11−x)r+1=(11−x)r(11−x)\left(\frac{1}{1-x}\right)^{r+1} = \left(\frac{1}{1-x}\right)^{r}\left(\frac{1}{1-x}\right)

and then comparing the coefficients of xk−rx^{k-r}

Kishlaya Jaiswal - 6 years, 3 months ago

Log in to reply

@Kishlaya Jaiswal – Have you read my comment at the bottom of this page ? No hurry, but can you please respond , so that I'll get a better idea of how to proceed

Thanks :)

A Former Brilliant Member - 6 years, 3 months ago

Log in to reply

@A Former Brilliant Member – Yep I've already read it. But actually, I'll take some to reply because I haven't tried out your chemistry problems yet. I will surely give them a try tomorrow.

Kishlaya Jaiswal - 6 years, 3 months ago

@Kishlaya Jaiswal – I am not looking for proof. I am trying to see if anyone has formulated it before me.

EDIT: I appreciate you looking into this.

Roman Frago - 6 years, 3 months ago

@Kishlaya Jaiswal – Yes it is . I had a wrong reference .(http://www.artofproblemsolving.com/Wiki/index.php/Pascal%27s_triangle)

But this one clearly shows that it is the Hockey-Stick:http://www.artofproblemsolving.com/Wiki/index.php/Combinatorialidentity#Hockey-StickIdentity.

Thank you very much.

EDIT: By the way, I thought of it looking into a pentagram.

Roman Frago - 6 years, 3 months ago
×

Problem Loading...

Note Loading...

Set Loading...