0
votes
1answer
33 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
1
vote
1answer
80 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
1
vote
0answers
45 views

How can I find the smallest set of groups of $n$ elements such that every element is in the same group as every other at least once?

Background: I'm working on a King of the Hill challenge for Programming Puzzles & Code Golf, and I've run into a problem with how I'm creating the individual matchups (groups of 4 entries). ...
0
votes
0answers
39 views

How many Euler diagrams with $n$ sets exist?

Does anyone have any thoughts on this? I have been struggling with it and I'm not sure if it's a hard problem, or easy and I'm just not getting it? For $n=2$ sets (say $A$ and $B$), it's obviously 4: ...
0
votes
3answers
64 views

Inclusion-Exclusion Principle for basic combinatorics problem…

How many ways are there to pick five people for a committee if there are six (different) men and eight (different) women and the selection must include at least one man and one woman? I know ...
1
vote
0answers
20 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
0
votes
2answers
49 views

How many combinations of three scoop cones are possibles?

An ice cream shop sells ice creams in five possible flavours. How many combinations of three scoop cones are possibles?[Note:The repetition of flavours is allowed but the order in which the flavours ...
0
votes
2answers
30 views

Countability of the Real Number set using an infinite-dimensional array

My friend and I were talking about Cantor's Diagonal Argument, and he was asking why the Real Numbers were uncountable. He proposed the following situation: On the first axis, we put 0, 1, 2, ..., 9 ...
1
vote
1answer
57 views
-5
votes
1answer
63 views

Dividing a set of n elements into k disjoint subsets.

I have been able to do the 1st part. I have not been able to prove the 2nd part. My attempt to the solution :- I took $k$ groups $ a_1, a_2, a_3…, a_k $ Let $a_1$ group has $b_1$ similarly so ...
11
votes
4answers
182 views

How find this minimum of the value $f(1)+f(2)+\cdots+f(100)$

Give the positive integer set $A=\{1,2,3,\cdots,100\}$, and define function $f:A\to A$ and (1):such for any $1\le i\le 99$,have $$|f(i)-f(i+1)|\le 1$$ (2): for any $1\le i\le 100$,have ...
0
votes
1answer
44 views

How many equivalence relations there are on a set with 7 elements with some conditions

Calculate how many equivalence relations there are on $\{1,2,3,4,5,6,7 \}$ that include the set $\{(2,2),(1,3),(3,6),(7,5)\}$ and are foreign to the set $\{(1,7),(4,7),(4,3)\}$. Well I first drew ...
0
votes
0answers
17 views

Find cardinality of the largest subset defined by some condition

Let $A = \left\{1,2,3,\dots,2^n\right\}$. Find p, such that $p = \mathop{\max\vphantom{p}}_{A'\subset\ A}\left|A'\right|$ where subsets $A'$ of $A$ satisfy such condition: $x=2y \implies x,y \not\in ...
1
vote
3answers
45 views

Proof that the combination formula actually gives you the number of combinations

Ok, there's no problem in defining a binomial coefficient the way it this: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$ I can also prove to myself that if I have $n$ elements, like: $\{a_1, a_2, \ldots, ...
0
votes
2answers
28 views

Question about the number of subsets

Given a set $S$ of size $25$, let $x$ be an element in $S$. What is the number of subsets of $S$ that contain $x$? Why am I stuck on this? The number of subsets that don't contain $x$ is $2^{24}$, ...
0
votes
1answer
89 views

Are all uncountable infinities greater than all countable infinities? Are some uncountable infinities greater than other uncountable infinities? [duplicate]

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable ...
1
vote
1answer
80 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...
0
votes
2answers
46 views

How find this $\max{|A|}$ if $A=\{S_{i}|S_{i}\equiv 1\pmod 2\}$

let $(a_{1},a_{2},\cdots,a_{2014})$ be a permutation of $(1,2,3,\cdots,2014)$,and define $$S_{k}=a_{1}+a_{2}+\cdots+a_{k},k=1,2,3,\cdots,2014$$ Find the $\max{|A|}$, where ...
0
votes
3answers
60 views

Are the following sets countable?

I'm trying to determine if the following sets are countable: (a) $\mathbb{Z}^{[0,1]}, (b) [0,1]^{\mathbb{Z}}, (c) \mathbb{Z}^{\mathbb{Z}}$, (d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ ...
1
vote
1answer
55 views

Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...
0
votes
1answer
60 views

Function returning number of subsets of size $k$ of a set of size $n$.

I am looking for a function that returns the number of subsets of size $k$ of a set of size $n$. Ideally, the function is commonly used. I took a look at the binomial coefficient. However, there ...
0
votes
1answer
75 views

An algebraic proof that a set has $2^n$ subsets. (I'm looking for an inductive argument.)

There will be duplicates of this, so let me explain why I am asking: I have become blind to what it may be, so I want hints. I am blind because I can do it "combinatorially". The question wishes me ...
3
votes
0answers
52 views

Proving the inclusion exclusion principle from the definition of the cardinality

I want to prove the inclusion exclusion principle: $|A\cup B| = |A| + |B| - |A\cap B|$ where $A$ and $B$ are finite sets. I proved the addition rule by contructing a bijection to a subset of ...
0
votes
1answer
35 views

My Proof for the Cardinality of a Particular Binary Distribution

my question reads as follows: I have constructed a proof and am concerned about 2 things: 1) The validity of my proof. 2) The construction of my proof. I am asking for someone to read through ...
0
votes
0answers
21 views

Help me find out the minimum of n(B) [duplicate]

About natural numbers a 1 ,a 2 ,…,a 20 , define set A={a i +a j |1≤i≤j≤20} . n(A)=201 , then about set B={|a i −a j ||1≤i≤j≤20} . What's the minimum of n(B) ? Last time I posted this question ...
4
votes
2answers
79 views

Number of functions on finite set

If $A$ has $n$ elements, how many functions are there from $A \rightarrow A$? How many bijective functions are there from $A$ to $A$? My thinking was that there are $n$ possibilities for $f(a_1)$, ...
2
votes
3answers
96 views

What is the number of ways to represent the $n$ element set as a union of distinct non-empty subsets

edit: I do not mean the number of partitions $B_n$ here. The title says it all. The n element set is $[n]=\{1,2,\dots,n\}$. One representation (the one using the most sets) for example is the union ...
1
vote
1answer
80 views

Generalization of principle of inclusion and exclusion (PIE)

The PIE can be stated as $$|\cup_{i=1}^n Y_i| = \sum_{J\subset[n], J\neq \emptyset} (-1)^{|J|-1} |Y_J|$$ where $[n]=\{1,2,...,n\}$ and $Y_J=\cap_{i \in J} Y_i$. Problems using it are usually reduced ...
0
votes
1answer
44 views

Find the cardinal of the set of all infinite sequences of $0,1,-1$ such that each sequence contains each digit at least once - Check my answer

As the title says, we are asked to find the cardinal of the set of all infinite sequences made from the digits $0,1,-1$ such that each sequence contains each digit at least once. My answer I solved ...
1
vote
2answers
39 views

Unique combination of sets

We start with a finite number of $N$ sets, $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$, each containing a finite number of integers. The sets do not in general have the same number of elements. The ...
3
votes
2answers
53 views

Mean Element of a Finite Set

Given a finite set $S = \{A_1,A_2,A_3...\}$ containing an arbitrary number of finite sets such that for any $A_i{}\in{}S$ and $A_j{}\in{}S$, $| A_i{} | = | A_j{} |$, and given that for every ...
1
vote
2answers
86 views

Bijective functions over naturals

It is easy to prove that one-to-one (bijective) functions $f : \mathbb{N} \to \mathbb{N}$ are uncountable using a diagonalization argument like this: Suppose that an enumeration $f_1,f_2,f_3,...$ ...
0
votes
1answer
28 views

how many pairs differ in one value from another

Assume I have a family of sets $X=\{X_1,X_2,...,X_m\}$ each set $X_i\in X$ has $n$ elements $\{x^i_1,x^i_2,...,x^i_n\}$. Let $Z$ be the cartesian product of $X$. Let $z^{\downarrow V}$ be the ...
0
votes
1answer
30 views

Language to describe a number smaller than, but related to Bell number

I understand that the Bell number $B_n$ is the number of partitions of a set of size $n$. Despite my incredible ineptitude at combinatorics, I also understand most of how the binomial coefficient ...
0
votes
1answer
46 views

The “counting” problem

Let $X$ be a set containing $n$ elements . Two subset $A$ and $B$ of $X$ are chosen at random . Find the probability that $ A \bigcup B = X $ . Solution given in the book : for each $x_i \in ...
0
votes
0answers
129 views

Iran Math Olympiad 2013 (Perfect Set)

Let $n$ be a natural number and suppose that $w_1,w_2,…,w_n$ are $n$ weights. We call the set of {$w_1,w_2,…,w_n$} to be a Perfect Set if we can achieve all of the 1, 2, …, W weights with sums of ...
4
votes
1answer
620 views

How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
0
votes
1answer
85 views

Finding the Nth element in a list of all possible numbers

This is an extension of my question found here: Given some number of digits, each with a have a specified range from 1 to some number, what would be the Nth element in the list of all permutations of ...
1
vote
1answer
46 views

Finding the Nth number in a generated list

I am generating numbers as follows: Let the first digit range from 1 to 2 inclusive. Let the second digit range from 1 to 3 inclusive. Let the last digit range from 1 to 2 inclusive. I am then ...
0
votes
2answers
200 views

Help understand this proof of even and odd subsets

I need help understanding the proof of the following statement, as given in the book I'm following: Show that a non-empty set has an equal number of even subsets (that is, subsets with an even ...
1
vote
1answer
56 views

Number of even and odd subsets — wrong question?

The book on Discrete Mathematics I'm following poses the following problem: Prove that a nonempty set has the same number of odd subsets (i.e., subsets with odd number of elements) as even ...
5
votes
1answer
73 views

Combinatorics question about downsets

Prove that if $\mathcal{A}$ is a downset then the average size of sets in $\mathcal{A}$ is at most $\frac{n}{2}$ ($\mathcal{A} ⊂ \mathcal{P}(n)$ is a downset if, for every $A∈\mathcal{A}$ , every ...
4
votes
1answer
101 views

Combinatorics intersecting sets question

Let $A_1 , . . . , A_m$ and $B_1 , . . . , B_m$ be subsets of $[n]$ such that $| A_i ∩ B_i |$ is odd for all $i$ and $| A_i ∩ B_j |$ is even for all $i \neq j$ . Show that $m ≤ n$. I've tried using ...
1
vote
1answer
106 views

Total k combinations with at least one element from each set.

Given $n$ sets the total amount of ways k of the elements can be combined is given by $$C(|S_1|+|S_2|+...+|S_n|,k)$$ Now suppose we wanted to find the total combinations possible when at least one ...
11
votes
7answers
2k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
0
votes
0answers
31 views

Some small (and probably easy) implication from combinatorics paper

I'm reading https://people.math.osu.edu/bergelson.1/PolSz.pdf . Question is about part from (1.7) on page 16. Why $ \lambda(\chi_{1})=\lambda(\chi_{1}) $? There's no problem if in 4-th verse ...
2
votes
0answers
50 views

Bell number with minimum bound on partition size

I know that the Bell number $B_n$ is the number of ways to partition a set of $n$ elements into distinct non-empty subsets. Is there a variant of this number that specifies the minimum number of ...
1
vote
1answer
62 views

Making minimum number of partitions of a set

Let us consider a set in which every element has an ordered pair of natural number (x,y)( Each pair is distinct) associated with it. Let us define a partition of a set to be consisting of elements ...
1
vote
2answers
2k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is ...
3
votes
0answers
30 views

Algorithm to Create All “Spot it!” Cards [duplicate]

"Spot it!" is a fun card game, played with 55 cards, each having eight symbols. There are more than 50 symbols in all. There is always one, and only one, matching symbol between any two cards, and ...