When does ## { n \choose k } ## represent set of lists?

[CGandC]

TL;DR Summary

When does ${ n \choose k }$ represent set of lists?

I'm not fully aware when ${ n \choose k }$ represents a set of subsets of cardinality $k$ and when does it represent a set of lists of size $k$. For example, look at the following two problems:
Problem 1: How many 7-digit binary strings have three 1's? Answer: ${ 7 \choose 3 }$=35 . Explanation: My 7-element set is {1,2,3,4,5,6,7} corresponding to the indices of the digits which form the string (i.e., 3 corresponds to the third digit). Now we choose three elements out of this set, corresponding to the spots of the string where a "one digit" should appear.
Problem 2: In how many ways can $n$ people be seated in a row if person $\beta$ is to the right of $\alpha$ ( not necessarily adjacent )? Answer: ${n \choose 2} (n-2)!$ which is also $\frac{n!}{2}$. Explanation: the ${ n \choose 2 }$ comes from choosing two distinct places for $\alpha$ and $\beta$ and seating them the correct way around. And the $(n-2)!$ comes from seating the rest of the $n-2$ people in the left-over seats after we seated $\alpha$ and $\beta$.

My difficulty:
( Problem 1 ) The set of all 7-digit binary strings is of the form $\{ (1,1,1,0,0,0,0) , (1,0,1,1,0,0,0,0), ... \}$ . Note the size of this set is ${ 7 \choose 3 } = 35$
( Problem 2 ) The set of all the spots where $\alpha$ and $\beta$ can sit is of the form $J_n=\{(a,b):a \in I_n,b \in I_n, a<b\}$ where $I_n=\{1,2,\ldots,n\}$ is the set of seat indices. An example of set $J_n$ is $\{ (1,3), (5,8),... \}$. Note the size of set $J_n$ is ${ n \choose 2 }$.

The problem as I see it is - In all those sets above we have lists and not subsets. I learned that ${ n \choose k }$ represents a set of subsets of cardinality $k$ and not a set of lists of size k. However, why in the sets above ( which we got from choosing ) we have sets of lists and not sets of subsets? Am I wrong that ${ n \choose k }$ gives me subsets? ( and that it should actually give me lists? )

 

[Mark44]

Summary:: When does ${ n \choose k }$ represent set of lists?

I'm not fully aware when ${ n \choose k }$ represents a set of subsets of cardinality $k$ and when does it represent a set of lists of size $k$.

Neither.
$n \choose k$ represents a number -- the number of combinations of n objects taken k at a time. It doesn't tell you what the combinations are -- just how many there are.

For example, look at the following two problems:
Problem 1: How many 7-digit binary strings have three 1's? Answer: ${ 7 \choose 3 }$=35 . Explanation: My 7-element set is {1,2,3,4,5,6,7} corresponding to the indices of the digits which form the string (i.e., 3 corresponds to the third digit). Now we choose three elements out of this set, corresponding to the spots of the string where a "one digit" should appear.
Problem 2: In how many ways can $n$ people be seated in a row if person $\beta$ is to the right of $\alpha$ ( not necessarily adjacent )? Answer: ${n \choose 2} (n-2)!$ which is also $\frac{n!}{2}$. Explanation: the ${ n \choose 2 }$ comes from choosing two distinct places for $\alpha$ and $\beta$ and seating them the correct way around. And the $(n-2)!$ comes from seating the rest of the $n-2$ people in the left-over seats after we seated $\alpha$ and $\beta$.

My difficulty:
( Problem 1 ) The set of all 7-digit binary strings is of the form $\{ (1,1,1,0,0,0,0) , (1,0,1,1,0,0,0,0), ... \}$ . Note the size of this set is ${ 7 \choose 3 } = 35$

Minor correction. The set you showed is the set of 7-digit binary strings that contain three 1 digits. There are 128 7-digit binary strings.

( Problem 2 ) The set of all the spots where $\alpha$ and $\beta$ can sit is of the form $J_n=\{(a,b):a \in I_n,b \in I_n, a<b\}$ where $I_n=\{1,2,\ldots,n\}$ is the set of seat indices. An example of set $J_n$ is $\{ (1,3), (5,8),... \}$. Note the size of set $J_n$ is ${ n \choose 2 }$.

