For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
2answers
51 views

A string Question

Consider the alphabet $X$={$C,D,S,T,X,Z$} A) how many strings of length 17 over the alphabet $X$ contain 4 $C's$, 2 $T's$, 8 $X's$ and $3 Z's$? B) How many of these strings in part A) have all 4 ...
0
votes
2answers
377 views

How many four letter words can be made from the multi-set {T,E,L,E,P,H,O,N,E}?

As the question states, how many four letter words can be made from the multi-set $\left\{T,E,L,E,P,H,O,N,E\right\}$? One condition applies, in that (EELE) is a valid four letter word but (EEEE) is ...
1
vote
1answer
49 views

Bound on probability of independent events

I found this problem which I'm struggling with. Any help with it is appreciated. Let $E = \{E_1, \ldots E_k \}$ be some set of events in a probability space, and let $p = \sum \Pr(E_i)$. Fixing $n ...
1
vote
0answers
80 views

How to show that $S(n, q)$ is a chamber complex?

A simplicial complex is called a chamber complex if any two chambers of the simplicial complex is connected by a gallery. A simplicial complex is a family of finite subsets $X$ of a set of vertices ...
0
votes
1answer
323 views

Number of ways a sum of r can occur if a die is rolled a number of times.

Show that $(1 - x - x^2 - x^3 - x^4 - x^5 -x^6)^{-1}$ is the generating function for the umber of ways a sum of r can occur if a die is rolled a number of times.
0
votes
2answers
69 views

Selecting $300$ Chocalate Candies from $7$ types

How many ways are there to select $300$ chocolate candies from seven types of candy if each type comes in boxes of $20$ and if at least one but not more than five boxes of each type are chosen? Can I ...
0
votes
2answers
76 views

Choosing two sets with k mutual elements

I am struggling with the following question: ...
0
votes
1answer
489 views

extended stars-and-bars problem(where the upper limit of the variable is bounded)

The problem of counting the solutions $(a_1,a_2,\ldots,a_n)$ with integer $a_i\geq0$ for $i\in\{1,2,\ldots,n\}$ such that $$a_1+a_2+a_3+....a_n=N$$ can be solved with a stars-and-bars argument. What ...
2
votes
0answers
56 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
0
votes
1answer
126 views

Number of simple directed graphs

How many simple directed graphs are there on the vertex set $\{1,\ldots,n\}$? I know there are $2^\binom{n}{2}$ simple undirected graphs, but I am confused as to where to go on this problem. I ...
0
votes
3answers
2k views

In a multiple choice test, is a sequence of repeating letters more likely to contain a wrong answer?

I've been wondering whether it's possible to improve the chances of getting fewer questions wrong on multiple choice exams using probability. I thought of this method, but I'm not sure if it helps. ...
4
votes
4answers
824 views

Throwing dice: Probability Total is Divisible by 3

Suppose I throw a fair die $1995$ times. What is the probability that the total is divisible by 3? I tried to attack this problem inductively, storing the total in a variable $t \mod 6$, and ...
4
votes
1answer
116 views

Computing Coefficients for Generalized Combinatorial Sets

I'm new to Combinatorics and am wondering if there is a well-known generalization to the binomial coefficients in the following sense: The binomial coefficients, $n \choose d$, can be considered as ...
1
vote
1answer
111 views

Combinatorics Graph Theory Proof problem

I am struggling with 9.31 from A Walk Through Combinatorics by Miklos Bona. The problem statement reads: There are several people in a classroom; some of them know each other. It is true that if ...
1
vote
2answers
322 views

Counting problem using exponential generating functions

From A Walk Through Combinatorics by Bona in the section on generating functions We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, ...
1
vote
1answer
87 views

Dead presidents

I need to find out the probability that at least 2 of the presidents of the United States have died on the same day of the year. I'm tempted to put 100% since it has actually happened (during the ...
4
votes
1answer
494 views

No-Four-In-Plane, can 11 points be picked from a $4\times4\times4$ grid?

In the No-Four-In-Plane problem, points are selected so that no four of them are coplanar. Eight points can be picked from a $3\times3\times3$ space in a unique way. Can 11 points be picked from a ...
2
votes
1answer
87 views

Tournament of 9 people in teams of 3, everyone teaming up and competing evenly?

We have a tournament of 9 people in changing teams of three, held at one field, one team pausing each game. f.e.: Game One: ABC vs DEF Pausing: GHI Game two: AEI vs DBG Pausing: CFH Is it possible ...
1
vote
1answer
2k views

