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
votes
2answers
25 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
0
votes
2answers
29 views

Method to solve probability of chips

A bag contains six chips, numbered 1 through 6. If two chips are chosen at random without replacement and the values on those two chips are multiplied, what is the probability that this product will ...
1
vote
1answer
104 views

How to convert a problem to a stars and bars problem?

Continued question from here. With certain questions I have $x_i$ being constrained by various different inequalities, I want to know how to remove these from the problem, to bring me back to a ...
-2
votes
1answer
59 views

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}\;$

I am unsatisfied with the answers here. (Half of which used algebraic methods despite being advised not to!) Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$ ...
1
vote
2answers
33 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 ...
0
votes
0answers
50 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
5
votes
1answer
99 views

$X^A \equiv B \pmod{2K + 1}$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$. Is there something special about the modulus being odd that allows us to ...
0
votes
3answers
93 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?
4
votes
3answers
157 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...
0
votes
1answer
44 views

How to evaluate $\sum_{k=0}^{n} \alpha^k \binom{n}{k}$?

I am trying to show that the function that satisfies $f^\prime(x)=f(x)$ with $f(0)=1$ behaves in an exponential way (in other words, I want to justify writing it as $e^x$). I need to show that: $$ ...
11
votes
3answers
210 views

Deducing correct answers from multiple choice exams

I am looking for an algorithmic way to solve the following problem. Problem Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
-5
votes
0answers
19 views

<html5> draw circle by arc and triangle [on hold]

I want if click the retacgle, draw a triangle around the circle. source code like this... but, triangle was not good each of positions.. How can i draw a triangle around the circle like attached ...
0
votes
1answer
234 views

Combinatorics and Inversion Sequences

Determine the inversion sequence of the following permutation of $ \{ 1,\ 2, \cdots , 8 \}$. $$ 83476215 $$ I just don't understand how that is converted into a series of numbers 0, 1, and 2 and ...
5
votes
3answers
1k views

How many 7-digit even numbers less than 3000000 can be formed using all the digits 1,2,2,3,5,5,6?

I've somewhat got this question down but I'm only half way. How many $7$-digit even numbers less than $3,000,000$ can be formed using all the digits $1,2,2,3,5,5,6$? So I figured that there's ...
2
votes
1answer
8k views

How can I calculate the number of potential combinations in a password?

If I create a $10$ digit password with the following requirements: At least one uppercase letter A-Z - $26$ At least one lowercase letter a-z - $26$ At least one digits 0-9 - $10$ At least one ...
2
votes
2answers
37 views

Collision of 8 Digit, Base-36 Numbers

I have an algorithm that generates a random 8 digit, base 36 number with uniform distribution. Thus, this algorithm can generate $36^8$ unique numbers. I run my algorithm 10,000 times, and write ...
4
votes
2answers
366 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
0
votes
2answers
16 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
1answer
224 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
0
votes
4answers
35 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
27 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 ...
1
vote
0answers
22 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
38 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 ...
0
votes
0answers
34 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 ...
3
votes
5answers
112 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 ...
2
votes
2answers
160 views

If a 3D-cake is cut by $n$ planes yielding the maximum number of pieces, then what is the number of pieces with the cake crust?

It is known that a 3D-cake can be cut by $n$ plane cuts at most into $N$ pieces, defined by Cake Number $N=\frac {1}{6}(n^3+5n+6)$. However, some of the pieces would have a crust of the cake as one of ...
1
vote
1answer
21 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 ...
1
vote
0answers
27 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
13 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 ...
1
vote
1answer
30 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
1answer
57 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
0answers
43 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
33 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
64 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$$ ...
0
votes
1answer
70 views

Are there magic knight tours on a $6\times6$ or $10\times10$ board?

In mathworld, magic tour, it is mentioned that for odd $n$, only semimagic knight tours are possible on a $n\times\ n$ - board. For $n = 8$, it has been verified that there are no magic knight ...
2
votes
3answers
263 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
31 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 ...
2
votes
1answer
276 views

Manipulation of Geometric Series and Binomial Theorem

I was just hoping to confirm that the following manipulations make sense: Say I begin with $\frac{1}{(1-x)^n}$. Then we have $(1-x)^{-n} = $$\sum$ $-n\choose k$ $(-x)^k$ = $\sum$ $(-1)^k$ $n+k-1 ...
0
votes
2answers
52 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 ...
2
votes
1answer
60 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 + ...
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 ...
1
vote
2answers
80 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 ...
8
votes
0answers
142 views
+100

How to estimate $Pr[vr_i=ur_i]$ in the presence of rotations

Suppose we want to compute the probability that for two different random vectors (with elements that are $0$ or $1$), denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ ...
1
vote
1answer
34 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
2answers
69 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 ...
1
vote
0answers
24 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 ...
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 ...
0
votes
0answers
15 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
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}\}$. ...
2
votes
0answers
19 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 ...