This tag is for basic 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)

0
votes
1answer
44 views

Placing indistinguishable objects on a indistinguishable shelve

How many ways can we place $10$ books on a bookcase with $3$ shelves if the books are (a) indistinguishable copies? (b) all distinct? For a, would it simply be $10!$ ?
0
votes
2answers
51 views

A combinatorial assignment problem

I have this combinatorial assignment problem: K candidates apply for a job. There are R referees available to review their resumes and make a recommendation. Suppose that we would like M referees ...
2
votes
0answers
57 views

How to generalize the Thue-Morse sequence to more than two symbols?

The Thue-Morse sequence is defined as a binary sequence and can be generated like 0, 01, 01 10, 01 10 10 01, 01 10 10 01 10 01 01 10, ... . So the second half of the series is always the binary ...
1
vote
2answers
709 views

Counting the number of $n$-digit quaternary sequence that have even number of $0's$ and an even number of $1's$

Show that the number of $n$-digit quaternary sequences(sequences that have $0's, 1's, 2's$ and $3's$ as the digits) that have an even number of $0's$ and an even number of $1's$ is $4^n/4+2^n/2$. ...
0
votes
0answers
25 views

Number of Gelfand-Tsetlin patterns, NP-complete?

Is the problem of determining the number of Gelfand-Tsetlin patterns between two given integer partitions $ \lambda=\lambda_1\ge\lambda_2,\dots,\ge\lambda_n $ and $ \mu=\mu_1\ge\mu_2,\dots,\ge\mu_n $ ...
0
votes
1answer
40 views

surjection from finite set X-Y

The surjection b is $$ b: X \to Y $$ there$ X=\{1,2,3,4\}$ and $Y=\{a,b\}$ How many surjections of this type of function can you find? I know that the function b is defined on the set to the left ...
1
vote
1answer
41 views

What's the expected score for guessing on a word bank/“matching” test?

Some quizzes/tests have a "matching" or "word bank" section, which is set up as follows: There are $n$ questions that the student must answer. The answer to each of the $n$ questions is one of $k ...
-1
votes
1answer
37 views

abandon a column, also $n$ different row vectors

$A$ is a $n\times n$ matrix, whose $n$ row vectors are all different. then, we can get rid of one column of $A$(there exist a column, we abandon this column ), such that the new $n\times (n-1)$ ...
1
vote
0answers
9 views

Simplifcation of the Function Required

I want to simplify the following expression $$ \sum_{x=0}^{D+m} \frac {x!} {(n+1)_x} (\frac {\theta_{eff}} {\mu})^x {D+m \choose x} $$ The parameters $D, m, n, \theta_{eff}, \mu, $ are constants. ...
0
votes
1answer
30 views

Is this the correct expression for a combination problem?

I feel that I have the correct expression for this problem, but I have this nagging feeling that something is incorrect. May I ask that you all verify this? Question: "In a game of chance, three of ...
2
votes
3answers
629 views

Number of sequences with n digits, even number of 1's

ASKED: Let $c_n$ be the number of sequences with $n$ digits from $\{1,2,3,4\} $ with an even number of $1's$. Determine $c_n$ for $n \geq 0$. GIVEN RESULT: $c_{n+1} = 3 \cdot c_n + 1 \cdot ...
2
votes
1answer
63 views

Number of ways to derive the number 14 using a recursive definition of EVEN numbers?

