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
2answers
15 views

How many different ways of displaying prints

Magda has 6 different prints that she wants to hang on her bedroom wall, but she has room to hang only 2 of them. In how many different ways can she display the prints on her wall? I tried $6 \times ...
1
vote
0answers
24 views

Interesting combinatoral identity

With the help of Mathematica I have discovered a following identity. Let $T>1$ be an integer, $x$ be a real number and let q be a positive even integer and $l=0,1,\cdots,q/2$. The following ...
0
votes
4answers
27 views

Probability: Linear Seating Arrangement

Okay, I'm new at probability and statistics, so please try to answer this as thoroughly as possible and explain why you did everything, from using a specific number to why using factorials and ...
0
votes
2answers
22 views

Given the sizes of various intersections, find the size of the union.

in a certain examination, 72 candidates offered maths, 64 offered English, 62 offered French, 18 offered maths and English, 24 offered maths and French, 20 offered English and French and 8 offered ...
0
votes
3answers
59 views

How to use stars and bars(combinatorics)

How to use the stars and bars method? Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$ Where $x_i\in\mathbb{N}$ Is this the correct time to apply the method?
1
vote
0answers
15 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
29 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
1
vote
1answer
11 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
2
votes
1answer
24 views

Vocal group no two singer stand next to each other?

A vocal group consisting of alf,bill,cal,deb,eve, and fay are deciding how to arrange themselves from left to right on a stage How many way to do this if Alf and Fay are the least skilled singer and ...
1
vote
0answers
19 views

Vocal group couples ordering

