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)

1
vote
2answers
494 views

Chromatic Polynomial

I am asked the following: Let n be a positive integer at least 3. The wheel W_n is the graph obtained by taking the cycle C_n, placing an additional vertex at the center, and joining it to ...
3
votes
2answers
277 views

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node ...
1
vote
3answers
265 views

How many permutations $\tau$ on 8 elements are there such that $\tau\circ\tau$ is the identity permutation?

How many permutations $\tau$ on 8 elements are there such that $\tau\circ\tau$ is the identity permutation? *Details and assumptions You may think of a permutation on 8 elements as a way to shuffle ...
3
votes
1answer
188 views

Three dice having sides labelled 0,1,e,π,i,√2 are rolled. Find the probability of getting the product of the three results a real number.

Three fair 6-sided dice each have their sides labeled $0\,,\,1\,,\,e\,,\,\pi\,,\,i\,,\,\sqrt 2\,$. If these dice are rolled, the probability that the product of all the numbers is real can be ...
2
votes
3answers
467 views

modified-paths-counting-in-a-rectangle

I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is: We are given K Rectangles. The dimensions ...
4
votes
1answer
276 views

Combinatorics: $N$ balls of $R$ different colors into $R$ bins

Another balls and bins problem, but I couldn't find one like this after browsing a while. Say I have $N$ balls of $R$ different colors (N/R balls of each color) and I need to put them into $R$ ...
2
votes
1answer
63 views

Finding Two probabilities are independent or not…

A bag contains 30 balls 20 red and 10 blue. Two balls are drawn from the bag. Let A be the event that the first ball is red, and B be the event that the second ball is red. Are A and B independent? I ...
2
votes
2answers
95 views

Stanley's Enumerative Combinatorics help

On page 63 of Volume 1 of Stanley’s Enumerative Combinatorics there is a statement, Clearly $w$ is uniquely determined by $w'$ and $w''$, and $\operatorname{inv}(w) = \operatorname{inv}(w') + ...
2
votes
1answer
176 views

The probability of exactly k successes in n independent Bernoulli trials

A coin is biased so that the probability of heads is $2/3$. What is the probability that exactly four heads come up when the coin is flipped seven times, assuming that the flips are independent? I am ...
5
votes
1answer
88 views

$S_n$ has only four (irred.) representations with degree $<n$ (for $n>6$)

I'm working on the following exercise: For $n\ge 7$, $S_n$ has no irreducible representations of dimension $m$ with $2\le m\le n-2$. There is a solution here but I'd like to follow the ...
6
votes
1answer
191 views

How many unique shapes can be created from a wiggly snake of $k$ links?

In one of her videos (at 0:46) Vihart muses about this problem. Given a wiggly plastic snake with $k$ links, how many valid and unique shapes can be created out of the snake. A shape is valid if it ...
0
votes
1answer
116 views

Another version of PP

Prove the following version of the pigeonhole principle. Let $m$ and $n$ be positive integers. If $m$ objects are distributed in some way among $n$ containers, then at least one container must hold at ...
2
votes
1answer
318 views

Combinatorics/Multisets problem question

I wonder how a problem of the following type can be solved. I have looked for a solution but I am not to identify the kind of problem I am facing. I would like to know if there is a close formula or ...
2
votes
1answer
92 views

Calculating $\binom{n}{r} \bmod\; p$ where $p$ is prime and as large as $1000000007$

I am trying to calculate $\binom{n}{r}$ modulo $1000000007$. I have read here about Lucas' Theorem but it seems to work for small values of $p$. Here $p = 1000000007$. Is there a way this can be ...
4
votes
2answers
115 views

Analog of Beta-function

What is the multi-dimensional analogue of the Beta-function called? The Beta-function being $$B(x,y) = \int_0^1 t^x (1-t)^y dt$$ I have a function $$F(x_1, x_2,\ldots, x_n) = ...
1
vote
1answer
243 views

Counting Number of Walks on a non-rectangular Grid

Here is the problem, I have a grid like below, now i am at the top-left point, and i want to goto bottom right corner point. from a point i can only go to bottom row, or right column, i cannot ...
3
votes
3answers
1k views

How many arrangements of the word marmalade can be made with the vowels in the original order

