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
0answers
36 views

About rotations of sets of vertices of a regular $p$-gon.

This is something I've been thinking about lately, and I don't seem to understand the problem well enough. There is a motivation to this problem, but I don't think giving it would be productive since ...
2
votes
1answer
114 views

Bijection Between Binary Rooted Trees and Planar Planted Trees

I was wondering if anyone could describe (or point me too) a description of a bijection between binary rooted trees and planar planted trees. My professor told me that this might be useful to know for ...
2
votes
1answer
90 views

probability convolution problem

Suppose $X,Y$ are uniformly distributed independent random variable on $\{1,...,N\}$ , compute the density of $X+Y$. So the density of $X$ or $Y$ is $f_X (x) = \frac{1}{N}$ (so if we sum the terms, ...
0
votes
2answers
96 views

Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7. So i'm not completely sure how to use strong induction, but the base case is ...
2
votes
2answers
213 views

Question about an 8 sided die

I have a question about an 8 sided die problem. I will put up my work what I have if someone can tell me how to proceed I will appreciate it. We roll an 8 sided die numbered 1 to 8 six times and ...
2
votes
1answer
212 views

Use a chinese abacus to translate hex and decimal numbers?

I read that the Chinese abacus is well suited to hex numbers as well as decimal, because its columns have 5 beads in the lower part, and 2 in the upper. Is there any efficient algorithm for ...
1
vote
2answers
440 views

Rubik's Cube Combination

Could anyone explain why the number of legal or reachable combinations of a $3\times 3\times 3$ Rubik's Cube is $1/12\mbox{th}$ of the total. I understood the logic behind the total number of ...
1
vote
1answer
185 views

Number of ways in which result of games can be predicted correctly

I have found this question: Suppose in a competition $11$ matches are to be played, each having one of $3$ distinct outcomes as possibilities. What is the number of ways one can predict the outcomes ...
0
votes
1answer
40 views

Combinations of various items

How many different combinations of $3$ can you make with $11$ items? I would think the answer to be $11\cdot10\cdot9$ but this is incorrect. Thanks.
-1
votes
1answer
228 views

permutation with cycles

Let $c(n,k)$ be the number of permutations of $[n]$ with $k$ cycles. I am looking for a proof of the following. $c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ for $n,k \geq 1$ and $c(0,0)=1$ The number of ...
0
votes
1answer
172 views

$n=\{1,2,3,\dots,n\}$, How many subsets of cardinality $k$ containing element 1 are in $n$? [duplicate]

Possible Duplicate: Combinatorics: Number of subsets with cardinality k with 1 element. A set n has elements $\{1,2,3,\dots,n\}$. How many subsets does it have of cardinality $k$ and that ...
0
votes
1answer
1k views

Proof that computing composition of permutations is in P

Consider the following problem: A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. ...
2
votes
3answers
94 views

What is the generating function for the negative terms in the integer equation?

Suppose $X_1, X_2$ and $X_3$ are all non-negative integers. So for this linear integer equation: $$X_1 - 2X_2 + X_3 = 10$$ Please note that the coefficient for $X_2$ is negative (i.e. $-2$). What ...
3
votes
2answers
201 views

Prove summation formula for binomial coefficients [duplicate]

Possible Duplicate: simple binomial theorem proof Prove that: \begin{equation} \sum_{k=0}^n \binom{k+a}{k}=\frac{(n+a+1)!}{n! (a+1)!}, \end{equation} where $a$ is a constant, without ...
7
votes
3answers
210 views

How to transform this infinite sum

How to transform this infinite sum $$\sum_{i\geq0}\frac{x^i}{(1-x)(1-x^2)\cdots(1-x^i)}$$ to an infinite product $$\prod_{i\geq1}\frac{1}{1-x^i}$$
4
votes
1answer
174 views

A variant of assignment problem (different sizes of sets)

I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always ...
0
votes
0answers
44 views

generic set definition

What is the exact definition of generic set ? I read the wikipaedia of generic set but I don understand what is stating there. Helps are appreaciated. It will be better if someone can provide me some ...
0
votes
1answer
147 views

In how many ways can the faces of a rectangular box can be painted so that the color changes occur only at each corner?

With three differently colored paints, in how many ways can the faces of a rectangular box can be painted so that the color changes occur only at each corner? I was trying to solve this by ...
1
vote
2answers
88 views

Making a $1,0,-1$ linear commbination of primes a multiple of $1000$

Prove that with every given 10 primes $p_1,p_ 2,\ldots,p_{10}$,there always exist 10 number which are not simultaneously equal to $0$, get one of three values: $-1$, $0$, $1$ satisfied that: ...
3
votes
1answer
273 views

probabilities in Random Graphs

I am trying to find the probability of a bernoulli random graph on $n=10$ vertices with probability that an edge connects any pair of vertices is $p=\frac{1}{6}$ as $n\to \infty$. This is what I ...
0
votes
2answers
319 views

Different recurrence relations that model the same problem

I'm trying to solve the following counting problem, but my answer is different from the textbook's: Find a recurrence relation for the number of n-digit ternary sequences that have the pattern "012" ...
2
votes
1answer
158 views

Combinatoric Selection of Passwords

Give that a password can be 8-12 characters long and each character in the password can be ether composed of upper case letters, lower case letters, numeric digits, or one of the six special ...
0
votes
1answer
199 views

Relative interior of a polytope

Can anyone explain to me what is the idea of relative interior of a convex hull of a set of finite points ? For interior of a set , I understand that it is a set which excludes its boundary. Is ...
1
vote
1answer
151 views

Schlegel diagram of polytope

I'm currently studying polytopes and using the book Lectures in Geometric Combinatorics by Thomas. When I come to Schlegel diagrams, I do not quite understand how to determine whether a Schlegel ...
1
vote
3answers
287 views

Probability question with combinations of different types of an item

Suppose a bakery has 18 varieties of bread, one of which is blueberry bread. If a half dozen loafs of bread are selected at random (with repetitions allowed), then what is the probability that at ...
3
votes
0answers
96 views

How many strings of length n which differ from each other by m or more letters are there?

Alphabet consists of M letters. Strings may have repeats. The question is: how many strings of n letters are there such that every string differs from each other by m or more letters?
3
votes
1answer
103 views

Number of squares in a hypercube

I am trying to count the number of $4$-cycles in the hypercube $Q_n$. Clearly if $x,y$ are two distinct vertices with two common neighbors then we get a $4$-cycle. But how do I count such $x$ and $y$? ...
4
votes
4answers
273 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
2
votes
1answer
133 views

number of ways to travel on L-shaped grid

No. of ways to travel from top left to bottom right in a rectangular grid of width N and height M is given by C(N+M,N).What will be the number of ways to travel from top left to bottom right when a ...
2
votes
3answers
616 views

How to solve second degree recurrence relation?

For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$. But how do you solve second degree? For example $$f(n)=\begin{cases} 1,&\text{for }n=1\\ ...
1
vote
2answers
110 views

A question about combinatorics

You are sorting assigning 6 people, A, B, C, D, E and F, into 3 different hotel rooms. How many ways can they be sorted such that A is in the same room with C, and B is not in the same room with D? ...
4
votes
2answers
1k views

Choosing a 5 member team out of 12 girls and 10 boys

We must choose a 5-member team from 12 girls and 10 boys. How many ways are there to make the choice so that there are no more than 3 boys on the team? The correct answer is $\binom{22}{5} - ...
2
votes
2answers
103 views

How can I solve this probability question?

An experiment consisting of testing calculators one after the other with no replacement until either 2 defective calculators are found or 4 are tested. Find the probability of: a)the Event E ...
1
vote
2answers
569 views

