0
votes
1answer
71 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
45 views

The biggest number of possible sets created by $\setminus,\cup$ [on hold]

How many atmost sets can be created by $n$ sets by operations $\setminus, \cup$ .
0
votes
1answer
65 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
52 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
38 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
41 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
2answers
60 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
47 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
34 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
70 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
94 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
69 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
42 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
37 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
50 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 ...
0
votes
1answer
27 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
28 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
43 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
110 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
455 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
58 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
41 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
132 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
51 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 ...
4
votes
1answer
67 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
93 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 ...
0
votes
2answers
34 views

Permutation Discrete mathematics

in survey of 50 households, 25 responded that they have an HDTV television, 35 responded that they had a multimedia personal computer and 15 responded they had both. How many households had neither an ...
1
vote
1answer
77 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
42 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
60 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
1k 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 ...
0
votes
1answer
45 views

A map from the set of binary strings to $\mathbb{N}$

Suppose $B$ is the set of all finite strings of $0$'s and $1$'s. Define a binary relation $R$ on $B$ as follows: $$\sigma R\tau\quad\mbox{ iff }\quad\mbox{ $\sigma$ is a proper initial segment of ...
0
votes
1answer
108 views

How can I count the number of partitions of S with exactly n parts?

If I have a set $S$ of $n$ elements, is there a way to find the number of partitions of that set with $k$ "parts/cells"? For example, if set $S = \{a, b, c, d\}$, there are 15 total partitions of ...
1
vote
0answers
45 views

Question about partitions and primes.

Let $A_1\cup A_2\cup\cdots\cup A_n = P$ , where $P$ stands for the set of odd primes $<\sqrt{x}$ and $A_i$ is nonempty. Also $\#A_k\gg \# A_l$ iff $k>l$ ($\#$ is cardinality ). In fact we ...
1
vote
0answers
54 views

Count $k$-subsets with at least $d>1$ different elements (pairwise)

The problem of counting the number of $k$-subsets in a set of size $n$ is well known. The answer is ${n \choose k}$. But here, I want $k$-subsets with the property that any two of them have at least ...
1
vote
2answers
80 views

Reconciling two statements of Ramsey's Theorem.

In the appendix to Shelah's book on Classification Theory: THEOREM 2.1 (Ramsey's Theorem): (1) For any infinite ordered set $I$, and $n$-place function $f$ from $I$, with range of cardinality ...
1
vote
2answers
96 views

Formulas for mappings between power set $P_n$ and $1, \ldots, 2^n$

Let $A_n$ be the ordered set of integers from $1$ to $n$ $$ A_n = \left\{1, 2, 3, \ldots, n-2, n-1, n \right\}, $$ let $B_n$ be the ordered set of integers from $1$ to $2^n$ $$ B_n = \left\{1, 2, 3, ...
1
vote
1answer
680 views

cardinality of a set with repeating elements? [duplicate]

What is the cardinality of a set which has repeating elements ? For example $S = \{1,1,1,2,2\}$ Is each individual element counted? Please quote a reference text if possible.
3
votes
2answers
52 views

Prove that the number of pairs $(A,B)$ equals ${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$

Prove that the number of pairs $(A,B)$ with $A\subseteq N_n, B\subseteq N_n, |A|=r, |B|=s, and |A\cap B|=i$ equals ${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$ My teacher told me ...
2
votes
1answer
57 views

Unique sequences from different sets

I am given $n$ sets with a selection of $m$ elements, such as: $$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$ I am trying to calculate the number of unique sequences that contain all elements ...
4
votes
1answer
1k views

Counting binary operations on a set with $n$ elements

I am trying to solve following problem but not able to find any way to proceed. Let $S$ be a set having $n$ elements. Can we count about number of binary operations that can be defined on a set? Can ...
0
votes
2answers
82 views

Counting the number of subsets of any size.

Let $X = \{1,2, \ldots ,10\}$. Define the relation $R$ on $X$ by: $\forall a,b \in X, \; aRb$ if and only if $a\cdot b$ is even. a) Find the number of subsets, $S$ of $X$, of any size that satisfy the ...
0
votes
2answers
65 views

A Combinatorial Problem

From any set of 5 distinct one-digit positive integers can we always choose two disjoint non-empty subsets , so that their elements have the same sum ?
1
vote
1answer
56 views

Prove that the Iwata function is Submodular

The Submodularity property for $f: 2^V \rightarrow \mathbb{R}$ is defined as: $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ where $X, Y \subseteq V$ While the Iwata function is defined as: ...
0
votes
2answers
51 views

Number of subsets $Z $ of $X$ such that $(Y - Z)\cup(Z-Y)=\{3\}$

$X = \{1,2,3,4,...10\}$ and $Y = \{1,2,3,4,5\}$. The number of subsets $Z$ of $X$ such that $(Y - Z)\cup(Z-Y)=\{3\}$ is ? What is most generalized approach for these kind of questions?