The problem as I see it is - In all those sets above we have lists and not subsets.

Going back to your first problem, the list you showed (in part) is a subset of the set of all possible 7-digit binary strings. I don't really see much of a difference between a list and a set, although elements in a set are generally considered to be unique, but can be repeated in a list.

I learned that ${ n \choose k }$ represents a set of subsets of cardinality $k$ and not a set of lists of size k. However, why in the sets above ( which we got from choosing ) we have sets of lists and not sets of subsets? Am I wrong that ${ n \choose k }$ gives me subsets? ( and that it should actually give me lists? )

Yes, that is incorrect. ${ n \choose k }$ is a number. To determine which combinations requires additional work.

 

[FactChecker]

You need to decide how much the order of the results matter. Any time you have 7 objects where order matters completely, there are 7!=5040 possible results. When you have 3 of those that can be swapped around and still give an equivalent result, you need to divide by the number of those exchanges (which 7! counted as different). That gives you 7!/3! = 5040/6=840 results that you want to consider to be different. Suppose you want the remaining 4 to be identical so that they can also be swapped around and still give the equivalent result. Then there are 4! ways they can be swapped around (which 7!/3! counted as different). So you should divide by 4! to get 7!/(3!*4!) = 35.

There is an endless variety of problems like this, where some sets of objects are equivalent (and can be swapped around) and others are not.

 

[CGandC]

Going back to your first problem, the list you showed (in part) is a subset of the set of all possible 7-digit binary strings. I don't really see much of a difference between a list and a set, although elements in a set are generally considered to be unique, but can be repeated in a list.

Looking at the second problem, you are telling me that If $I_n=\{1,2,\ldots,n\}$ then considering $J_n=\{(a,b):a \in I_n,b \in I_n, a<b\}$ and $K_n=\{\{a,b\}:a \in I_n,b \in I_n, a\not=b\}$ there is a natural bijection $f:J_n \to K_n$ of $f((a,b)) = \{a,b\}$, so they have the same number of elements, namely ${n \choose 2}$. So I can use $J_n$ or $K_n$ and get the same answer, is this the reasoning when you said you don't see a difference between a list and set of subsets?

Yes, that is incorrect. ${ n \choose k }$ is a number. To determine which combinations requires additional work.

I meant that ${n \choose k}$ is a number that represents a set of subsets of cardinality k, or does it represent a set of lists of size k?

You need to decide how much the order of the results matter. Any time you have 7 objects where order matters completely, there are 7!=5040 possible results. When you have 3 of those that can be swapped around and still give an equivalent result, you need to divide by the number of those exchanges (which 7! counted as different). That gives you 7!/3! = 5040/6=840 results that you want to consider to be different. Suppose you want the remaining 4 to be identical so that they can also be swapped around and still give the equivalent result. Then there are 4! ways they can be swapped around (which 7!/3! counted as different). So you should divide by 4! to get 7!/(3!*4!) = 35.

So we are actually constructing a set of lists with size 7 and the size of this set is ${ 7 \choose 3 }$? And just because it happens in the problem for the size of the set to be ${ 7 \choose 3 }$ then it does not necessarily mean the set is actually made of subsets of cardinality 7?

 

[FactChecker]

So we are actually constructing a set of lists with size 7 and the size of this set is ${ 7 \choose 3 }$? And just because it happens in the problem for the size of the set to be ${ 7 \choose 3 }$ then it does not necessarily mean the set is actually made of subsets of cardinality 7?

I think that this is wrong. Each object in the set is a list of length=7. The issue is how many of those objects are really equivalent because 3 items (the '1' digits) can be swapped around without making any difference. Therefore, divide by the number of ways that they can be swapped around, 3!. And the other elements on the list (the zeros) can also be swapped around without making any difference, so they should only count once. Divide by the number of ways that they are swapped around, 4!.

 

[Stephen Tashi]

The problem as I see it is - In all those sets above we have lists and not subsets.

Combinatorial problems traditionally ask "how many ways...". However there is no standard definition for what a "way" is. What makes two "way's" the same way or different ways varies from problem to problem.

