For 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)

2
votes
1answer
59 views

a collection of 20 marbles from infinite pool of 2 color marbles with replacement.. [on hold]

I have an infinite supply of pink and blue marbles. Probability that any random draw will yield a pink marble is "p" and prob. of picking blue is 1-p. Let us assume p=0.4 if a numeric value helps. ...
1
vote
1answer
67 views

longest way to rearrange students before returning to original arrangement? [on hold]

This is Q24 from the 2012 Intermediate Australian Mathematics Competition: "A teacher has a class of twelve students. She thinks it would be a nice idea if they change desks every day, so she has ...
1
vote
2answers
23 views

Permutation of coefficient with coditions [on hold]

I have 6 coefficients, (V1,V2,H1,H2,D1,D2). Their permutation is 6! = 720. But I have a rule: V2 cannot lead V1, H2 cannot lead H1 and D2 cannot lead D1. For example: V2V1H1H2D1D2 is prohibit. ...
0
votes
0answers
39 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
9
votes
5answers
170 views

How many arrangements of the letters in the word CALIFORNIA have no consecutive letter the same?

First off, the correct answer is $$584,640 = {10!\over 2!2!}- \left[{9! \over 2!}+{9! \over 2!}\right] + 8!$$ which can be found using the inclusion-exclusion principle. My own approach is different ...
1
vote
1answer
63 views

Number of permutations with two elements in one cycle

Show, that for a set of permutations of a set $\{1,\dots,n\}$ $(n>0)$ the following statement is true. statement: The number of permutations where $1$ is in the same cycle with $k$, and the number ...
3
votes
1answer
28 views

Bell numbers and the Moments of expected number of fixed points

Let $X_N$ be the random variable corresponding to the number of fixed points (1-cycles) in a permutation chosen uniformly at random from $S_N$. Then, the $m^{\text{th}}$ moment, when $m < N$, is ...
0
votes
5answers
40 views

What is the probability of obtaining a hand with TWO PAIRS in a standard 5 card game of poker?

