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)

0
votes
2answers
97 views

Catalan numbers and triangulation

Assume $C_n$ is the number of triangulations of a polygon with $n+2$ sides. Using a combinatorial proof, show that $(4n+2)C_n=(n+2)C_{n+1}$. I don't even know where to start with this one. I ...
1
vote
2answers
40 views

Subsets with 3 consecutive terms

Consider the following set: $$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$ I want to calculate how many subsets of length $6$ have no three consecutive terms. My idea was to do: length 6 have no ...
1
vote
2answers
68 views

Setting up an inclusion-exclusion question

What is the number of one-to-one functions $f$ from the set $\{1,2,...,n\}$ to the set $\{1,2,...,2n\}$ so that $f(x) \neq x$ and $f(x) \neq 2n - x + 1$ for all $x$? I'm getting that the number of ...
5
votes
2answers
54 views

Find the number of tuples consisting of $0, 1$ and $3$

How can I find the number of tuples $(k_1, k_2, ...,k_{26})$ such that each $k_i$ equals $0, 1$ or $3$ and $k_1 + k_2 + ... + k_{26} = 15$. I can reduce this problem to finding the coefficient of ...
0
votes
0answers
35 views

Combinatorics problem - arranging a ping pong tournament

There is a ping pong tournament between $8$ players being held for which the following rules hold: -Everyone will play with everyone else exactly once. -If in the $i$-th round there is a match ...
4
votes
5answers
111 views

Explain Why ${21 \choose 2}^2 - {21 \choose 2} = 3!{22 \choose 4}$

I was given this little problem for precalc homework after a class discussion on series and sigma notation, and applying combinatorial approaches to them. We happened upon the equation in a larger ...
0
votes
1answer
20 views

Good book on combinatorics for beginners in statistical mechanics

Im studying stat mech and i want to have a better understanding on counting microstates. What book in combinatorics do you guys recommend for beginners like me? Thanks in advance
1
vote
1answer
30 views

How many 2-dimensional subspaces is a 1-dimensional subspace contained in?

V is a 3-dimensional vector space over some field K of order 2. There are seven 2-dimensional subspaces, and seven 1-dimensional subspaces, using ${n\choose k}_q = ...
0
votes
1answer
45 views

In how many ways can 3 integers (not necessarily distinct) be chosen from {1 to 100} so that their sum is even

I dont get the solution. SOLN: Case 1: 3 even. The answer is (52C3)= 22100. Case 2: 2 odd 1 even. (50C1)x(51C2))= 63750. Thus ans = 22100 + 63750 = 85850
2
votes
0answers
38 views

Positive integers $<100000$, how many contain exactly one $3$, one $4$ and one $5$

So I use $5$ positions for range $00000$ to $99999$ Choose $3$, choose $4$ and choose $5$ as follows: $5C1 \cdot 4C1 \cdot 3C1$ Remaining $2$ digits have $7$ possible digits as input Ans: $5C1 ...
3
votes
1answer
42 views

Painting a 2x2 Grid

We have a 2x2 grid and 10 different colours. I want to paint such that adjacent grids are painted with different colors. How many ways can i do this? ...
0
votes
0answers
16 views

Inclusion/exclusion argument for partitions

My question regards Frobenius partitions, or $F$-partitions for short, of a number $n$. A short explanation of the concept is linked below. Specifically, my question is as follows. $F$-partitions of ...
1
vote
0answers
42 views

Permutation of people and teams

Suppose 20 people attend an event where there is 4 different activities to do. Suppose we want to split the group in subgroups, each subgroup attending one session of an activity, then moving on the ...
1
vote
2answers
23 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
1
vote
4answers
84 views

Find the limit of $\frac{n^4}{\binom{4n}{4}}$ as $n \rightarrow \infty$

$\frac{n^4}{\binom{4n}{4}}$ $= \frac{n^4 4! (4n-4)!}{(4n)!}$ $= \frac{24n^4}{(4n-1)(4n-2)(4n-3)}$ $\rightarrow \infty$ as $n \rightarrow \infty$ However, the answer key says that ...
1
vote
2answers
48 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
3
votes
1answer
118 views

Film Academy “Oscar”