How many arrangements of the word MARMALADE can be made with the vowels in the original order? What is the procedure for doing this problem? Is there more than one way of approaching it?
0
votes
2answers
369 views

Finding number of cases , arranging people around circular table

Suppose we have a circular table and it contains 10 seats how many way we can arrange 15 people in this table ? Please Correct me: $ \dbinom {15}{10} \cdot \dfrac {15!}{5!} $
0
votes
2answers
3k views

Yahtzee game, probability of getting full house,4 of a kind

In the game of Yahtzee, five dice are tossed simultaneously. Find the probability of getting a. full house b. 4 of a kind Bases on wikipedia Full House = A three-of-a-kind and a pair ...
7
votes
1answer
118 views

Probability of duplicate free sample of iid discrete random sample

Let $\{X_1,\ldots,X_n\}$ be independent identically distributed discrete random variables. I am interested in computing the probability of the event that the sample is duplicate free: $$ ...
1
vote
2answers
73 views

Finding Number Of Cases,Simple Counting Question

How many positive integers less than 1000 have at least one decimal digit equal to 9? Please correct me: Answer = (1) + {(1*10) + (9*1)}+ {(1*10*10) + (9*10*1) + (9*1*10)} ==> 9 + 9x + x9 + 9xx + ...
0
votes
1answer
61 views

probability question - Please Correct me

Thirteen people on a softball team show up for a game. Of the 13 people who show up three are women.How many ways are there to choose 10 players to take the field if at least two of these players must ...
1
vote
0answers
79 views

How to characterize the partial order on the k-combinations of a totally ordered set?

Consider a finite set $X = \{x_1,\ldots,x_n\}$ whose elements are totally ordered. In fact, for concreteness, assume that $X$ is a set of reals, and without loss of generality assume that $x_i$ is ...
3
votes
1answer
1k views

Putnam 2012 B3 - Tournament combinatorics

A round-robin tournament among $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ ...
0
votes
1answer
35 views

Reducing the expression to more simplified expression

Can the following expression be reduced to some more simplified expression? $\sum_{j=0}^{k} \binom{n-a + m-j}{n-a} \times \binom{a-1 + j}{a-1}$ n,m and a are some positive constants with a < ...
5
votes
1answer
208 views

How can I apply a Inclusion–exclusion principle in this task?

Simple task from combinatorics: How much sequences does exist, that consist of letters A, B, C, D, ..., O, P; if no sequence could have any of these words: PONK, DOBA, COP. This task is about ...
1
vote
1answer
461 views

Combinatorics in card games

With a regular set of playing cards (52, 4 of each number). Out of x draws, how can I find the number of draw combinations in which two or more cards have the same number.
4
votes
3answers
189 views

p(n) is count of all n-digit numbers…

Let $n$ be an arbitrary positive integer, and $p(n)$ be the number of $n$-digit numbers which consist only of the digits $1,2,3,4,5$, and in which each two neighbour digits differ by $2$ or more. My ...
4
votes
3answers
128 views

Let $X=\{1,2,3,\ldots,10\}$ Find the number of pairs $\{A,B\}$

Let $X=\{1,2,3,\ldots,10\}$. Find the number of pairs $\{A,B\}$ Such that $A,B\subseteq X$, $A\neq B$ and $A \cap B=\{5,7,8\}$. Not a homework question. It is a question from a Math olympiad.
1
vote
1answer
252 views

How many graphs with vertex degrees (1, 1, 1, 1, 2, 4, 5, 6, 6) are there?

How many graphs with vertex degrees (1, 1, 1, 1, 2, 4, 5, 6, 6) are there? Assuming that all vertices and edges are labelled. I know there's a long way to do it by drawing all of them and count. Is ...
11
votes
2answers
385 views

Sunflower combinatorics

$\newcommand{\ms}{\mathscr}$Please give me only a small hint, or give me an easier problem to solve that would help me do this. A sunflower is a family of sets (petals) for which ever pairwise ...
2
votes
1answer
77 views

Evaluate a certain derivative

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $\{l_1,\dots,l_n\}$ a vector of natural numbers such that $l_1+l_2+\dots+l_n=N$. Let $$ h_j(x)=\prod_{i\neq j,i=1,\dots, n} ...
4
votes
2answers
751 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
4
votes
0answers
202 views