I can't figure out this combinatorics problem… Or at least why my solution doesn't work.

If the only contents of a container are 10 disks that are each numbered with a different positive integer from 1 through 10, inclusive. If 4 disks are to be selected one after the other, with each ...
1
vote
1answer
147 views

challenging probability question

I got this from a friend. There are $43$ potential essay prompts. Six will show up on the history final, and you will have to choose $3$ to write about. What is the minimum number essay prompts that ...
0
votes
2answers
115 views

Permutation and Combinations

So the example I'm trying to complete is the following: The English alphabet contains 21 consonants and five vowels. How many strings of six lowercase letters of the English alphabet contain: a) ...
0
votes
1answer
370 views

Using the pigeonhole principle to prove there is at least two groups of people whose age sums are the same.

In a room there are 10 people, none of whom are older than 100 (ages are given in whole numbers only) but each of whom is at least 1 year old. Prove that one can always find two groups of people ...
2
votes
3answers
272 views

Algebraic manipulation of binomial theorem

Prove, by algebraic manipulation, that: \[ {{2n} \choose {n}} + {{2n} \choose {n+1}}={1\over2} {{2n+2} \choose {n+1}} \]
0
votes
2answers
676 views

Combinatorics: Number of subsets with cardinality k with 1 element.

Consider the set |n| = {1,2,...,n}. How many subsets does it have of cardinality k and that contain the element 1? I understand that with each element, you can either include it or not to have a ...
2
votes
1answer
103 views