In problem 1, we could have counted the "way's" by listing all distinct subsets of $\{1,2,3,4,5,6,7\}$ that consist of 3 elements. Instead you chose to visualize the "way's" as strings, as suggested by the phrasing of the problem. As far as your own mental process can be described, yes, I'd say that you make a mapping between the counting of subsets and it's realization as a set of strings. However, there is nothing in the definition of $\binom{N}{K}$ that specifies that such a mapping must exist. The number $\binom{N}{K}$ happens to be the correct answer for "the number of way's" in many combinatorial problems, but it is not defined in terms of a specific problem. So it is not defined to be a count of subsets or a count of lists etc.

We define $\binom{N}{K}$ to be $\frac{N!}{(N-K)! K!}$ When we explain it to the average person, we are likely to give an example of it's application instead of quoting the mathematical definition.

 

[CGandC]

Out of curiosity, how would the bijection look like between the set of all subsets of size 3 whose elements are indices ( less than or equal to $n$ ) to the set of all lists (of size 7 ) where 3 numbers are ones and the rest of 4 numbers are zero? My attempt is below but It is wrong because the right set is actually of size one, meaning it only represents $\{ ( 1,1,1,0,0,0,0) \}$
$\{ \{ i,j,k \} : i \neq j \neq k \land i,j,k \leq n \} \rightarrow \{ \{ a \} , \{ \{ b \} \} , \{ \{ \{ c \} \} \} , \{ \{ \{ \{ 0 \} \} \} \} \} , \{ \{ \{ \{ \{ 0 \} \} \} \} \} , \{ \{ \{ \{ \{ \{ 0 \} \} \} \} \} \} ,\{ \{ \{ \{ \{ \{ \{ 0 \} \} \} \} \} \} \} : a=b=c=1 \}$

 

[Stephen Tashi]

to the set of all lists (of size 7 )

What technical definition of a "list" do we use?

The use of deeply nested brackets is confusing. Are you using the set theoretic definition of integers where the consecutive integers are defined as sets who elements have deeper and deeper layers of nested brackets? I suggest not doing that!

A convenient definition for a list of elements of the set $S$ is that the list is a mapping from the first N positive integers to elements of $S$. With that definition, if you want to map a subset of the first M positive integers to a list, you need to map the subset to a mapping. So, in your definition of this map-to-a-mapping, you need to have a mapping on the right side of the "$\rightarrow$".

The conventional way to denote a list is write something like $(a,b,a,a,c)$ as an abbreviation for the mapping:
$1 \rightarrow a$
$2 \rightarrow b$
$3 \rightarrow a$
$4 \rightarrow a$
$5 \rightarrow c$.

This is similar to the definition of a sequence. When we say "the sequence $\frac{N}{N+2}$" this is understood to mean the function defined by $N \rightarrow \frac{N}{N+2}$.

 

[CGandC]

What technical definition of a "list" do we use?

The use of deeply nested brackets is confusing. Are you using the set theoretic definition of integers where the consecutive integers are defined as sets who elements have deeper and deeper layers of nested brackets? I suggest not doing that!

You right, I just didn't conceive of how to represent the set of lists conveniently like the left set I wrote using set-builder notation.

A convenient definition for a list of elements of the set $S$ is that the list is a mapping from the first N positive integers to elements of $S$. With that definition, if you want to map a subset of the first M positive integers to a list, you need to map the subset to a mapping. So, in your definition of this map-to-a-mapping, you need to have a mapping on the right side of the "$\rightarrow$".

Interesting, I'll have to digest this in my thoughts for awhile.

The conventional way to denote a list is write something like $(a,b,a,a,c)$ as an abbreviation for the mapping:
$1 \rightarrow a$
$2 \rightarrow b$
$3 \rightarrow a$
$4 \rightarrow a$
$5 \rightarrow c$.

Yes, this is the definition of lists I meant.By the way, I think the method I am using ( Showing there is a bijection between sets - therefore they are having the same cardinality ) in counting the number of ways of something ( the counting result represents some cardinality of a set after all ) is called " Double Counting ". Am I right?

 

[Stephen Tashi]

is called " Double Counting ". Am I right?

I've only heard "Double counting" used to describe an error in combinatorial reasoning where the proposed solution counts the same "way" twice as two different ways.

 

