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
33 views

Limit of double sum involving binomials

I am trying to get a meaningful interpretation of the behaviour of the following double sum in the limit of a large $t$ and small $p$. I look at its value as a function of $\beta$. Here's the sum: ...
1
vote
2answers
94 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 ...
3
votes
1answer
463 views

General formula or a pattern for the $n$th derivatives of $e^{f(x)}$?

I want to find the $nth$ derivatives of the function $e^{f(x)}$ with respect to $x$, the first derivative is $$e^{f(x)}f^{\prime}(x).$$ The second derivative is $$\left( {\frac {d^{2}}{d{x}^{2}}}f ...
0
votes
0answers
13 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.)
12
votes
1answer
392 views

Fibonacci, compositions, history

There are three basic families of restricted compositions (ordered partitions) that are enumerated by the Fibonacci numbers (with offsets): a) compositions with parts from the set {1,2} (e.g., 2+2 = ...
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
57 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 ...
0
votes
0answers
21 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 ...
1
vote
0answers
31 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 ...
3
votes
2answers
64 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
2answers
28 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 ...
14
votes
1answer
253 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
1
vote
0answers
47 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
0
votes
1answer
37 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
15 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 ...
0
votes
1answer
35 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
18 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
9 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
3answers
33 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 ...
4
votes
1answer
110 views

Identity with Catalan numbers

How would you prove the following identity $$ \sum_{1\leq j<j'\leq n} \prod_{k\neq j,j'}^n \frac{(j+j')^2}{(j-k)(j'-k)} = C_{n-2} $$ where $C_k$ is the $k$-th Catalan number defined as $$ C_k = ...
0
votes
0answers
43 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
41 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 ...
0
votes
3answers
32 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 ...
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 ...
1
vote
1answer
29 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 ...
2
votes
1answer
15 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? ...
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 ...
3
votes
1answer
70 views

Probability of at least m in a row out of n? (generic formula)

In a previously asked question of mine, I was specific in asking for a 75% freethrow shooter, what is the probability he would make at least 5 freethrow shots in a row out of 10. That means he would ...
4
votes
1answer
236 views

Finding intersecting subsets for given binomial coefficient

My apologies if this question is more appropriate for mathisfun.com, but I can only get so far reading about combinatrics and set theory before the interlocking logic becomes totally blurred. If this ...
1
vote
1answer
42 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 ...
0
votes
2answers
39 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.
3
votes
2answers
62 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 ...
1
vote
1answer
50 views

Combinatorics of a tournament where one wins by taking either three games in a row or four in total

Two teams play each other repeatedly until either one of them wins three games in a row or one of them wins a total of four games. What are all the ways in which the tournament can be played? What ...
1
vote
3answers
61 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 ...
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
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?
3
votes
3answers
461 views

Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive ...
1
vote
2answers
18 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
1answer
20 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
23 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 ...
0
votes
1answer
27 views

How to distribute groups over activities in rounds

I typed out my problem in a Latex file and I will add an image of it here: If anyone could help me how to solve this problem that would be amazing. Thank in advance. Boris
10
votes
1answer
140 views

How many arrays with crossed cells, order of rows/columns irrelevant

I've been struggling with this simple problem for months though as I am a newbie to… well, maths, there's high chance someone more educated than myself may get it right! Let's consider an array or a ...
1
vote
4answers
40 views

Having problems proving $ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $

I'm trying to prove the following $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $$ using the identity $$ \sum_{r=0}^{n} \binom{n}{r} = 2^{n} $$ but I'm not able to. This is what I did so far, ...
0
votes
4answers
37 views

How many 3 digit even numbers can be formed using (0, 1, 2, 3, 4) and no repetition?

My solution to the problem is as follows: The answer I get is 27. My reasoning is that the last digit must be even, so for that position there are 3 choose 1 possibilities. Then the first digit ...
0
votes
2answers
25 views

Permutations of a Multi-Set

Find the number of permutations of the multi-set {m.1,n.2}, where m,n $\in N $, which must contain m 1's. I thought the permutation is $\frac{(m+n)!}{m!n!}$ since multi-set is basically a collection ...
0
votes
0answers
21 views

Number of 2n-digit binary sequences

Find the number of 2n-digit binary sequences in which the number of 0's in the first n digits is equal to the number of 1's in the last n digits. I'm not sure how to approach the question. My ...
0
votes
0answers
15 views

Combinatorics or permutations of language? [on hold]

I am looking to understand the combinatorial or permutative space of the English language. 26 letters up to length 25. How big is the space? And if anyone has an algorithm for this in shell or ...
1
vote
2answers
54 views

Grid problem - combinatorics? [on hold]

In a city, streets are laid out as a grid. Your home is at location (0,0) and work is at location (10,10). You walk to work taking only steps up and to the right. (a) How many distinct ways can you ...
3
votes
4answers
77 views

Question about ${n+1\choose k} = {n\choose k} + {n\choose k-1}$ proof?

I've found past proofs of this problem and for the most part I'm able to follow. $$\eqalign{{n\choose k}+{n\choose k-1}&= {n!\over (n-k)!k!}+ {n!\over (n-(k-1))! (k-1)!} \text{ (step 1)}\cr ...
48
votes
7answers
26k views

Probability that random moves in the game 2048 will win

I have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game: If he were to write a ...