0
votes
1answer
24 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?
0
votes
1answer
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 ...
0
votes
1answer
67 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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ? ...
2
votes
1answer
28 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
2
votes
4answers
42 views

Subsets $S$ such that $7 \notin S $ or $2 \notin S $

How many subsets $S \subseteq\{1,2...10\}$ are there such that $7 \notin S $ or $2 \notin S $? I can't find the right way to write a formal response. I think that we should consider at least ...
0
votes
1answer
38 views

is the probability of selecting a completely even family $\frac1{2^ n}$?

let $A$ be a set with $N$ elements, and for $0 \le M_{\mathfrak{B}} \le 2^n$ let $\mathfrak{B} =\{B_j\}_{j=0 \cdots M_{\mathfrak{B}}}$ be a a random variable whose value is a family of subsets of $A$, ...
1
vote
1answer
51 views

Count of matched items in multiple sets

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe): Counting ...
2
votes
1answer
55 views

Count amount of pairs $(a,b)$ from two sets $A$ and $B$ such that $a\neq b$

I have two sets $A=\{1,2,3\}$ and $B=\{2,3,4\}$ How do I count the amount of pairs $(a,b)$ where $a\in A$ and $b\in B$, such that $a\ne b$ This problem can easily be done on paper, but how can I ...
2
votes
2answers
79 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
0
votes
1answer
41 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
90 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
47 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
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 ...
1
vote
0answers
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\}) \}$$ ...
0
votes
2answers
57 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
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 ...
1
vote
1answer
58 views
-5
votes
1answer
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 ...
2
votes
1answer
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 ...
11
votes
4answers
184 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
18 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
57 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
103 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
86 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
64 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
62 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
79 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
80 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
55 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
36 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
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 ...
4
votes
2answers
90 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
98 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
83 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
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 ...
1
vote
2answers
44 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
88 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
31 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
47 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
137 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
745 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
92 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 ...