[CGandC]

Hmm, you are talking about this https://en.wikipedia.org/wiki/Double_counting_(fallacy), I'm talking about https://en.wikipedia.org/wiki/Double_counting_(proof_technique). Maybe you know a book that discusses this method extensively? ( the few ones that I managed to find that are mentioning this method are discussing very little about it )

 

[Mark44]

Looking at the second problem, you are telling me that if $I_n=\{1,2,\ldots,n\}$ then considering $J_n=\{(a,b):a \in I_n,b \in I_n, a<b\}$ and $K_n=\{\{a,b\}:a \in I_n,b \in I_n, a\not=b\}$ there is a natural bijection $f:J_n \to K_n$ of $f((a,b)) = \{a,b\}$, so they have the same number of elements, namely ${n \choose 2}$. So I can use $J_n$ or $K_n$ and get the same answer, is this the reasoning when you said you don't see a difference between a list and set of subsets?

I didn't say anything about the 2nd problem, so I'm not telling you anything about it. Except for the fact that there aren't repeated values in sets, I don't see any difference between a list of subsets and a set of subsets.

I meant that ${n \choose k}$ is a number that represents a set of subsets of cardinality k, or does it represent a set of lists of size k?

Again, I don't see any difference, except for the possibility that a list can contain duplicates.
Also, your terminology is confusing, at the least. ${n \choose k}$ is a number. It is not true that it "represents a set of subsets of cardinality k" -- it is how many subsets there are in the list/set of subsets.

 

[CGandC]

. It is not true that it "represents a set of subsets of cardinality k" -- it is how many subsets there are in the list/set of subsets.

I'm using the Von Neumann definition for natural numbers (https://en.wikipedia.org/wiki/Natural_number#Von_Neumann_ordinals) so in that case it is true, this fact allows me to use the "Double Counting" technique I posted a link to above.

 

[pbuk]

the few [books] that I managed to find that are mentioning this method are discussing very little about it

Perhaps that is because it is not generally accepted to be very useful.

What is your objective here, is it to learn how to solve problems in combinatorics? If so my advice to you is to Keep It Simple: diversions into set theory are unnecessary complications. For instance:

Problem 2: In how many ways can $n$ people be seated in a row if person $\beta$ is to the right of $\alpha$ ( not necessarily adjacent )?

$n$ people can be seated in a row $n!$ ways; by symmetry in exactly half of these $\alpha$ is seated to the right of $\beta$ so the answer is $\frac{n!}{2}$.

 

[Mark44]

I meant that ${n \choose k}$ is a number that represents a set of subsets of cardinality k, or does it represent a set of lists of size k?

It is not true that it "represents a set of subsets of cardinality k" -- it is how many subsets there are in the list/set of subsets.

Here "it" refers to ${n \choose k}$.

I'm using the Von Neumann definition for natural numbers (https://en.wikipedia.org/wiki/Natural_number#Von_Neumann_ordinals) so in that case it is true, this fact allows me to use the "Double Counting" technique I posted a link to above.

No, I don't think this is applicable. ${n \choose k}$ is a number only. You need to distinguish between the size of a set, i.e., the number of elements in a set, versus, and the set itself.

What I'm disputing is the phrase "a number that represents a set of subsets..." The number is just how many elements are in the set, and doesn't "represent" a set or list or whatever.

I think you are trying hard to describe things precisely, but are not quite getting there. Here's an example of what I'm quibbling over. Let $S = \{\text{dog}, \text{cat}, \text{goldfish}, \text{parakeet} \}$.

$|S| = 4$, which in no way represents this set, other than to say how many elements are in it. In the same way ${n \choose k}$ only says how many combinations of n things taken k at a time there are, with no connection to what the things actually are.

 

[CGandC]

Perhaps that is because it is not generally accepted to be very useful.

What is your objective here, is it to learn how to solve problems in combinatorics? If so my advice to you is to Keep It Simple: diversions into set theory are unnecessary complications. For instance:

Although I agree and I do solved many problems in combinatorics, sometimes I get to a problem which is totally unapproachable for me in terms of intuition so I'm trying for the first time to tackle combinatorics in a different perspective - using more a set theoretical approach.