There are $n$ horses. At a time only $k$ horse can run in the single race. How many minimum races are required to find the top $m$ fastest horses?

There are $n$ horses. At a time only $k$ horses can run in the single race. How many minimum races are required to find the top $m$ fastest horses? Please explain your answer. PS: There is no timer.
9
votes
1answer
1k views

Losing at Spider Solitaire

Spider Solitaire has the property that sometimes none of the cards in the final deal can "go" and so you lose, regardless of how much progress you have made beforehand. You would have known that you ...
1
vote
3answers
318 views

Probability we get a king on the nth card draw when drawing from a pack of 52

I'm looking for the probability that we first get a king on the nth card draw when drawing from a pack of 52 cards. Here's what I have done - Let $A_i$ be the event that we don't get a king on card ...
1
vote
2answers
3k views

Drawing two cards from 52, what is the probability that the second card has a higher face value than the first?

So if I draw two cards from 52, what is the probability that the second card has a higher face value than the first? The values of the cards are Ace = 1, Two = 2,..., King = 13. I got as far as ...
2
votes
2answers
64 views

Non-isomorphic combinatorial classes with growth rate equal to the golden ratio?

In a couple of weeks, I'm giving a talk about the growth rates of some combinatorial classes. In the introduction, I thought I'd present the class of tilings of a $n\!\times\!2$ strip with dominos, ...
1
vote
1answer
160 views

Question on inclusion-exclusion principle when $n=2$

Using the inclusion exclusion principle - http://www.proofwiki.org/wiki/Inclusion-Exclusion_Principle - if I set $n=2$ I get the following - $$P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2) + ...
2
votes
4answers
308 views

Coloring a Hexagon

Consider the following hexagon with the shown vertices connected: We now add additional connections: i) e is connected to b ii) c is connected to d ii) a is connected to f How many ways can we ...
0
votes
0answers
308 views

Solving a recurrence relation with generating functions

I'm having trouble midway with solving this recurrence relation using generating functions: $a_{k+2} - a_{k + 1} + 2a_k = 4^x$, with initial conditions $a_0=2, a_1=1$. I'm not sure if this is ...
9
votes
4answers
239 views

An upper bound for $\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$?

Does anyone know of a reasonable upper bound for the following: $$\sum_{i = 1}^m \frac{\binom{i}{k}}{2^i},$$ where we $k$ and $m$ are fixed positive integers, and we assume that $\binom{i}{k} = 0$ ...
0
votes
1answer
144 views

Prove that $p\mid \binom{p}{k},\ 0< k< p$

Prove that: $$p \,\,\left|\, {p \choose k} \right., \quad 0< k \lt p$$ if $p$ is prime. how to prove that with direct proof?
1
vote
1answer
2k views

Combinatorics question about english letters (with consonants and vowels)

The english alphabet contains $21$ consonants and $5$ vowels. How many strings of $6$ lowercase letters of the English alphabet contain a) exactly 1 vowel b) exactly 2 vowels c) at least one vowel ...
3
votes
5answers
257 views

Why do you need to specify that a coin is fair?

This sounds like the kind of etherial question that generally gets dropped from stack exchange sites, but I don't know of a better venue to ask so I'm hoping this question will help other folks with a ...
0
votes
3answers
170 views

Probability of selecting a combination of two variables.

I have a bag of toys. 10% of the toys are balls. 10% of the toys are blue. If I draw one toy at random, what're the odds I'll draw a blue ball?
1
vote
1answer
187 views

Determining if it is a permutation or a combination for this question

I am having some issues determining if it is a permutation or a combination for the following question. Some help would be really appreciated. A county park system rates its 20 golf courses in ...
3
votes
3answers
489 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 ...
0
votes
1answer
51 views

definition of $l$-equivalence

In the following paper http://www.math.ucsd.edu/~ronspubs/74_01_van_der_waerden.pdf, just in the first paragraph the author defines what $l$-equivalence for two m-tuples $\in [0,l]^m$ means. Can ...
1
vote
1answer
869 views

Combinatorics: how many ways are there to form 100 with 1, 2 and 5 [duplicate]

Possible Duplicate: Making Change for a Dollar (and other number partitioning problems) dollar notes in denominations of 1, 2 and 5. How many ways are there to form exactly $100 using just ...