# Tagged Questions

39 views

### Number of subsets of A∪B that contain an odd number of elements

So I have a problem which defines two sets: $A = \{1,3,5\}$ and $B = \{ 1,2,3,4\}$. The question asks for the number of subsets of $A \cup B$ that contain an odd number of elements. I know the ...
32 views

### The number of $p$-subsets of an $n$-set is $n$ choose $p$

I want to show that the number of subsets of cardinality $p$ of a set $E$ of cardinality $n$ is ${n \choose p}$. I've read a proof that I couldn't understand it basically says that for any injection ...
18 views

### Number of words with a given number of letters.

Let $A$ be the set of the alphabet, $card(A)=26$. The set of all words with three letters has $26^3$ elements, this is just the cardinality of the cartesian product $A\times A\times A$. Now I want to ...
37 views

### Why is my reasoning wrong in determining how many functions there are from set A to set B?

I am trying to count how many functions there are from a set $A$ to a set $B$. The answer to this (and many textbook explanations) are readily available and accessible; I am not looking for the ...
27 views

### Is there a powerset equivalent to the Kleene star?

For some arbitrary alphabet E, is there an equivalent way to construct E* using powersets, sets, or sequences?
17 views

### Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
69 views

### Pigeonhole proof of the existence of two numbers with given sum [duplicate]

Let $|W|=m+1$ and $W$ be a subset of $X=\{1,2,3,\dots ,2m\}$ ($m$ is any natural number). Prove there exists two numbers in $W$ whose sum is $2m+1$. Can anyone give me a hint to prove this? I ...
22 views

### Equivalence of n-Item sets

I am working with AprioriTid algorithm to generate frequent item sets. The Problem - Assume a set of sets : S1 = { {1},{2},{3},{4},...,{m} } This is a 1-item set. To generate a 2-item set we ...
60 views

### Number of subsets of a set $S$ of n elements , is $2^n$ [duplicate]

I know that Number of subsets of a set $S$ of size n , is given by the binomial sum $\sum_{k=0} ^n \binom{n}{k}=2^n$ , n=1,2,3,.. elements how we could conclude of prove this formula ? ...
28 views

49 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). ...
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: ...
80 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 ...
24 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\}) \}$$ ...
59 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 ...
39 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 ...
58 views

### Is it true that for all sets $A, B$, $|A \cap B| \geqslant \frac{1}{2}|A||B|$?

Or is this only true for downsets? Thanks!
65 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 ...
121 views

### There are more functions from $T$ to $S$ than there are subsets of $T$

Question Let $S$ be the set of stars in our galaxy and let $T$ be the set of cars on earth right now. There are more functions $f:T\rightarrow S$ than there are subsets of $T$ . Solution ...
187 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 ...
45 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 ...
18 views

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}$, ...
107 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 ...
87 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 ...
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 ...
66 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}$ ...
66 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 ...
80 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 ...
81 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 ...
56 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 ...
37 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 ...
22 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 ...
93 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)$, ...
99 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 ...
85 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 ...
45 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 ...
45 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 ...
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 ...
90 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,...$ ...
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 ...
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 ...