Having a forest and making it into a tree?

Let F be a forest with 100 vertices and 90 edges. How many new edges must be added without adding vertices to obtain a tree? This is what I have so far for this question... I don't think it's this ...
2
votes
2answers
96 views

graph theory /combinatorics committee existence

I'm having trouble figuring out the problem below. I've laid out my approach and it seems combinatorics formulas might help solve this. If anyone can point to me to the right direction i would greatly ...
1
vote
1answer
514 views

Number of distinguishable ways a ten digit number can be arranged?

If there is a ten digit number (like a US 10 digit telephone number) such as 7177425231, how many different ways can the digits be rearranged? I understand how you would go about finding this if you ...
2
votes
1answer
3k views

How many positive integers between 50 and 100 are divisible by 7?

How many positive integers between 50 and 100 a) are divisible by 7? Which integers are these? This question is in the basic counting section of my textbook and I'm just studying for finals now. For ...
1
vote
2answers
208 views

$\sum_{m=0}^n (m-np)^2 {n \choose m} p^m q^{n-m} = npq$

How to show that: $\sum_{m=0}^n (m-np)^2 {n \choose m} p^m q^{n-m} = npq$
17
votes
3answers
502 views

Counting binary sequences with no more than $2$ equal consecutive numbers

I invented the following problem, but I can't solve it. There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers. So for ...
7
votes
2answers
216 views

The pebble sequence

Let we have $n\cdot(n+1)/2$ stones grouped by piles. We can pick up 1 stone from each pile and put them as a new pile. Show that after doing it some times we will get the following piles: $1, 2, ...
3
votes
0answers
102 views

Polyonimo Tiling

I came up with the following conjecture the other day, and was wondering if the result was well-known or even true: Define $f(P)$ for a polyomino $P$ (without holes) to be the least number of total ...
0
votes
2answers
384 views

Figuring how many paths there are to get to a point on a cartesian coordinate system [duplicate]

Possible Duplicate: Counting number of moves on a grid I have an exercise in my Computer Science class, to figure out how many paths there are from $(0,0)$ to $(x,y)$ on a cartesian ...
1
vote
2answers
108 views

combinatoric question

I have a group with the size of n, and only 2 different elements (1 and 0) with k times 1 and m times 0. For example: 1 1 1 0 1 1 1 where n would be 7, k 6 and m 1. I can arrange this group in ...
8
votes
5answers
720 views

Probability that all bins contain strictly more than one ball?

Here's the problem I'm working on: Given that I'm distributing $N$ balls into $K$ bins, what is the probability that all bins contain at least two (strictly more than 1) balls? This seems like a very ...