A vocal group consisting of alf,bill,cal,deb,eve, and fay (3 boys and 3 girls) are deciding how to arrange themselves from left to right on a stage. How many ways to this if There are 3 couples (Alf ...
1
vote
1answer
10 views

Combination selecting a vocal group

A vocal group consisting of alf,bill,cal,deb,eve, and fay (3 boys and 3 girls) are deciding how to arrange themselves from left to right on a stage. How many way to do this if A. The boys should be ...
3
votes
5answers
109 views

Computing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$

I came across this while trying to solve Google's boys & girls problem, and although I know now it's not the right approach to take, I'm still interested in summing ...
0
votes
0answers
26 views

Proving that number of codes with even weight is the same as number of codes with odd weight for a specific code book

Consider the $[n,n]$ code-book $C_0=\{0,1\}^n$ with $n$ being odd and the codes $c_i \in C_0=[c_1,c_2,...,c_{2^n}]$ being sorted in the ascending order of hamming weight (from $0$ to $n$). Now let's ...
2
votes
0answers
39 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
0
votes
1answer
32 views

Non-punctual Boundary

In the book of Bill Thurston, Three dimensional geometry and topology, there is an exercise to show torus can be partitioned into 7 countries, each on one piece and has common (non-punctual) ...
2
votes
1answer
53 views

Stair flight problem

A stair flight has 10 steps. A kid can move in jumps of 1, 2 or 3 steps. Assume the kid starts on the floor (step 0), and always has to end in step 10 because there is a door that needs to be open. In ...
2
votes
1answer
61 views

What is $\lim_{n\to \infty}\frac{2n \choose {n}}{4^n}$? [duplicate]

What is the result of the following limit? $$\lim_{n\to \infty}\frac{2n \choose {n}}{4^n}$$ since $$\sum_{k=0}^{2n}{2n \choose {k}}=2^{2n}=4^n$$ then $$\frac{4^n}{2n+1}\leq{2n \choose {n}}\leq 4^n$$ ...
1
vote
1answer
28 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
2
votes
3answers
262 views

Probability of dying from smallpox?

A family of four is infected with Variola major. There is a fatality rate of 30%. Calculate the probability that... Here are my attempts, The probability that nobody dies, ...
0
votes
0answers
29 views

Given a particular order how many times will it appear in all the possible permutations it has?

I have $10$ different coloured balls. I'm interested in selling them in packs of $15$ and the order is important. I know there are $10^{15}$ different ways of arranging these balls if I include the ...
0
votes
2answers
43 views

Sequence for number of seating arrangements. [on hold]

I have a problem: Find the number of unique ways to seat $n \in \{2,3,4\}$ guests at a round table. When seating guests at a round table two arrangements are considered the same if each person has ...
1
vote
2answers
19 views

Compensation Question

I want to create a compensation system which takes into account two variables. Lets say I have $1M to distribute among ten employees who produce widgets. I want to compensate each employee by two ...
2
votes
1answer
59 views

How many ways to do choose $\leq 10$ from $5$ sets of $30$ objects.

I have $5$ sets of letters each of size $30$ each. More specifically I have thirty 'a's,'b's,'c's,'d's and 'e's. How many ways can I choose to paint $10$ or less of them? So I seem to have $x_1 + ...
1
vote
2answers
79 views

Number of solutions to $a+b+c+d=14$

Where $a,b,c,d\in\{0,1,2,\ldots\}$. I understand how to find to solution (now), however I'm asking why a particular method I tried failed to work. I imagined laying out $14$ objects in a row, and ...
1
vote
1answer
33 views

For an alphabet of size $N$, how many strings have all of its substrings of length $\geq 2$ unique?

For an alphabet of $N$ characters, how many strings can be formed (including the empty string) so that no substring of length $\geq 2$ appears more than once in the string? The maximum length of such ...
1
vote
0answers
23 views

Counting zeros in a factorial(terminal + zeros in between digits)

The usual counting zeros in a factorial asks to count only the terminal zeros.This question, which also asks to count the zeros that are in between digits,for example, 8! (40320, has a zero between 4 ...
1
vote
2answers
62 views

Pulling aces from a split deck

I have a normal deck of 52. I pull the aces, deal it in to 4 piles of 12, and put an ace in each pile. I shuffle each pile like a monkey on meth. I flip cards from one pile, and when I see its ace ...
0
votes
0answers
13 views

Quotients in exterior products

I just started learning exterior products. The way I understand it, one can associate a subspace with with a bunch of spanning vectors using an alternating multilinear form. The 'k-blade' remains ...
0
votes
3answers
19 views

Game of Score Four

How many possible sequences of length 64 and made from the characters 0123456789ABCDEF are there, where each character appears exactly 4 times. (This is no homework! I am trying to calculate an upper ...
2
votes
0answers
18 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
2
votes
0answers
36 views

the numer of monic irreducible polynomials of degree $3$ in $\mathbb{F}_q$

I want to know how hany monic irreducible polynomials of degree $3$ there are in a field $\mathbb{F}_q$. The whole number of monic polynomials of degree three is $q^3$. Now I want to find out how ...
0
votes
2answers
35 views

Boxes and colored balls with replacement

Suppose there are $n+1$ boxes numbered from $0$ to $n$. The $i$-th box contains $i$ white balls and $n-i$ black balls. A box is chosen randomly and a ball is selected from the box, after that the ...
1
vote
1answer
56 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
2
votes
2answers
70 views

Pólya's urn scheme, proof using conditional probability and induction

Problem An urn contains $B$ blue balls and $R$ red balls. Suppose that one extracts successively $n$ balls at random such that when a ball is chosen, it is returned to the urn again along with $c$ ...
1
vote
3answers
58 views

Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts

A partition of the set $\{1, 2, . . . , n\}$ into $k$ parts is a way of writing the set as a disjoint union of $k$ subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup\{2, 3\} \cup \{5\}$ is a ...
2
votes
1answer
25 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
0
votes
1answer
27 views

Dice, balls and boxes probability problem (conditional probability)

Problem Suppose there are two boxes $A$ and $B$ such that $A=\{\text{5 red balls and 3 white balls}\}$, $B=\{\text{1 red ball and 2 white balls}\}.$ A dice is thrown, if the result is $3$ or $6$, a ...
2
votes
1answer
35 views

Colored balls in three boxes (conditional probability problem)

Problem Suppose there are three boxes numbered with twenty balls in each of them. The first box contains twenty white balls; the second, fifteen, and the third,ten; the rest of the balls are black. ...
1
vote
1answer
49 views

Find all the compositions of two function. [on hold]

I need to know that given two functions $f(x)=\frac{x-3}{x-2}$ and $g(x)=3-x$ in how many forms do I can compose these two functions, I have: $f \circ g, g\circ f, f\circ f, g\circ g, f\circ ...
2
votes
1answer
69 views

A possible incorrect application of Law of Large numbers

A friend left this teaser for me. He asked me to first compute: $$ \lim_{n \to \infty} \frac{\binom{2n}{n}}{2^{2n}}$$ Using Stirling's approximation (and another method), I got the answer as $0$. ...
0
votes
0answers
29 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
2
votes
2answers
24 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
0
votes
1answer
73 views

Find if permutation is possible

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we ...
2
votes
1answer
48 views

Counting problem, given a finite field and number variables

Let $F_5= {0,1,2,3,4}$ the finite field with 5 elements and let $S=F_5[x_1, x_2, x_3, x_4, x_5, x_6, x_7]$ the ring of polynomials over the $F_5$ field with 7 variables. 1) How many monomials of ...
2
votes
2answers
55 views

Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
1
vote
2answers
26 views

Ice cream combinatorics question

An ice cream shop sells ice creams in $5$ possible flavours: vanilla, chocolate, strawberry, mango and pineapple. How many combinations of $3$ scoops cone are possible? [note: repetition of flavours ...
0
votes
2answers
70 views

If bridges between islands collapse independently with probability $p$, what is the probability that islands remain connected?

This is a follow-up to Probability Question: Bridge problem. There are $n$ islands in the ocean. Each island is linked by a single bridge to each other island. The probability of each bridge ...
1
vote
1answer
43 views

Probability Question: Bridge problem

There are $n$ islands in the ocean. Each island is linked by a single bridge between each and every unique pair of islands to ensure no island is isolated from the others. The probability of each ...
-1
votes
0answers
44 views

Count Triangular Triplets

Given a range [L,R] we need to calculate numbers of such triplets [A,B,K] which follows A+B=K where A,B are any two triangular numbers and K must be in an ...
0
votes
1answer
31 views

Probability formula related to distribution balls in boxes.

Problem Suppose there is a distribution of $N$ distinct balls in $n$ different boxes such that each ball has the same probability to be in any box. Let $A_i=\{\text{the i-th box is not empty}\}$. ...