I have the following recursive definition for the construction of EVEN Numbers- [RULE 1]: 2 is an EVEN number. [RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN ...
2
votes
1answer
72 views

Probability Question: Round table meeting

Six delegations have a round table meeting. The meeting organization randomly arranges the seat for them. It is important to consider who is sitting to the left or right for each delegation. How many ...
1
vote
1answer
29 views

Packing 5 identical books into 5 identical boxes

How many ways are there to pack $5$ identical books into $5$ identical boxes with no restrictions placed on how many can go in a box? No restrictions means some boxes can be empty. Would it be ...
0
votes
1answer
42 views

Combinatorics — Graphs

I need to construct a graph that has the following properties: the vertices of G are the edges of a complete graph $K_5$ on 5 vertices. The vertices of G are adjacent if and only if the corresponding ...
2
votes
2answers
128 views

How many subsets of size $n+1$ can we have so no two of them have intersection of size $n$

Suppose we have a set of size $m$. How many sets of fixed size $n+1$ can we have so that no two of them have an intersection of size $n$ ?
2
votes
1answer
46 views

Euler's Formula — Combinatorics

A convex polyhedron has only pentagonal and hexagonal faces. Prove that it has at least 12 pentagonal faces. Can anyone help me with this? At least can someone give me a hint or two? $$$$ $$$$ ...
0
votes
1answer
31 views

Counting cases?

I don't have a background on probabilities but i do want to get the rule to solve the following problem and similar ones . Let's say we have a 2x2 matrix , in which every element could be either 1 or ...
0
votes
1answer
9 views

Numbers of lists that take one value of each row in a $n\times n$ matrix that differs by more than one number.

I have a matrix $M$ with dimensions $n\times n$ and a list $L$ that takes exactly one value of each row. As a example, let's take this matrix of dimensions $3\times 3$ $$A= \begin{pmatrix} 1 & ...
1
vote
0answers
56 views

the number of $m$-divisible subsets of an $n$-set

Let $\omega$ be a primitive $m^{th}$ root of unity. How can we use the binomial expansion of $(1+\omega)^n$ to find out the number of $m$-divisible subsets of an $n$-set. Actually, I mean, to find a ...
1
vote
1answer
113 views

Finding the amount partitions of a multiset

A multiset $A$ contains $n$ positive integers. The multiplicity of every integer is less or equal to $m$. $A$ is partitioned into $m$ subsequences in such a way that the multiplicity of all elements ...
1
vote
2answers
41 views

Different ways to distribute

If I have $5$ bananas, $3$ oranges, and $8$ apples, how many ways can I distribute these to $16$ friends, if each friend gets one fruit? Would it simply be $5*3*8=120$?
0
votes
6answers
160 views

Probability that there are exactly two wrongly addressed envelopes

There are four Envelopes with letters. Two are chosen Randomly and opened and found that they are wrongly addressed. Find the Probability that there are exactly two wrongly addressed envelopes. My ...
0
votes
2answers
63 views

Combinatorics question - seats

In how many options can we arrange random number of men (identical men) in line of 15 chairs but: 1. 2 men can't sit next to each other. 2. next to each empty chair - there is at least one men. i ...
1
vote
1answer
39 views

The least number of DAG's out there

I found a statement in a book that I don't understand, it suggests that the number of DAGs on N nodes can be bounded from below by $$\prod \limits^N_{n=1} 2^{n-1} = 2^{N(N-1)/2}$$ My way of thinking ...
0
votes
1answer
40 views

computing the chromatic polynomial for a graph resulted from merging $n$ forests

Let $G=(V,E)$ be a connected undirected graph such that $E$ is the union of $n$ forests $F_1\cup F_2 \cup \dots \cup F_n$. Each forest has $V$ as its nodes and containts $k$ disconnected components. ...
2
votes
2answers
76 views

I am confused on how to solve a question by using burnside's lemma:

How many ways are there to color the ten balls of a triangular array that is free to rotate using 2 colors? The triangular array is arranged such that a single ball is in the apex [first row]; the ...
0
votes
1answer
20 views

Packing distinguishable objects into boxes

How many ways are there to pack $18$ different books into $6$ boxes with $3$ books each if (a) all $6$ boxes are sent to different addresses? (b) all $6$ boxes are sent to the same address? (c) ...
1
vote
2answers
49 views

Choosing two people from 2 boys and 2 girls

If you have 2 boys and 2 girls, how many ways are there to choose two people? One possible answers comes from saying that there are two possible genders for the first person and two possible ...
0
votes
1answer
42 views

I am having trouble understanding Polya's theorem and how to apply it to the following question:

How many ways are there to color the vertices of a 3 x 5 card (rectangle) that is free to move in 3-space using m colors? I am having trouble determining the rotations; I can sort-of understand ...
0
votes
1answer
62 views

Show $\large\sum\limits_{j=0}^{r}\binom{j+k-1}{k-1}=\binom{r+k}{k}$

Show $\large\sum\limits_{j=0}^{r}\binom{j+k-1}{k-1}=\binom{r+k}{k}$ Hint: Place $r$ balls in $m$ urns, in how many of this arrangements can you find $b$ balls in the first urn. I'm sure that ...
0
votes
1answer
27 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
0
votes
2answers
77 views

Combinatorics and probability: size of sample space

I'm having a tough time finding the next example's sample space's size: We have at our disposal the following: the three letters $\;a,b,c\;$ , and the five digits $\;1,2,3,4,5\;$ . We have to form ...
1
vote
1answer
67 views

Number of ways to partition a set of balls of two colors into k urns

A set of $n_1$ green and $n_2$ red balls, where $n_1 + n_2 = n$, is to be partitioned into $k$ urns. Both the balls and the urns are indistinguishable (unlabeled). How many ways to do the ...
0
votes
1answer
25 views

Minimum number of consecutive elements that must be chosen when choosing $\frac{3n}{4}$ elements from a sequence of length $n$

Given a sequence of length $n$, $S = (x_1 \cdot x_2 \cdot \ldots \cdot x_n$), I need to choose $\frac{3n}{4}$ elements such that I minimize the choice of consecutive elements (called a "square"). ...
0
votes
1answer
39 views

counting lattice paths with turns

I want to count words weighted by the number of "turns". Pascal's triangle counts words of length $n$ with $k$ elements as explained in the binomial theorem : $$(x+y)^n = \sum x^k ...
4
votes
1answer
192 views

How prove this $|S_{1}|-|S_{2}|\le 2^{2n}\binom{2n}{n}$

Question: Let $n\in \mathbf N^{+}$,and define set $S=\{1,2,\cdots,4n\}$, for any $ a<b\in \mathbf R^{+}$, define $$S_{1}=\{\,X\mid X\subseteq S,a\le S(X)\le b,S(X)\equiv 1\pmod 2\,\}$$ ...
1
vote
3answers
49 views

How to find exponent of a number in a combination?

How do I find the exponent of $7$ in $^{100}C_{50}$ that is, $\dfrac{100!}{(100-50)!\cdot 50!} =\dfrac{100!}{50!\cdot 50!}$, this question was out of the blue, and I haven't been able to find any ...
1
vote
1answer
58 views

Catalan numbers with both prefix and suffix

In one of the applications of Catalan number,it calculates the number of Dyck word in which a string consisting of n $X's$ and n $Y's$ such that no prefix of the string has more $Y's$ than $X's$, and ...
2
votes
2answers
98 views

Is the complement of the inversion relation (in the context of permutations) transitive?

I'm studying from An Invitation to Discrete Mathematics where I came upon an exercise which confuses me. Let $\pi$ be a permutation of the set $\{1,2,\dots,n\}$ and let $I(\pi)$ denote the set of ...
4
votes
0answers
205 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
3
votes
1answer
38 views

Induction help for a Combinatorics problem.

I've been asked to prove the following problem with induction and I'm not sure how proceed. $\textbf{Given}$ $\frac{1}{1-z}=\sum^\infty_{k=0}z^k, |z|<1$ $\textbf{Prove}$ $\forall ...
3
votes
1answer
41 views

Find the Generating Function with respect to n

The following is a problem from Chapter 2 of Herbert Wilf's generatingfunctionology: Let $S$ and $T$ be two fixed sets of nonnegative integers. Let $f(n,k,S,T)$ denote the number of ordered ...
20
votes
2answers
2k views

How to reverse the $n$ choose $k$ formula?

If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below: $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$ What if I want to go the ...
0
votes
1answer
34 views

How many different $4$-digit numbers can be made from digits of number 4426269$ with given rules?

How many different $4$-digit numbers can be made from digits of number $426269$ with given rules if every digit can appear the number of times it appears in the number $426269$ ($2 \times 2, 2 \times ...
0
votes
1answer
76 views

Arrangements of all the letters in the word “rearrangement” with the r's being adjacent

If an arrangement of all the letters in the word "rearrangement" is chosen at random, what is the probability that all the r's are adjacent? Can someone give me a hint?
0
votes
0answers
30 views

A p-Sylow-subgroup of the group $GL(n, \mathbb{F}_p)$ for prime $p$ and $n\geq 2$

I would like some help to handle the following matter: I have to find a p-Sylow-subgroup of the group $GL(n, \mathbb{F}_p)$ for prime $p$ and $n\geq 2$. My own tries I guess I have to know how ...
0
votes
1answer
22 views

Combinatorics questions: returning $n$ hats to their owners

Lets say there are $n$ hat wearing people entering a restaurant. When they enter, a waiter takes their hats. Upon leaving, the waiter returned the hats. How many ways are there for the waiter to ...
0
votes
1answer
49 views

Help with counting problems

So this is the question i am having problem with: 1) in how many ways can the letter a,b,c,d,e,f be arranged so that the letter a and b are next to each other, but a and c are not. i know that if a ...
1
vote
1answer
27 views

Arranging $m$ edges on a graph of order $n$.

I am new to graph theory and combinatorics, and thought of a question yesterday that I couldn't find the answer to. Is there a formula for counting the number of ways to arrange $m$ edges on a ...