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)

1
vote
1answer
37 views

Why is $\frac{2n!}{n^2+n}=2(n-1)!$?

I'm reading a book on combinatorics, and I've been asked to expand and simplify the following: $$\frac{\prod_{j=0}^{n} (j+1)}{\sum_{i=1}^{n}i}$$ Given that: $$\prod_{j=0}^{n} (j+1)=j!$$ and ...
1
vote
1answer
16 views

Number of ways of distributing 7 distinct balls into 7 distinct boxes with exactly one box with 3 balls.

This is what I tried. I can distribute the balls in four ways: 1) 3,1,1,1,1 2) 3,2,1,1 3) 3,2,2 4) 3,4 For 1) I can first pick 5 boxes in ${7 \choose 5}$ ways and then pick 3 balls in ${7 \choose ...
4
votes
1answer
49 views

General term of $(1+x)(1+x^2)(1+x^3)…$?

Is there a closed for the coefficient of $x^n$ in $(1+x)(1+x^2)(1+x^3)\cdots$? If not, then what is the closest to a closed form that anyone has found? (An infinite series that approximates it ...
0
votes
0answers
6 views

Selecting one number from each set with minimum variance

I have a dataset that I need to find several sets of "similar" looking events across many days, which leads to the following problem. Suppose I have $N \sim 500$ sets, each containing $N_j \in [5, ...
0
votes
2answers
18 views

How to calculate the number of ways of partitioning n identical objects into r different groups such that each group has same number of objects?

I was solving the following problem, "Given a collection of 10 identical objects calculate the number of ways in which these objects can be partitioned into 2 groups of 6 and 4 objects each" - for ...
0
votes
0answers
18 views

A question on enumerative combinatorics : k-length subsequence of n-length sequence

Is this a known result? Let $A = (a_1,...,a_n)$ be a sequence of $n$ integers such that $a_1 < a_2 < ... < a_n$. We say a permutation $\sigma$ is $k$-safe if in $\sigma$, no $k+1$ length ...
0
votes
2answers
42 views

Sum of sequence of cubes and summation on the upper index

Express the sum of the sequence of cubes as a polynomial in n using the summation on the upper index formula: $$ \sum\limits_{k=0}^n\binom{k}{m} = \binom{n+1}{m+1} $$ It has been proven that the sum ...
-1
votes
0answers
14 views

Actuarial Interest Problem [on hold]

I am not certain how to solve this problem. Schroeder borrows money to buy a new piano. He agrees to pay back the loan with level annual payments at the end of year for 30 years. The annual interest ...
1
vote
1answer
32 views

How many functions can be constructed?

How many functions $f:\left\{1, 2, 3, 4,5 \right\} \rightarrow \left\{ 1, 2, 3, 4, 5 \right\}$ satisfy the relation $f\left( x \right) =f\left( f\left( x \right) \right)$ for every $x\in \left\{ 1, ...
1
vote
2answers
31 views

Problem proving $ \sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2} $

I'm stuck at proving the following. $$ \sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2} $$ I know that I have to use the Binomial theorem like this, letting x=1,y=n in $(x+y)^{2n-1}$ $$ ...
0
votes
0answers
32 views

How many Possible Combinations exist?

I have $120$ coins and $21$ buckets. Each bucket can hold $0$ to $20$ coins. How many possible coin/bucket combinations are there?
1
vote
1answer
59 views

If 6 different books are to be divided among 3 libraries, each containing precisely 2 books, how many possible divisions are there?

The way I reasoned was that for the first library, there are ${6 \choose 2}$ choices. Then for the second and third libraries, there are ${4 \choose 2}$ and ${2 \choose 2}$ choices respectively. So ...
1
vote
1answer
37 views

Analytic Proof Of ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$

Analytic Proof Of ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$ My Approach Let $x_k$ be one element in a set of $n$ elements. $n-1\choose r-1$ $=$ the number of unique groups of $r$ containing ...
0
votes
0answers
14 views

Understanding why Hall's marriage theorem $\Leftrightarrow$ Dilworth's theorem

Many books say that Hall's marriage theorem is equivalent to Dilworth's theorem. Some use König's theorem to show that, but many just don't prove it at all. Is there any simple approach to understand ...
0
votes
2answers
26 views

Proving $ \sum_{r=0}^{n} \frac{1}{r+1} \binom{n}{r} = \frac{1}{n+1} (2^{n+1} - 1) $

I'm stuck at proving the following. $$ \sum_{r=0}^{n} \frac{1}{r+1} \binom{n}{r} = \frac{1}{n+1} (2^{n+1} - 1) $$ This is what I have so far. $ \sum_{r=0}^{n} \frac{1}{r+1} \binom{n}{r} = (1) ...
0
votes
1answer
39 views

Calculating partitions using multiplication rule

A teacher wants to create 4 study groups of 5 students from a class of 20 students. How many ways are there to do this? The answer is $\binom{20}{5}\binom{15}{5}\binom{10}{5}\binom{5}{5}$. I don't ...
0
votes
1answer
26 views

Problem finding the number of r-element multi-subsets of the multi-set $M=\{ a_{1},a_{2},…,a_{n},m.b \} $

Let $m,n,r \in \mathbb{N}$. Find the number of $r$-element multi-subsets of the multi-set $$M= \{ a_{1},a_{2},...,a_{n},m.b \} $$ when $r \leq m,r\leq n$. Below is the given answer. ...
0
votes
3answers
58 views

Solving Coin Toss Problem

If a coin is tossed 3 times,there are possible 8 outcomes. HHH HHT HTH HTT THH THT TTH TTT In the above experiment we see 1 sequnce has 3 consecutive H, 3 sequence has 2 consecutive H and 7 sequence ...
2
votes
2answers
276 views

How many injective functions are there from {1 2 3} to {4 5 6 7 8)?

My thoughts are that to find the number of injective functions, just multiply 3 and 5 together since there are 3 elements in the first set and 5 elements in the second. Is this the right way to ...
1
vote
1answer
26 views

Distributing M identical objects in N containers with capacity C

What is the number of integer solutions to $x_1+x_2+ \cdots + x_N = M$ where $0 \leq x_i \leq C$ for $i = 1, \dots, N$? (All constants are positive integers.)
2
votes
1answer
154 views

Probability that the second-best player finishes second in a single-elimination tournament, given that better players always defeat weaker players?

A chess tournament (single-elimination format) has 16 players. Suppose that no two players have the same strength, and that each player always defeats the players weaker than himself/herself (i.e. no ...
0
votes
0answers
26 views

Distance between triangles in a pattern

Lets say you have a triangle similar to the one below, with each triangle numbered $(N, i) $ where $N$ is the row number and $i$ is the position within the row. From any triangle, you are allowed ...
0
votes
1answer
19 views

Probability that a company is worth $xM after y years, if its value can only stay the same or double every year?

Let's say a company is worth \$1M. Each year, the value of the company eithers stays the same with probability $\frac{1}{2}$, or doubles with probability $\frac{1}{2}$. What is the probability that ...
1
vote
4answers
68 views

Probability of at least 3 red balls given 4 choices in a bag of 4 red balls and 4 black balls?

Let's say there are 8 balls in a bag, where 4 are red and 4 are black. If I choose four balls from the bag without replacement, what is the probability that I will choose at least 3 red balls? My ...
1
vote
2answers
30 views

Probability of being selected twice in a week given a set of n people?

Let's say a child is selected out of a group of 10 students each day to stay after school and help clean the classroom. What is the probability that a particular child is selected exactly twice during ...
0
votes
1answer
39 views

If 51 mosquitoes are sitting on a square with side 1m, are at least 3 of them within a disk of radius 1/7?

There are 51 mosquitoes on a square-shaped window with side 1 m. Can Stephen kill 3 mosquitoes with a circular plastic disk of radius 1/7 m in a single strike? I know this can be solved by ...
0
votes
1answer
16 views

counting bitstrings of specific length

Is my solution right refarding this question? How many bitstrings of length 77 are there that start with 010 (i.e, have 010 at position 1, 2, and 3) or have 101 at positions 2,3, and 4, or have 010 ...
2
votes
1answer
44 views

Prove $\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}$

How to prove that $$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ? I tried to break the right ...
0
votes
1answer
37 views

Let $S$ be the set of all subsets of size $n$ from the set $\{1, 2, …, 2n\}$.

If $n$ must be greater than or equal to 2, prove that the cardinality of $S$ is a composite number. Any help would be greatly appreciated. Edit: I see now that this is more simply a matter of ...
1
vote
2answers
19 views

K Zeros between 14641

One Writes K- Zeros between every two digits of the number 14641. What is the square root of the number obtained? I want to know if there is a better way of writing out the solution. As of now I know ...
0
votes
0answers
11 views

The Whitehouse simplicial complexes and compositional (Lagrange) inversion

Associahedra and Lagrange inversion of ordinary generating functions (OEIS A133437): For an o.g.f $ f(x)= a_1x+a_2x^2 + \cdots$ with inverse $f^{(-1)}(x)= b_1x+b_2x^2 + \cdots$, the compositional ...
0
votes
0answers
47 views

Door game between alice and bob

Alice and Bob are taking a walk in the Land Of Doors which is a magical place having a series of N adjacent doors that are either open or close. After a while they get bored and decide to do ...
1
vote
1answer
42 views

How many solutions does the equation $2i+j+3k=l$ have in nonnegative integers?

Let $i,j,k$ be nonnegative integers and $l$ be a positive integer. How many solutions does the equation $2i+j+3k=l$ have? For low enough $l$, I can easily find the number of solutions, but is there ...
1
vote
0answers
48 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
0
votes
3answers
34 views

Rewriting an expression

I got the following problem and can't solve it. Factorize the following statement: C(n+2, n) + C(n+3, n+2). So basically they are asking to rewrite the expression as a X*P expression instead of A+B ...
0
votes
3answers
38 views

Using binomial theorem to evaluate summation in closed form

A problem I'm trying to figure out asks that I use the binomial theorem (or any other method I want) to evaluate $ \sum_{k=0}^n \frac{1}{k+1} {n \choose k}$ in closed form. The binomial theorem ...
2
votes
1answer
17 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
1
vote
1answer
30 views

How to figure out the number of possible subsets?

Let S = $\{1, 2, 3, ..., n\}$. Let set A be a selection of integers from S. Let set B also be a selection of integers from set S. How many ways are there of choosing the elements for both A and B ...
0
votes
1answer
25 views

Sequence of polynomials with rational coefficients

Clearly, the set of all univariate polynomials with rational coefficients is countable. That is, we can enumerate the members, say, as $x_1,x_2, \dots ,x_n, \dots $ How can we find $x_n$ for a given ...
1
vote
3answers
33 views

How many poker hands have a pair? (two cards in one denomination)

Poker is played with a regular deck of cards which contains 52 cards. In the deck of cards there are 4 colors, I guess you know them. And each color exists in 13 denominations, I guess you know that ...
3
votes
2answers
77 views

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
1
vote
1answer
46 views

Placing m books on n shelves

If we let m and n be integers with $m \ge n \ge 1$. how many ways are there to place m books on n shelves, if there must be at least one book on each shelf? the order matter. How do I solve this, do I ...
3
votes
2answers
64 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
1answer
19 views

number of vertices a special graph

Suppose a tree G has exactly one vertex of degree i for each 2<=i<=m and all other vertices have degree 1. How many vertices does G have?
0
votes
1answer
22 views

In how many ways can you paint 90 distinct buckets?

In how many ways can you paint 90 distinct buckets, if 25 of them must be painted red, 40 of them must be painted blue, and 25 of them must be painted green? I am right to assume that these object ...
0
votes
2answers
41 views

Solve Identity about Combination

Find the values of a and b such that $\binom{2n}{2} = a\binom{n}{2} + b(n^2)$ This is a past year question about Introduction of Combinatorics in my university.
1
vote
2answers
19 views

How many ways can the school choose a President Vice President?

There are n >= 4 students. The school has a Board of Directors, consisting of one president and three vice-presidents. The entire board consists of four distinct students. How can I prove that ...
1
vote
3answers
63 views

Problem proving $ P_{r}^{r} + P_{r}^{r+1} + … + P_{r}^{2r} = P_{r}^{2r+1} $

Show that $$ P_{r}^{r} + P_{r}^{r+1} + ... + P_{r}^{2r} = P_{r}^{2r+1} $$ where r is a nonnegative integer. This is what I've come up with so far but I'm not sure how to continue. I know I need to ...
1
vote
1answer
23 views

Question about the proof of Ramsey's Theorem

I was reading up on a proof of Ramsey's Theorem and I can't understand this part of the proof: Pick a vertex $v$ from the graph, and partition the remaining vertices into two sets $M$ and $N$, ...
0
votes
1answer
24 views

Find probability of 4th smallest number?

Seven numbers are selected from the numbers (1, 2, 4, 8, 9, 10, 11, 15, 17) without replacement. What is the probability that the 4th smallest number is 9? I'm not sure if I'm getting the correct ...