Number of ways to distribute identical balls into identical bins

I have a question which I expected to be quite famous and common, yet I haven't found much... How many ways are there to distribute $k$ identical balls into $n$ identical bins? For example $(k, ...
0
votes
0answers
38 views

Number of square ($0$, $1$)-matrices with $1$s confined to main diagonal & contiguous sub & superdiagonals with column and row sums in {$0$, $1$}

What is the number of n x n $(0,1)$-matrices having exactly k $1$s ($0$ $\leq$ k $\leq$ n), with the $1$s confined to the main diagonal, plus the first md subdiagonals, plus the first mu ...
3
votes
2answers
836 views

How many length-6 passwords with at least one letter & at least one number can be formed?

How many passwords can be constructed of length 6 which must use at least one letter and at least one number (not case sensitive)? I got $36^{6}-10^{6}-26^{6}$. But I don't know if I missed something ...
1
vote
1answer
69 views

Prove that number of $(A, B, C)$ with $A ∩ B ∩ C = \emptyset$, $A ∩ B \ne \emptyset$, $B ∩ C \ne \emptyset$ is $7^n − 2\cdot6^n + 5^n$

Prove that the number of triples $(A, B, C)$ where $A, B, C$ are subsets of $\{1,2,\cdots,n\}$ such that $A ∩ B ∩ C = \emptyset$, $A ∩ B \ne \emptyset$, $B ∩ C \ne \emptyset$ is $7^n − 2\cdot6^n ...
1
vote
1answer
88 views

Counting positive integral solutions to an equation

How many positive integral solutions to $y_1+y_2+y_3+y_4+y_5+y_6=13$ are there? I started with $y_1=8$ and distributed the rest to $y_2$ to $y_6$, but I feel like I will miss some of them by doing so. ...
1
vote
1answer
202 views

Combinatorics - Find the coefficient of $x^{12}$ in…

Would someone be able to help me figure out these two binomial coefficient problems using generating functions? Its a rough concept for me to understand, so a good explanation would be very much ...
1
vote
1answer
70 views

Combinations' Problem

A person has six friends and during a certain vacation, he met them during several dinners. He found that he dined:- with all the six exactly on one day, with every five of them on 2 days, with every ...
0
votes
2answers
940 views

how to find number of subsets which have fixed number of elements?

If the set $U=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\}$, then how many possible subsets are there in which the number of elements in the subset is $5$? For example: $s_1=\{a,b,c,d,e\}$, ...
2
votes
2answers
3k views

How many different ways can a number be expressed as a sum of any number of integers when order matters?

How many different ways can a number $n \in \mathbb{N} $ be expressed as a sum of any number of positive numbers when order matters? My solution: Since I know, that $n$ can be represented as a sum ...
1
vote
1answer
150 views

Probability that between two Bernoulli sequences, one will get 'ahead' and remain there to sequence end.

As per title, given two Bernoulli sequences both of length $N$ with probability of success $P$ the same for both, what is the probability that one will 'get ahead' in its sum from 1st of the sequence ...
2
votes
2answers
270 views

Probability to form boy-girl pairs

n pairs are formed from n girls and n boys randomly. What is the probability that each pair is formed by one boy and one girl?
0
votes
2answers
65 views

Count combinations of a given partition

Suppose we have a partition $(n_1,\ldots,n_k)$ with $n_i\geq1$ of a given positive number $n$, that is $n_1+\cdots+n_k=n$. How many compositions $(n_1',\ldots,n_k')$ are there, giving the same ...
1
vote
2answers
98 views

90 people with ten friends in the group. Prove its possible to have each person invite 3 people such that each knows at least two others

A high school has 90 alumni, each of whom has ten friends among the other alumni. Prove that each alumni can invite three people for lunch so that each of the four people at the lunch table will know ...
1
vote
2answers
143 views

Determine number of function given two sets and properties

Let A={1,2,3,4,5,6,7} and B={v,w,x,y,z}. Determine the number of functions $f:A \rightarrow B$ where (i) f(A)={v, x}; (ii) |f(A)|=2 For (i) the answer key gives 2!S(7, 2) and (ii) ...
1
vote
2answers
286 views

tournament of 8 people in teams of two, everyone teaming up once and competing twice?