A committee of $3366$ film critics are voting for the Oscars. Every critic voted just an actor and just one actress. After the voting, it was found that for every positive integer $n \in \left\{1; 2; ...
0
votes
0answers
15 views

Constructing partial Steiner triple systems

Is there a general way to construct a partial Steiner triple system? There are algorithms to construct complete Steiner triple systems for $n \equiv 1, 3 \bmod 6$. From complete Steiner triple ...
1
vote
0answers
35 views

Number of ways you can visit places

A country has n cities, each of which is connected by road to every other city. A tourist wants to tour the country in such a way that starting from city $1$, she visits each city exactly once, and ...
2
votes
3answers
57 views

In how many ways can four integers be selected from $1, 2, 3, \ldots, 35$ so that the difference of any pair of the four numbers is at least $3$? [closed]

I want to choose $4$ integers from the numbers $1$ to $35$. Condition: The difference of any pair of the $4$ numbers should be $\geq 3$. How do I model this problem?
0
votes
0answers
33 views

In how many different ways can a schedule be created for all rounds in a ping pong table tournament?

In a ping pong table tournament participate 8 competitors and the following rules apply: Each competitor plays with every other competitor exactly one match If in the $i$-th round there ...
2
votes
1answer
28 views

Probability of getting exactly $\alpha$ “A” runs and $\beta$ “B” runs in a randomly drawn word

Let $a, b \in \mathbb{N}$. Each "word" that we can form using exactly $a$ times the letter $"A"$ and $b$ times the letter $"B"$ is written onto a card. Next, one of these $\pmatrix{a + b \\ a}$ cards ...
0
votes
1answer
50 views

How many number of functions are there?

$A=\{1,2,\dots,10\}$ Define $f:A \rightarrow A$ then $f^{30}(x) = x$ ($30$ times composite of $f(x) = x$ and the number $30$ is the least number for $f$ to become an identity function) How many ...
2
votes
2answers
47 views

Combination and Probability

There are n students and n+2 different gifts. Each student have to receive 1 gift package. How many ways can we give out all the gifts. ...
3
votes
2answers
46 views

Extract coefficients for a formal power series using Lagrange Inversion Formula

Given $f(x)$ is a formal power series that satisfies $f(0) = 0$ $(f(x))^{3} + 2(f(x))^{2} + f(x) - x = 0$ I know that the Lagrange inversion formula states given f(u) & $\varphi(u)$ are formal ...
0
votes
1answer
22 views

Generating function for multiset formula

It's said that the generating function for $g(x) = \sum_{d=0}^\infty {d+m-1 \choose m-1} x^d$ is equal to $\frac{1}{(1-x)^m}$. In the proof that I have seen it states that: By the geometric series, ...
1
vote
4answers
31 views

A team squad combination and probability problem

A team of 11 is chosen randomly from a squad of 18. Two of the squad are goal keepers and one of them must be chosen. If neither of the goalkeepers is captain or vice captain, what now is the ...
1
vote
0answers
17 views

$D_n$ is the number of derangements of $n$ objects, $P_n$ the number of permutations of $n$ objects with one fixed point. Find $D_{n-1}$

Let $D_n$ be the number of derangements of $n$ objects and $P_n$ be the number of permutations of $n$ objects with exactly one fixed point. How to find $P_n$ in terms of $D_{n-1}$? After putting some ...
1
vote
1answer
19 views

Prove continuity of a function from $S^n$ to $\Bbb R^n$

Given an interval $k$-coloring of $[0,1]$, define a function $f: S^k \to \Bbb R^k$ as follows ($S^k$ is the $k$-sphere). Let $x = (x_1,x_2,...,x_{k+1})$ be a point on the $k$-sphere $S^k$. Define $z = ...
1
vote
1answer
23 views

Question 3(c), pg-7, Introduction to Topology and Modern Analysis, Simmons

The question says: Let $U$ be a set $ \{ 1, 2, . . . , n \}$ for an arbitrary positive integer $n$. How many subsets are there? How many possible relations of the form $A \subseteq B$ are there? Can ...
4
votes
1answer
40 views

What is wrong with my combinatorics method?

Suppose I want to select a team of $7$ from a pool of $10$ from $A$, $8$ from $B$ and $5$ from $C$. However, I want to make sure that I have at least one from each group. My idea was to do the ...
3
votes
1answer
24 views

When is the intersection of $k$ sets non-empty?

Suppose, given a ground set $S$, we have two subsets $A,B \subseteq S$. If we know that $|A|, |B| > \frac{|S|}{2}$, then we know that $A \cap B \neq \emptyset$. Can this be generalized to $k$ ...
-1
votes
0answers
22 views

Multiset Combination without repetition

Now, How should we find the r-combinations of a multiset without repetition? Well, If there are repetitions allowed then we use ${k+r-1\choose r}={k+r-1\choose k-1}$. What should we do when ...
0
votes
0answers
12 views

Smallest Parameter to Satisfy Exponentially Scaled Binomial Coefficient Inequality

Let $t$ be given, I am mainly interested in large $t$. Define $m(t)$ as below $$ m(t)=\min\left\{m: \sum_{k=0}^m \binom{t+k-2}{k} 2^{t+k} \geq 2^{2t}\right\}. $$ Is there a nice estimate for $m(t)$? ...
2
votes
1answer
25 views

Expectation of the fraction a random function covers its range

Preamble: The number of onto functions from a set of $m$ elements to a set of $n$ elements is, as stated in this answer, computed as follows: $$n!{m\brace n}\;.$$ Now, let's count the number of ...
0
votes
2answers
41 views

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?, assuming that the coins all have different dates and so are distinguishable from each other, and the ...
0
votes
1answer
34 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
2
votes
2answers
49 views

Catalan numbers formula derivation

I'm trying to follow a proof of the Catalan numbers being equal to $\frac{1}{n+1} {2n \choose n}$ from the recurrence relation $C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_{1}+C_{n-1}C_0$ Now it's seen ...
6
votes
0answers
57 views

When can we quit a game of War?

Consider the game of War. (The rules are below.) It would be nice to be able to end the game early. Suppose, for example, one player has 50 of the 52 cards. It is very likely that he's going to win. ...
0
votes
0answers
18 views

name for pairs without repetition

Let $X:=\{x_i\}_{i=1}^k$, $Y:=\{y_i\}_{i=1}^k$, $\sigma$ a permutation on the index set $\{1,...,k\}$. Is there a name for the following set and or for an element in it: ...
4
votes
0answers
29 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
1
vote
0answers
23 views

Understanding the expansion of product notation.

I have a question regarding the expansion of product notation in the picture below. Equation 3.1 in the attached picture is ...
3
votes
3answers
112 views

Powers of two with coefficients $\{1, -1\}$

Given a vector $(n_0, n_1, \dots, n_l)$ where $n_i \in \{-1, 1\}$, $i = \overline{0, l-1}, n_l = 1$ and $l \in \mathbb{N}$. Prove that for all $a$ such that $$0 < a \leq 2^0n_0 + 2^1n_1 + \dots + ...
0
votes
2answers
14 views

Whether the equality $C^{m}_{2m}=\Sigma_{i=1}^{m}C^{i}_{m+1}C^{i-1}_{m-1}$ holds or not?

I've tried some values of $m$, and found that the equality $C^{m}_{2m}=\Sigma_{i=1}^{m}C^{i}_{m+1}C^{i-1}_{m-1}$ holds. But I can't give it a proof. Can anybody give some suggestions?
0
votes
1answer
14 views

Counting monomials with $k$ variables

Say we expand $\left(\sum_{i=1}^n x_i\right)^k$ into monomials. If $k=3$ there are $3n(n-1)$ monomials with two variables: $3x_1x_2^2 + 3x_1x_3^2 +\dots + 3x_1^2x_2 + \dots$. Is there a closed form ...
0
votes
3answers
30 views

Iteration of $A_{n}(q)=q^nA_{n-1} (q)$

I can't seem to find how $A_{n}(q)=q^nA_{n-1} (q)$ iterates to $$A_{n}(q) = q^{n+1 \choose 2}A_{0}(q)$$ Where ${a \choose 2} = a(a-1)/2$ and absolute value of q is less than 1. I understand that I ...
0
votes
2answers
35 views

Laurent Series Expansion Logic

Relative to the below image, I am curious about the progression from equation 3.2 to equation 3.3, then from equation 3.3 to equation 3.4. I understand the logic in 3.2. I understand that a Laurent ...
3
votes
3answers
39 views

Intuitive proof for a Combinatorial Problem

Given a set $S$ such that $|S|=N$ and $S$ contains exactly $K$ $0$s $(K >0)$ and $N-K$ $1$s, then exactly half of the subsets of $S$ contain an $odd$ number of 1s, $indepedent$ of the value of ...
1
vote
2answers
46 views

The number $\binom{8}{4}$ is equal to the number of subsets of size 4 of the set $\{1, \dots, 8\}$

I was asked to proof if is true and give a counter example if it is false. However I prefer True. since all the numbers 1-8 insides the brackets are in the sets. I'm I correct?
1
vote
3answers
52 views

Show Latin Square is not a group.

If we fix the first two rows in the above figure, then there are many ways to fill in the remaining rows to obtain a Latin square. Show that none of these Latin squares is the multiplication ...