Combinatorics: Partitioning Generating Functions

In summary, combinatorics is a branch of mathematics that deals with counting and arranging objects. Partitioning generating functions, also known as generating functions for partitions, are a combinatorial tool used to represent and analyze the number of ways a set can be partitioned into smaller subsets. They work by assigning a variable to each element in a set and the coefficients of the resulting polynomial represent the number of ways the set can be partitioned. Partitioning generating functions have various applications in combinatorics, number theory, and statistics, and can be used to solve real-world problems such as dividing groups of people or distributing items. However, they have limitations when dealing with large sets or a large number of subsets, and other combinatorial tools may
  • #1
Shoney45
68
0

Homework Statement



Show with generating functions that every positive integer can be written as a unique power of 2.

Homework Equations



The generating function for ar, the number of ways to write an integer r as a sum of distinct powers of 2 = g(x) = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...(1 + x^2k)...

The Attempt at a Solution



This is an example from the text that is pretty crucial to understanding this section of my text. The book then goes on to say the following:

"To show that every integer can be written as a unique sum of distinct powers of 2, we must show that the coefficient of every power of x in g(x) is 1. That is, show that:

g(x) = 1 + x + x^2 + x^3 + ...= 1/(1-x)".

1) So my first problem is that I don't understand why g(x) is changing. The actual generating function is for powers of two. But for the above identity, the author is using the standard identity for the polynomial expansion of 1/(1-x)

I don't get it.

2) The identity [1 + x + x^2 + x^3 + ... = 1/(1-x)] can also be expressed as (1-x)*g(x) = 1. This is achieved by repeatedly using the factorization (1-x^k)(1+x^k) = 1-x^2k such that:

(1-x)*g(x) = (1 - x)(1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...
= (1 - x^2)(1 + x^2)(1 + x^4)(1 + x^8)...
= (1 - x^4)(1 + x^4)(1 + x^8)...
.
.
.
= 1

My problem is that I can't understand how to make the final step that sets (1-x)*g(x) = 1. By my reckoning, if I keep on applying the identity, then I will keep on getting powers of (1 - x^2k), and I don't understand how that eventually becomes 1.
 
Last edited:
Physics news on Phys.org
  • #2

Hello,

Thank you for your post and for your questions. I understand your confusion about the generating function for powers of 2 and the use of the standard identity for polynomial expansion. Let me try to explain it in a different way.

The generating function g(x) = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...(1 + x^2k)... is actually a representation of the powers of 2. Each term in the product, (1 + x^2k), represents the number of ways to write k as a sum of distinct powers of 2. For example, (1 + x^4) represents the number of ways to write 4 as a sum of distinct powers of 2, which is 1 (since 4 can only be written as 2^2).

Now, when we multiply all these terms together, we are essentially adding up all the different ways to write any positive integer as a sum of distinct powers of 2. So, g(x) represents the generating function for all the powers of 2.

Now, the identity [1 + x + x^2 + x^3 + ... = 1/(1-x)] can be used to show that every integer can be written as a unique sum of distinct powers of 2. This is because when we multiply (1-x) with g(x), we are essentially removing the terms that represent the same power of 2. For example, (1-x)(1+x^2) will remove the term (1+x^2) from (1+x)(1+x^2), leaving us with just (1+x), which represents the number of ways to write 1 as a sum of distinct powers of 2.

By repeatedly using this factorization, we will eventually be left with just the term 1, which represents the number of ways to write 0 as a sum of distinct powers of 2. This means that every integer has a unique representation as a sum of distinct powers of 2, since we have removed all the duplicate terms.

I hope this helps to clarify the use of the generating function and the identity. Let me know if you have any further questions or need more clarification. Keep up the good work!
 

1. What is combinatorics and how does it relate to partitioning generating functions?

Combinatorics is the branch of mathematics that deals with counting and arranging objects. Partitioning generating functions, also known as generating functions for partitions, is a combinatorial tool used to represent and analyze the number of ways a set can be partitioned into smaller subsets.

2. How do partitioning generating functions work?

Partitioning generating functions work by assigning a variable, usually denoted as x, to each element in a set. The coefficients of the resulting polynomial represent the number of ways the set can be partitioned into subsets of different sizes. The power of x indicates the number of elements in each subset.

3. What are the applications of partitioning generating functions?

Partitioning generating functions have various applications in combinatorics, number theory, and statistics. They are commonly used to solve problems related to counting partitions, integer partitions, and compositions. They also have applications in graph theory, probability, and computer science.

4. Can partitioning generating functions be used to solve real-world problems?

Yes, partitioning generating functions have practical applications in real-world problems. For example, they can be used to determine the number of ways a group of people can be divided into teams, or the number of ways to distribute items in different groups. They can also be used to analyze the complexity of algorithms in computer science.

5. Are there any limitations to using partitioning generating functions?

While partitioning generating functions are a powerful tool in combinatorics, they do have some limitations. They may not be appropriate for solving problems involving large sets or when the number of subsets is too large. Additionally, they may not be the most efficient method for solving certain problems, and other combinatorial tools may be more suitable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
10
Views
792
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
722
  • Calculus and Beyond Homework Help
Replies
1
Views
94
  • Calculus and Beyond Homework Help
Replies
1
Views
167
  • Calculus and Beyond Homework Help
Replies
14
Views
428
  • Calculus and Beyond Homework Help
Replies
3
Views
444
  • Calculus and Beyond Homework Help
Replies
1
Views
663
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top