What I'm disputing is the phrase "a number that represents a set of subsets..." The number is just how many elements are in the set, and doesn't "represent" a set or list or whatever.

I think you are trying hard to describe things precisely, but are not quite getting there. Here's an example of what I'm quibbling over. Let $S = \{\text{dog}, \text{cat}, \text{goldfish}, \text{parakeet} \}$.

I learned in discrete math that the cardinality of a set is an equivalence class for all the sets that have the "size" the cardinality represents. For example $1 = \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$ . So I'm looking at a natural number from this perspective when studying combinatorics.Maybe I didn't say this but currently I'm doing discrete math course and the professor teaches us about "Double Counting" and requires us to use it alot, we jumped to combinatorics section after learning about cardinalities of infinite sets ( for example we learned about $\aleph_0$ ) and we use techniques from cardinalities of infinite sets in the current study of combinatorics.

 

[pbuk]

Although I agree and I do solved many problems in combinatorics, sometimes I get to a problem which is totally unapproachable for me in terms of intuition so I'm trying for the first time to tackle combinatorics in a different perspective - using more a set theoretical approach.

Everyone is different and we must each find our own way to tackle mathematical problems using whatever mental models we are most comfortable with. Personally my mental model of set cardinalities, particularly regarding infinite sets, is very different from the one I have for combinatorial problems and I find it surprising that anyone could find useful parallels. Again, KISS.

$1 = \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$

No these two things are not equal. You can write $1 \equiv \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$ or some people (including Wikipedia and MathWorld) use the notation$1 \sim \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$.

Perhaps this is the root of your confusion: equivalence is nowhere near as strong a relation as equality.

Maybe I didn't say this but currently I'm doing discrete math course and the professor teaches us about "Double Counting" and requires us to use it alot, we jumped to combinatorics section after learning about cardinalities of infinite sets ( for example we learned about ) and we use techniques from cardinalities of infinite sets in the current study of combinatorics.

Professors teaching their 'pet' topic instead of the one they should be teaching is not unusual

 

[Mark44]

For example $1 = \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$ .

No these two things are not equal. You can write $1 \equiv \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$ or some people (including Wikipedia and MathWorld) use the notation$1 \sim \{ \{ dog \} , \{ \bigtriangleup \} , \{ "A" \},... \}$.

@CGandC, although you can map sets to equivalence classes in any way you want, it would be very unusual in my experience to map a set with an apparently arbitrary number of elements to the numeral 1.

A more reasonable mapping might be something like this, where the equivalence class corresponds to the number of elements in the set:
$0 \equiv \{ \}$
$1 \equiv \{ \text{dog}\}$
$2 \equiv \{ \text{dog}, "A"\}$
and so on.

Also, I agree with @pbuk's opinion here:

Personally my mental model of set cardinalities, particularly regarding infinite sets, is very different from the one I have for combinatorial problems and I find it surprising that anyone could find useful parallels.

 

[Stephen Tashi]

so I'm trying for the first time to tackle combinatorics in a different perspective - using more a set theoretical approach.

Continue your effort, but expect it to be a life long adventure. Unfortunately, current mathematical knowledge doesn't have a good theoretical approach to combinatorics. As I mentioned before, the fundamental quesion in combinatorial problems ("how many ways") doesn't have a standard mathematical definition. So the study of combinatorics tends to be organized as the study of certain types of verbal puzzles - people-sitting-at-tables-problems, balls-in-urns-problems, etc.

Heavy duty mathematical concepts ( homomorphisms, isomorphisms, group theory) don't come to the fore in explaining answers to combinatorial problems - at least in our current state of knowledge.

In the history of mathematics (and in many current textbooks) probability theory is intertwined with combinatorics. Probability theory only became a coherent mathematical structure after it was treated independently of combinatorics. It had to escape combinatorics before it made sense!

 

[pbuk]

it would be very unusual in my experience to map a set with an apparently arbitrary number of elements to the numeral 1.

Yes, good point - I hadn't even noticed what was on the RHS!

 

[CGandC]

Thank you people for your help, I feel more comfortable with combinatorics ( at least for now ) using some of the methods taken from set theory that was discussed in this thread. Although I wouldn't use it all the time but would keep it simple, it helped me make sense of things.