What is the intuition behind, 'What is the probability of obtaining a hand with TWO PAIRS in a standard 5 card game of poker?' I know the solution is, $$\frac{\binom{13}{2}\binom{4}{2}\binom{4}{2}...
0
votes
3answers
46 views

What is the probability of getting NO PAIRS in a $13$-card poker game?

What is the probability of getting NO PAIRS in a $13$-card poker game? Here is my attempt: The setup for the required poker hand would be: $$ABCDEFGHIJKLM$$ where $A, B, \ldots, M$ are distinct ...
0
votes
0answers
21 views

Is there a faster way of computing the probability of a sum $S$ when $n$ dice are rolled? [duplicate]

So far, I've only had to deal with $2$ dice or $3$ dice problems. For example, if the problem asks to find the probability that a sum of $8$ will be achieved from rolling $3$ dice, I just list all the ...
0
votes
0answers
21 views
1
vote
2answers
51 views

Scheduling a Round Robin tournament - 4-way games

I'm looking to schedule 16 players to play a round robin tournament with each other such that there are 4 players at each table. I'd like for each player to play with each other player exactly once ...
1
vote
1answer
46 views

Notation for probability: $C_n^r$, $P_n^r$, $A_n^r$?

I was told that $C^{n}_{k}$ refers to combinations or choose k elements from n elements, $\bar{C^{n}_{k}}$ refers to combinations with repetitions (i.e. $C^{n+k-1}_{k}$), and $P^{n}_{k}$ refers to ...
1
vote
1answer
99 views

Let $S$ be a set of $2009$ positive integer numbers.

Let $S$ be a set of $2009$ positive integer numbers. $S$ has the property that for any distinct $a, b, c\in S$ if $gcd(a, b)>1$, then at least $gcd(a, c)$ or $gcd(b, c)$ is also greater than $1$. ...
0
votes
2answers
46 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
0
votes
1answer
761 views

Probability of Obtaining A Particular Sum from Successive Dice Rolls

Suppose you have a regular die with 6 faces numbered 1 through 6, respectively, and roll the die 4 times. What is the probability that the sum of the 4 rolls is 14? This problem is equivalent to ...
1
vote
0answers
30 views

The relation between Weyl character formula and Frobenius characteristic map

Let $\mathfrak{gl}(n)$ be the general linear Lie algebra of rank $n$, and $\mathfrak{S}_d$ be the symmetric group of rank $d$. It is well-known that the Schur-Weyl duality provide a equivalence ...
0
votes
4answers
37 views

Why doesn't this alternative method work? Chance of getting four of a kind in a hand of $5$ cards?

Please note: This is not a duplicate since it is asking about an alternative method of solving the question What is the probability of getting four of a kind in a hand of $5$ cards from a standard ...
5
votes
5answers
88 views

How to find number of solutions of an equation?

Given $n$, how to count the number of solutions to the equation $$x + 2y + 2z = n$$ where $x, y, z, n$ are non-negative integers?
1
vote
1answer
18 views

What's the formula to map between multiindices and indices?

What is the formula to map between multiindices and indices? By multiindex, I mean a variable $I\in\mathbb{N}^d$ where $|I|=\sum\limits_{i=1}^d I_i=n$. Here, $d$ denotes the dimension. Basically, ...
0
votes
2answers
47 views

No of integral solutions to an equation confusion?

For an equation like ${ x }_{ 1 }+{ x }_{ 2 }+{ x }_{ 3 }=60$, I am seeing that in some books they are using $( (60 + 4 - 1) C (4) )$ as solution whereas in some book they are using $( (60 + 4 - 1) C (...
4
votes
3answers
572 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
2
votes
1answer
33 views

Can't understand one chance in R of winning where R is some result of factorials.

In lotto game, let you select six no. from 51 no. on a card and the Lotto managers pick six no. at random. If your choice exactly matches theirs, you win a few dollars. If you have to pick 6 values ...
1
vote
1answer
43 views

Subtle Sample Space

I have been self-studying probability and statistics using Sheldon Ross's "A First Course in Probability" for a while, yet I still have problems on recognizing sample spaces in some probability ...
0
votes
3answers
82 views

How many ways are there to choose 5 ice cream cones if there are 10 flavors?

I had this on a test and I gave answer as: (10 C 5) but it was incorrect. Why? Isn't this just a typical combination problem where you select 5 objects of 10 objects! Correct answer: $_{(10+5−1)}C_{ ...
0
votes
1answer
30 views

Committee selection problem

The problem goes as follows: A committee of $7$ is to be formed from $9$ boys and $4$ girls. In how many ways can this be done when the committee consists of 1. At least $3$ girls? 2. ...
5
votes
1answer
62 views

On “good” numbers and $m \times n$ real matrices

Let $m,n > 1$ be odd integers. Different real numbers are written in the cells of the $m \times n$ table ($m$ rows and $n$ columns). The number is called "good" if 1) It is the largest in its ...
-1
votes
3answers
44 views

Suppose that an ice-cream café has 10 different flavors of ice cream. [on hold]

In how many different ways one can choose 3 scoops of ice-cream, so that order of flavors does not matter?
3
votes
1answer
2k views

hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of $N$ men at a party throws his hat into the center of the room. The hats are first mixed up, ...
4
votes
1answer
93 views

Probabilistic method: vertex disjoint cycles in digraphs

Let us say that a di-graph is $k$-regular if every vertex has precisely $k$ out-edges. The following theorem appears in a book I am currently studying Theorem. Every $k$-regular graph $D$ has a ...
1
vote
3answers
342 views

Three meetings where each attends exactly two

Suppose three meetings of a group of professors were arranged in Mumbai, Delhi and Chennai. Each professor of the group attended exactly two meetings. $21$ professors attended Mumbai meeting, $27$ ...
6
votes
3answers
58 views

In how many ways can an inspector visit $4$ normal sites and $1$ “suspicious” one?

I cannot figure out why my answer to the following question is wrong: Suppose that a weapons inspector must inspect each of five different sites twice, visiting one site per day. The inspector is ...
2
votes
0answers
39 views

The number of partitions of $n$…Subbarao

(Subbarao) The number of partitions of $n$ in which each part appears two, three, or five times equals the number of partitions of $n$ into parts congruent to $2, 3, 6, 9,$ or $10$ modulo $12$. ...
0
votes
3answers
31 views

Find the number of all possible valuations that will satisfy given expression.

This part concerns the 256 possible truth valuations of the following eight propositional letters A, B, C, D, E, F, G, H. For each of the following expressions, say how many of the 256 valuations ...
0
votes
2answers
36 views

How many ways are there to distribute $2$ indistinguishable white and $4$ indistinguishable black balls into $4$ indistinguishable boxes?

How many ways are there to distribute $2$ indistinguishable white and $4$ indistinguishable black balls into $4$ indistinguishable boxes? If the question was asked as "distinct boxes", I can solve. ...
0
votes
2answers
112 views

Round table seating - expected value

There are $p$ women, $s$ men and $p+s$ seats in a round table. Let $X$ be the number of women who sit between two men. Find the expected value of $X$. I know that expected value of $X$ is given by ...
0
votes
2answers
133 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
-1
votes
0answers
214 views
+50

seating at two round tables

We have $n$ people sitting in two round tables like the picture. We randomly change the place of the people we decide two of them and change their places. We can only change the place of the ...
0
votes
1answer
65 views

How do I calculate all possible combinations for a player creator in a game?

I'm currently working on a character creator for a game, but I don't know how to calculate all possible character combinations the player can create. In the creator, the player is required to choose ...
1
vote
1answer
36 views

How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one. There is one where three periphery nodes point to a central node. ...
1
vote
3answers
40 views

Number of ways to partition a set with $2n$ elements

In how many ways can I partition $S = \{1,2,\cdots,2n\}$ into $n$ disjoint $2$ element subsets. Suppose if I subsets of $S$ were $S_{1},S_{2},\cdots,S_{n}$, then I can choose $S_{1}$ in $\binom{2n}{2}$...
1
vote
3answers
65 views

Number of non-negative distinct integer solutions of $x+y+z+w=10$

I understand that there are already many questions relating to this, but my question is regarding some concept of mine that should be working but doesn't produce the right result. So, I follow an ...
2
votes
4answers
332 views

Distributing Objects into Boxes (Discrete Mathematics)

I am trying to solve this question: "How many ways are there to pack eight identical DVDs into five indistinguishable boxes so that each box contains at least one DVD?" I am very lost at trying to ...
0
votes
4answers
74 views

How many $3$ member subsets $\{x, y, z\}$ of positive natural numbers have the sum $x + y + z = 100$?

I have a math homework problem where I think I have to use Permutation/Combination. The question is: How many $3$ member subsets $\{x, y, z\}$ of positive natural numbers have the sum $x + y + z = ...
2
votes
4answers
93 views

Number of positive unordered integral solutions

What are the number of positive unordered integral solutions for $a+b+c=36$ Solution given is $108.$.But I am getting $91$ as $$\frac{\binom{35}2-3\times16-1}{3!}.$$ $3\times16($ for $a=b$ cases and ...
2
votes
1answer
24 views

How many ways can a committee of six be made from 4 students and 8 teachers if the committee contains at least three students?

How many ways can a committee of six be made from 4 students and 8 teachers if the committee contains at least three students? The obvious answer would be to select 3 students and 3 teachers or 4 ...
1
vote
1answer
25 views

Number of monotonic paths in a rectangular grid avoiding certain points

In a rectangular grid of size $m \times n$, the number of paths from $(0,0)$ to $(m,n)$ (without backtracking) is ${m+n \choose {n}} = \frac{(m+n)!}{(m!*n!)}$. Now if there are certain points in the ...