We have a tournament of 8 people in changing teams of two. 14 games, held at two fields. f.e.: Field One, Game One: AB vs CD Field Two, Game Two: EF vs GH Is it possible to mix and team the 8 ...
1
vote
0answers
26 views

Doubt of combinatorics in a question in algebraic geometry

I think the right number is $N=(r+1)(s+1)=rs+r+s+1$ because count $N$ is equivalent to find the number of ordered pairs $(i,j)$, where $0\le i\le r$ and $0\le j\le s$. Thanks
3
votes
5answers
177 views

Show that $\sum_{i=0}^{n-1} 2^i = 2^n - 1$

This is a problem from a book with no solution. Show that: $$\sum_{i=0}^{n-1} 2^i = 2^n - 1$$ without using the formula for geometric series. My lengthy solution is as follows: Try with $n = 1, 2, ...
1
vote
5answers
330 views

What is zero choose one?

Algebraically it comes out to be undefined- but if I have zero elements, and I'm asked to pull elements from it, this should just be zero, right?
0
votes
1answer
52 views

A Combinatorial problem , matrix

I am trying to solve the following problem : Let A be a square matrix whose entries are zeroes and ones. It is allowed to put minus ones instead of ones . Prove that this can be done in such a way ...
3
votes
2answers
162 views

Google Question: Number of ways to select sets such that n is pure

Consider a subset $S$ of positive integers. A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
2
votes
1answer
290 views

Proving Cographic matroid is indeed a matroid

Given a connected graph $G=(V,E)$ let us define $M(G)=(E,I)$ where $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$. When proving $M(G)$ is a Matroid we must show: if $A,B\in I$ ...
1
vote
2answers
614 views

The number of monomials of a given degree

I'm trying to understand why the number of the monomials of degree $d$ in $n+1$ variables is $C_{n+d,n}$. If someone could help me to remember how to solve this, I would be glad. Thanks.
0
votes
1answer
91 views

If we let B be a subset of A, where |A|=n,|B|=k. What is the number of all subsets of A whose intersection with B has X element?

I know when the number of all subsets of A whose intersection with B has x=1 element, the answer would be $${k} 2^{n-k} $$ but what about when x =2 ?? any help would be appreciated.
0
votes
1answer
157 views

The number of rolls of $6$ dice with exactly $4$ distinct values.

I know the answer is $${6 \choose 4}{5 \choose 3}$$ However, I don't understand why this is true?
1
vote
1answer
229 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 ...
2
votes
1answer
272 views

Stirling numbers of second type [duplicate]

How can I do a combinatoric proof that for Stirling number of second type the equality if true: $${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
0
votes
1answer
25 views

In how many ways can a 15-asset portfolio be constructed?

Consider a portfolio with 15 assets, each with individual weight w(i). The weights are integers between 0 and 100, the sum of all weights are 100. In how many ways can this portfolio be constructed? ...
1
vote
0answers
55 views

Counting squares

A total of $64$ dots are arranged in an $8\times8$ grid. How many squares, with sides parallel to the axes, may be formed from these dots? And how many squares altogether? For the first part, I ...
0
votes
2answers
70 views

Sum $\binom{n}{k}+\binom{n+1}{k}+\binom{n+2}{k}+…+\binom{n+m}{k}$

Evaluate the following series sum which n, m, k are nonnegative integers. $$\binom{n}{k}+\binom{n+1}{k}+\binom{n+2}{k}+...+\binom{n+m}{k}$$ I have no idea about it@@
1
vote
1answer
135 views

What is the probability of of drawing at least 1 C, 2 Ds and 3 As in a 7 tile draw from a standard/full Scrabble bag?

The title problem is just one specific example of a more generalized problem that I'm trying to solve. I'm trying to write an efficient algorithm for calculating the probability of at least k ...
0
votes
1answer
32 views

Linear homogeneous recursive sequence of constant sign

Let recursive sequence be defined by the formula $$ s_{j+1}=as_j-s_{j-1}, $$ where $a>1$ is some integer number. Is it true that $s_0<0$, $s_1<0$ implies $s_j<0$ for $j \geq 0$? Edit: ...
0
votes
0answers
33 views

Edge versus vertex assignment in graphs

Consider a graph $G = (V,E)$. Let $x \in \{-1,1\}^V$ be a label assignment to vertices of the graph and $z \in \{-1,1\}^E$ be a label assignment to edges of the graph. We say that $z$ is compatible ...