Intro combinatorics question

In summary, the homework asks you to find a one-to-one correspondence between binary strings of odd length that have an even number of 1's, and those that have an odd number of 1's. If you understand the problem, it's very easy. There's no guarantee that you understand it correctly, though.
  • #1
future_phd
19
0

Homework Statement


Find a one-to-one correspondence between the binary strings (i.e. sequences of 0's and 1's) of length k that have an odd number of 1's, and those that have an even number of 1's.


Homework Equations





The Attempt at a Solution


I'm not exactly sure of what it's asking me to do.
If it's of length k, then you have 2^k different combinations. Half of these will have an even number of 1's, half will have an odd number. So you get (2^k)/2 or 2^(k-1) with an odd number of 1's, and 2^(k-1) with an even number of 1's. Not exactly sure where to go from here.
 
Last edited:
Physics news on Phys.org
  • #2
If I understand this problem correctly, it's very easy. There's no guarantee that I understand it correctly, though.:biggrin:

Consider a binary string of length k, with n 1's and (k - n) 0's. Form a new string of the same length, switching 1's to 0's and 0's to 1's. The new string will have n 0's and (k - n) 1's.

This is clearly a 1:1 mapping, and I think you can satisfy yourself that if the first string had an odd number of 1's, the new string will have an even number of 1's.
 
  • #3
Mark44 said:
If I understand this problem correctly, it's very easy. There's no guarantee that I understand it correctly, though.:biggrin:

Consider a binary string of length k, with n 1's and (k - n) 0's. Form a new string of the same length, switching 1's to 0's and 0's to 1's. The new string will have n 0's and (k - n) 1's.

This is clearly a 1:1 mapping, and I think you can satisfy yourself that if the first string had an odd number of 1's, the new string will have an even number of 1's.
Ahh! That makes sense, that's probably what it's asking. Thanks! :D
 

What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or elements in a systematic way.

Why is combinatorics important?

Combinatorics is important because it helps solve problems related to counting and arranging objects, which are fundamental concepts in many fields such as computer science, statistics, and engineering.

What are the basic principles of combinatorics?

The basic principles of combinatorics include permutations, combinations, and the multiplication and addition principles. Permutations refer to the arrangement of objects in a specific order, while combinations refer to the selection of objects without considering their order. The multiplication principle states that the total number of ways to perform a sequence of tasks is equal to the product of the number of ways to perform each task individually. The addition principle states that the total number of ways to perform a task that can be done in multiple ways is equal to the sum of those ways.

What are some real-world applications of combinatorics?

Combinatorics has many real-world applications, such as in coding theory, which deals with error-correcting codes for secure communication, and in designing efficient algorithms for data processing. It is also used in probability and statistics to analyze and predict outcomes, and in economics to study decision-making and game theory.

What skills are needed to excel in combinatorics?

To excel in combinatorics, one needs a strong foundation in basic mathematics, including algebra, geometry, and logic. It also requires critical thinking, problem-solving, and abstract reasoning skills. Familiarity with computer programming and algorithms can also be beneficial in applying combinatorial principles to solve complex problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
551
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
532
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
1
Views
252
  • Calculus and Beyond Homework Help
Replies
3
Views
689
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • General Math
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top