How many combinations can be formed from 5 binary digits?

In summary: How many ways can we select items?In summary, the conversation discusses a mathematical problem involving combinatorics and proofs. The goal is to prove the identity of the sum of combinations and find a way to fix an issue with the lower limit of the sum. One approach is to use the binomial expansion formula, while another involves representing selections of items with 1's and 0's.
  • #1
otto
4
0
So look at what I've done:
[tex]
{n+1 \choose k} = \frac {(n+1)!} {(n+1-k)! \cdot k!} = \frac {(n+1)\cdot n!}{(n-(k-1))!\cdot k \cdot (k-1)!}
[/tex][tex]
=
\frac {(n+1)}{k} \cdot

\frac { n!}{(n-(k-1))!\cdot (k-1)!} =

\frac {(n+1)}{k}

\cdot {n \choose k-1}

[/tex]
oops I accidentally posted this before I finished my calculations, please ignore this until I've finished it. Thanks

[edit] So Yea, that's it. Thing is, somethings wrong (try plugging numbers into it). Anyways, I need to figure out what I did wrong. This is just part of a massive can of worms. I am trying to figure out the proof for: [tex]\sum\limits_{i=1}^n {n \choose k} = 2^n
[/tex]
 
Last edited:
Mathematics news on Phys.org
  • #3
Pascals identity to be exact. I've read some "proofs" if you can call them that, but they were rather not helpful. math stack exchange.

When I replace my summation from k=0 to n, with the combinatorics: [itex]

\sum_{k=0}^n{n+1 \choose k} =

\sum_{k=0}^n {n \choose k} +{n \choose k-1}

[/itex] I have the problem that k-1 will equal -1 in the first iteration of the summation. don't know how to fix this.
 
  • #4
otto said:
I am trying to figure out the proof for: [tex]


\sum\limits_{i=1}^n {n \choose k} = 2^n
[/tex]

The lower limit of the sum should be k=0 because i isn't present in the combinatoric and for reasons you'll eventually find out, it should start at 0.


So you want to prove
[tex]
\sum\limits_{k=0}^n {n \choose k} = 2^n
[/tex]

then simply notice that the binomial expansion is

[tex](a+b)^n = \sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k[/tex]

So for what values of a and b is

[tex]\sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k\equiv \sum\limits_{k=0}^n {n \choose k}[/tex]
 
  • #5
otto said:
Pascals identity to be exact. I've read some "proofs" if you can call them that, but they were rather not helpful. math stack exchange.

When I replace my summation from k=0 to n, with the combinatorics: [itex]

\sum_{k=0}^n{n+1 \choose k} =

\sum_{k=0}^n {n \choose k} +{n \choose k-1}

[/itex] I have the problem that k-1 will equal -1 in the first iteration of the summation. don't know how to fix this.

The problem here is that ##\binom{n+1}k=\binom nk+\binom n{k-1}## only for k>0; if k=0 then it's just ##\binom nk##, as both are 1. I think the convention is often to let ##\binom n{-1}=0##; then ##\binom{n+1}k=\binom nk+\binom n{k-1}## even when k=0.
 
  • #6
You are right that the proof by induction approach can turn into a can of worms.
Notice that [itex]
\sum\limits_{k=0}^n {n \choose k}
[/itex] is the total number of ways that any number of items (including 0 and n) can be selected from n items.

If we indicate whether an item is selected or not by 1 or 0, respectively, and put the 1's and 0's in order, we can represent any set of selected items.

For instance, starting with n=5 items, 10110 = select first, don't select second, select third, select fourth, don't select fifth, represents one way of selecting 3 of the 5. Now, how many zero/one patterns can we get from 5 binary digits?
 

What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and organizing combinations and permutations of objects.

Why is combinatorics important?

Combinatorics is important because it has practical applications in fields such as computer science, statistics, and engineering. It also helps us understand and solve problems related to counting and probability.

What are some common examples of combinatorics in everyday life?

Some common examples of combinatorics in everyday life include counting the number of possible outcomes in a game of chance, organizing schedules or events, and creating passwords or security codes.

What skills are needed to excel in combinatorics?

To excel in combinatorics, one needs a strong foundation in basic mathematics, logic, and problem-solving skills. It also requires the ability to think creatively and approach problems systematically.

How can combinatorics be applied in other fields?

Combinatorics can be applied in other fields such as computer science for optimizing algorithms, in biology for analyzing genetic sequences, and in economics for studying consumer behavior and market trends.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
852
Replies
6
Views
2K
Replies
1
Views
1K
  • General Math
Replies
1
Views
1K
  • Quantum Physics
Replies
6
Views
979
  • Calculus and Beyond Homework Help
Replies
1
Views
535
  • Engineering and Comp Sci Homework Help
Replies
1
Views
809
Replies
16
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Advanced Physics Homework Help
Replies
5
Views
1K
Back
Top