Tagged Questions

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 (5)

20
votes
3answers
601 views

Finding the Robot

There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
0
votes
1answer
48 views

Constructing a particular vertex coloring

My apologies for asking so many questions recently. Let $0\le c<d<e$ be fixed natural numbers and consider any graph on $2e$ vertices, with the vertices labelled as $0,1,\cdots 2e-1$. I want to ...
0
votes
1answer
811 views

How to find the Circular permutation with Repetition [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? Need some guidance with the following problem : There are 'n' different types of objects which needs ...
2
votes
0answers
35 views

How many ways are there to place the ball in N different bags under given condition? [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? I have a doubt in following Combinatorics question : There are N bags, and there several balls of 4 ...
2
votes
1answer
677 views

Solving a series $n(1 + n + n^2 + n^3 + n^4 +…n^{n-1})$

I'm trying to sum the following series? $n(1 + n + n^2 + n^3 + n^4 +.......n^{n-1})$ Do you have any ideas?
3
votes
1answer
317 views

“Sorting” matrix entries by swapping rows and columns

Suppose one has an $n \times n$ matrix whose entries are filled with the numbers $1,2,\ldots,n^2$, but not in that order. Q1: What is the largest number of row or column swaps ever needed to end up ...
1
vote
0answers
58 views

1000 Spanish salads [duplicate]

Possible Duplicate: How to reverse the $n$ choose $k$ formula? Recently saw an ad for a salad bar in Spain offering 1000 different combinations. Now, this could be a salad containing three ...
4
votes
1answer
344 views

Combinatorics: boy-girl pairs

It is the last problem of the AHSME competition 1988-1989 (question 30) "Suppose that $7$ boys and $13$ girls line up in a row. Let $S$ be the number of places in the row where a boy and a girl are ...
1
vote
1answer
172 views

Can you determine a formula for this problem?

Given: A list of integers is there.Now there are 2 buckets -bucket A and bucket B.This step is repeated as long as there are numbers left in the list.Integers from start or end of the list are ...
8
votes
1answer
955 views

In how many ways can we colour $n$ baskets with $r$ colours?

In how many ways can we colour $n$ baskets using up to $r$ colours such that no two consecutive baskets have the same colour and the first and the last baskets also have different colours? For ...
3
votes
1answer
91 views

Stuck in proof of combinatorial identity - Fulton and Harris A.39

I'm trying exercise $A.39$ in Fulton and Harris. They suggest to first prove the formula $$|x_j^{l_i}| \prod_{j=1}^k(1-x_j)^{-1} = \sum |x_j^{m_i}| \hspace{1in} (\ast)$$ where the sum on the right ...
4
votes
2answers
760 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
3
votes
2answers
164 views

Exact number of compositions.

I was wondering if any of you guys could help me with this combinatorial problem. I need to determine the exact number of compositions $(a_1, \ldots,a_k)$ of $n$ which have $k$ parts and satisfy ...
0
votes
1answer
2k views

How to draw a Hasse Diagram

Let $A=\{a,b,c,d,e,f\}$, $R$ is defined by: $\{(a,b), (c,d),(d,c),(d,a),(d,b),(d,f),(e,a),(e,b),(e,c),(e,d),(e,f),(f,a),(f,b)\} \cup \Delta_A$. I am not sure on how to draw a Hasse Diagram for $R$. ...
-2
votes
1answer
403 views

How many ways an examiner can assign 15 marks to 5 questions? [duplicate]

The number of ways in which an examiner can assign 15 marks to 5 questions giving not less than 2 marks to any question is a.1 b.126 c.120 d.240 I am getting no clue!
3
votes
1answer
366 views

Divisibility and Pigeonhole principle

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq ...
1
vote
2answers
155 views

Number of ways to choose shoes so that there will be no complete pair

I am just stuck with a problem and need your help. The question is: A closet has 5 pairs of shoes. The number of ways in which 4 shoes can be chosen from it so that there will be no complete pair is ...
1
vote
2answers
584 views

Generating Series for the set of all compositions which have an even number of parts.

I'm having trouble showing that the generating series for all compositions which have an even number of parts. I'm given that each part congruent to 1 mod 5 is equal ...
4
votes
0answers
203 views

Generating function for product of binomial coefficients

In general, if $a(n)$ is an integer sequence with generating function $A(t)$ and $b(n)$ is an integer sequence with generating function $B(t)$, it is not easy to find the generating function $C(t)$ ...
2
votes
3answers
488 views

Permutations of n beads on a string.

Suppose you have n beads on a string, the beads are labeled 1,2,3,...,n. How many possible permutations are there if you are allowed to flip the string over? E.g. For 4 beads, 1--2--3--4 is ...
1
vote
1answer
146 views

Number of different necklaces using $m$ red and $n$ white pebbles

It's very well known that the number of different necklaces using two colors of pebbles (Two necklaces which can be obtained from one another by rotation are considered the same), is exactly ...
0
votes
1answer
63 views

Probability/Polytope concept

Let $X$ be a real random variable, with real values $X_i$ associated with probabilities $p_i \ge0, p_1 \le 1$, $i=1$ to $n$. The variance $V_p(X)$, is, as usual: $$V_p(X) = \sum^n_{i=1} p_i X_i^2 ...
1
vote
2answers
81 views

how to determine the coefficient to simplify this expression

As I am not good at math, I would like to construct an expression having the form like: $$ a^n (\sum_{i=0}^{n-1} \lambda_i \cdot b^i ) +(\sum_{i=0}^{n-1} \lambda_i \cdot a^i)\cdot b^n + ...
7
votes
4answers
723 views

How do I compute multinomials efficiently?

I'm trying to reproduce Excel's MULTINOMIAL function in C# so $${MULTINOMIAL(a,b,..,n)} = \frac{(a+b +\cdots +n)!}{a!b! \cdots n!}$$ How can I do this without causing an overflow due to the ...
2
votes
2answers
178 views

Simplify $\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$

I am trying to simplify an expression involving summation as follows: $$\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$$ where $n$ is an integer, and $x$ is a positive real number. At a first ...
2
votes
1answer
825 views

Probability of predicting, then throwing, a particular multiset for 5 dice.

My friend shared with me a story that after losing to his SO at Yahtzee, before they put the game away he just randomly predicted he would roll four 5's and a 1. He then got that roll and freaked out. ...
8
votes
3answers
1k views

Combinatorial argument to prove the recurrence relation for number of derangements

Give a combinatorial argument to prove that the number of derangements satisfies the following relation: $$d_n = (n − 1)(d_{n−1} + d_{n−2})$$ for $n \geq 2$. I am able to prove this ...
1
vote
2answers
147 views

Listing all derangements for a given n

How to find all the derangements of [n]. Specifically,if n is 4? What is the process to get all the derangments in general?
31
votes
7answers
15k views

How many triangles

I saw this riddle today, it asks how many triangles are in this picture . I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence. ...
1
vote
2answers
3k views

How many ways you can make change for an amount [duplicate]

I am looking for a formula or at least something to use when trying to compute how many ways I can make change for an amount. Example: there are $3$ ways to give change for $4$ if you have coins ...
3
votes
2answers
197 views

Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 } $$ where $|V_1| - $ number of leaves in a tree, and ...
5
votes
3answers
1k views

Enumerating number of solutions to an equation

How do you find the number of solutions like this? $$x_1 + x_2 + x_3 + x_4 = 32$$ where $0 \le x_i \le 10$. What's the generalized approach for it?
2
votes
1answer
200 views

Counting multidimensional structures (Chomp game states)

The game Chomp is described as follows on Wikipedia: Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks (rectangular cells). The ...
0
votes
1answer
69 views

Generating Series Proof

I'm having a bit of trouble with this proof and was wondering if I could get some assistance. I need to show that: $$ΦS(x) = \frac{1}{\sqrt{1-4x}}$$ All I have is: $$\sum\limits_{k=0}^n {2n\choose ...
1
vote
1answer
130 views

Closed form of binomial sum

I want to find closed form of the following expression. Will you kindly help me? $\binom{e}{0}\binom{n-e}{i}+\binom{e}{2}\binom{n-e}{i-2}+\ldots+\binom{e}{i}\binom{n-e}{0}$ for an even positive ...
4
votes
1answer
96 views

Computing binomial symbols modulo m

While procrastinating, I decided to play around with computing binomial symbols modulo $m$, $$\binom{n}{r} \equiv q \pmod{m}, 0 \leq q < m.$$ Using Pascal's formula, I discovered that this may be ...
2
votes
1answer
481 views

Proof about lucas numbers.

Define the lucas numbers to be $$l_n = l_{n-1} + l_{n-2} $$ if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$ I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by ...
5
votes
1answer
363 views

Counting multidimensional lattice paths

I want to count the number of shortest paths from one corner of a multidimensional lattice, to the opposite corner. Hence in the 2-dimensional case, given a lattice (or grid graph) of $n_1 \times n_2$ ...
2
votes
1answer
335 views

Number combinations multi set

Here is my question: Consider a multiset $\{n\cdot a, n\cdot b, 1,2,3, \ldots, n+1\}$ of size $3n+1$. Determine the number of $n$-combinations. I know from my textbook that if you have a ...
3
votes
4answers
2k views

5 black, 7 red, 9 blue, and 6 white marbles.

I'm having trouble finding how many ways there is to arrange 5 black, 7 red, 9 blue, and 6 white marbles to find the probability that every white marble is adjacent to at least one other white marble. ...
0
votes
4answers
127 views

Calculating this combination: $C_{n}^{l}\cdot C_{l}^{l}+C_{n}^{l+1}\cdot C_{l+1}^{l}+\ldots+C_{n}^{n}\cdot C_{n}^{l}=?$

Calculating this combination: $$C_{n}^{l}\cdot C_{l}^{l}+C_{n}^{l+1}\cdot C_{l+1}^{l}+\ldots+C_{n}^{n}\cdot C_{n}^{l}=?$$
0
votes
1answer
187 views

Write set of Binary Strings as an infinite sum.

I'm new to this generating series stuff and wondering if I could get some assistance. The question goes something like this: Let S be the set of all binary strings with the same number of zeros and ...
1
vote
2answers
86 views

Existence of 5-d centrally symmetric self-dual polytope

Does there exist a 5-dimensional centrally symmetric self-dual polytope?
2
votes
3answers
143 views

What is the number of combinations of the solutions to $a+b+c=7$ in $\mathbb{N}$?

My professor gave me this problem: Find the number of combinations of the integer solutions to the equation $a+b+c=7$ using combinatorics. Thank you. UPDATE Positive solutions
1
vote
2answers
53 views

Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario. If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client ...
2
votes
3answers
63 views

Why are there 5 groups that contain the 2 enemies?

Suppose I must form a committee of 3 people chosen out of 7. 2 of the 7 are enemies of each other. These 2 people would wreak havoc if they are both chosen to be on the committee. How may ways are ...
1
vote
2answers
111 views

Proof for one of the Lucas problem

Can anybody provide a combinatorial proof or algebraic proof of following identity? $${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = ...
2
votes
2answers
230 views

Number of solutions of $x_1+x_2+x_3+x_4=1000$

How many solutions possible for the equation $x_1+x_2+x_3+x_4=1000$ if all $x_1,x_2,x_3,x_4$ are non-negative integer and $\left| {{x_i} - {x_j}} \right| \in \left\{ {0,1} \right\}\text{ }\forall 1 ...
10
votes
3answers
1k views

In the card game Set, what's the probability of a Set existing in n cards?

Given $n$ randomly drawn Set cards on a table from a standard 81-card deck, how can I determine the probability of one or more Sets existing on the table? First, for those who may not be familiar ...
1
vote
1answer
93 views

Gambler with infinite bankroll reaching his target

Suppose a gambler with infinite bankroll has a target of winning 10 dollars. He wins/loses $\$1$ with probabilities $0.48=p$ and $0.52=q$ respectively. What is the probability that he meets the ...