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. Combinatorics is a ...

learn more… | top users | synonyms (4)

3
votes
2answers
351 views

Combinatoric Solution To The Birthday Paradox

I attempted the following solution to the birthday "paradox" problem. It is not correct, but I'd like to know where I went wrong. Where $P(N)$ is the probability of any two people in a group of $N$ ...
1
vote
0answers
37 views

Generating function from a set of binary strings

So this question is in my textbook and there's no solution, so I'm seeing if I can get a confirmation? Q: Let $S$ be the set of all binary strings of length 4, where for each string $a\in S$, the ...
1
vote
2answers
39 views

Double Factorial

I am having trouble proving/understanding this question. Let $n=2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a partition of $X$ into $k$ sets of size $2$. Show that the ...
1
vote
3answers
40 views

Generating series of integers with a specified sum

If I say that 6 positive integers were added together to get a total of 200. let count = 6 let sum = 200 I have 2 questions First of all, is there a formula for generating a list of all the possible ...
2
votes
1answer
24 views

Different combinations of objects with restrictions

first of all please excuse the title, hopefully the question will make it more clear. Suppose that there are 17 students in a class. For assignment 1, the students are to partition themselves into 4 ...
1
vote
1answer
14 views

Combinatorics Number of Possible Assignment Combinations

Say I have Group A and Group B Group A needs 1 student and group B needs 2 students. There are 3 students total (A,B,C). What sort of formula could I use to determine the total number of assignment ...
1
vote
2answers
51 views

combinatorics dice question

There are $10$ identical dice ($1$ - $6$). How many different results can we get so that the set of results will be exactly $3$. for example: $7$ dice will be the number $2$, $2$ dice will be $3$ and ...
0
votes
1answer
23 views

permutation on relations

Let $A = \{1, 2, 3, 4\}$. Call a binary relation on $A$ interesting if it is symmetric or it does not contain the pair $(1, 4)$. How to calculate the number of interesting binary relations on $A$. My ...
3
votes
1answer
37 views

Bringing a permutation back to the identity

I'm working with transposition distance (nothing to do with algebraic transpositions) on given permutations. Given a permutation, how many moves (transpositions) will it take to get back to the ...
1
vote
2answers
66 views

A problem about pigeonhole principle or graph.

Let $A=\{1,2,...,n\}$, where $\binom{n}{3}\geq n+1$. Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $A$ such that $\bigcup_{i=1}^{n+1}A_i=A$ and $n(A_i)=3$ for all $i$. How to prove or disprove that ...
2
votes
1answer
38 views

Counting problem: multiple scenarios for distributing balls into boxes (more boxes than balls)

I am having a bit of trouble understanding which combinatorial methods to use for this problem. I've actually resorted to listing some of these scenarios out (brute force) to get my solution. I would ...
3
votes
1answer
48 views

How many points are needed to intersect all elements in a sequence of measurable sets

Suppose $(X,\mathcal B, \mu)$ is a probability space and $n\in\mathbb N$ is an arbitrary but fixed integer. Is it true that if $m\in\mathbb N$ and if $A_1,\ldots,A_m\in\mathcal B$ with ...
0
votes
1answer
30 views

With $m>n$ , In how many ways $m$ men and $n$ women can seat in row for a photograph so that no two women are adjacent? [duplicate]

Given $m>n$ , In how many ways $ m$ men and $n$ women can seat in row for a photograph so that no two women are adjacent? My effort : There are $m-1$ gaps if $m$ men are seated. Now we have to ...
2
votes
2answers
48 views

How many ways are there of coloring $n$ numbers (using $k$ colors) s.t. each color is used at most $d$ times?

Let's assume we have $n$ numbered items and $k$ colors. We color each of the items with a single color. How many such colorings exist such that each of the colors is used at most $d$ times?
1
vote
0answers
41 views

Counting problems that still remains unsolved?

I just proved that the cartesian product of $\mathbb{Q}$ and $\mathbb{N}$ is countable and I started to wonder if there exists any sets that is still not yet proven to be countable/uncountable? Also, ...
1
vote
1answer
29 views

Combinations with Repetition

I am looking the basics of combinations with repetition. The other name is Stars and Bars problem. On MIT OCW I found this: An ice-cream store specializes in super-sized deserts. They offer a ...
0
votes
1answer
45 views

proof of the negative binomial series using induction?

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$ I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the ...
0
votes
1answer
25 views

Solving a summation where the inner summation is limited by the iterator of the two outer summations

I'm trying to solve the following summation (where C is some constant) but I'm stuck because of the inner most summation which is limited by $i\sqrt[2]{j}$ where i and j are the iterators of the outer ...
0
votes
0answers
30 views

the number of ways a planar graph can be partitioned

i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned ...
3
votes
1answer
22 views

Exponents with Combinatorics

How many of the first $242$ positive integers are expressible as a sum of three or fewer members of the set $\{3^0,3^1,3^2,3^3,3^4\}$ if we are allowed to use the same power more than once. For ...
2
votes
3answers
83 views

Combinatorics Problem w/ money (exact purchase with XXX coins)

Mr. Long Johns has 2 pennies, 3 nickels, 2 dimes, 3 quarters, and 8 dollar coins. For how many different amounts can John make an exact purchase? (no change required) A penny is 1 cent A nickel is 5 ...
2
votes
3answers
76 views

The number of positive integers less than 1000 with an odd number of divisors

How many positive integers less than 1000 have an odd number of positive integer divisors? Well I know that the number has to be composite because a prime number has 2 divisors, which are 1 and ...
4
votes
2answers
41 views

What is the number $p(n)$ of partitions of an abundant number $n$ into distinct, proper divisors of $n$?

For lack of a better symbol, $p_{\sigma\tau}(n)$ (feel free to suggest something better). For example, $p_{\sigma\tau}(12) \geq 2$ since $12 = 1 + 2 + 3 + 6 = 2 + 4 + 6$. Of course if $n$ is ...
0
votes
1answer
31 views

Rank notion of a matrix

$\newcommand{\rank}{\operatorname{rank}}$Divide $p-1$ ($p=q^k>2$ with $k>1$, $q$ prime) elements in $\Bbb F_p^\times$ into equal disjoint subsets $S_+,S_-$. Given square $0-1$ matrix $A$, ...
1
vote
1answer
39 views

Generating Functions for Two Variables

Find the generating function for the number of words, from the standard 26-letter alphabet, that have $k$ letter with exactly 1 A and at least 2 Bs. ($k$ will vary) Workings: For the time being I'm ...
1
vote
2answers
143 views

Assigning tables for Speed Networking session

I'm planning a structured Speed Networking activity for an event. Here are the details: 100 attendees participating Split into groups of 4 12 rotations 25 tables One person at each table never ...
2
votes
1answer
22 views

Finding external angles for Misiurewicz points in the Mandelbrot set

In the Mandelbrot set for the quadratic polynomial $z \to z^2 + c$, rational external angles with even denominator are pre-periodic and have corresponding external rays which land at Misiurewicz ...
1
vote
1answer
34 views

Nth pemutation of Lexicographic String

Can someone please explain the logic behind the mathematical equation, that for finding the Nth Lexicographic rank of a string the Leading Entry is $a_q$ if $k=q\cdot (n!)+r.$ The link to the problem ...
1
vote
1answer
48 views

Roots of permutations [closed]

If $(10 1 7 12)(3 2 4 5 6)(11 8)(13 9) = k$ where $k∈S13$ so that $p^3=k$ and $p∈S13$, decide whether $p$ exists or not. If it doesn't, prove it. I have no idea how to start and even do this type of ...
-1
votes
1answer
35 views

Probability of sum of dice rolls combinatorics [closed]

The question is as follows. A cyclist is going for a bike journey of 1950 kilometres. Every morning he tosses a die, and if the outcome is k, where k = 1, 2, . . . , 6, he cycles 10k kilometres on ...
1
vote
0answers
17 views

Definition of minimal presentation of a group

I'm working on a problem on the braid monodromy of complex lines arrangements in $\mathbb{C}^{2}.$ I have the following question. It's just a simple definition. However, I didn't find anywhere. Let ...
1
vote
4answers
48 views

How many ways letter can be placed in the box?

There are 6 letters and 6 boxes numbered 1 to 6 , letters are to placed in the box such that letter having number 1 should not be placed in box having number 1 and so on. Letter 1 is fixly placed in ...
0
votes
1answer
35 views

Linear Permutations of $n$ objects

Suppose there are $n$ distinct objects $O_{1},O_{2},O_{3},\ldots,O_{n-1},O_{n}$. We have to find out the number of ways we can arrange them. But, there is a catch. We have to arrange them such that ...
0
votes
2answers
24 views

Number of ways to distribute 4 objects in 6 drawers with some restrictions

The question is: We have 4 different objects, and 6 drawers on top of another. So the question in how many ways can we distribute the objects to the drawers so that the top drawer will have exactly ...
5
votes
2answers
79 views

A combinatorial identity.

Let $n \in \mathbb N$ and $X_1,\ldots,X_n$ be subsets of $\{1,\ldots,n\}$ such that there is some $p$ such that $\forall i\in \{1,\ldots,n\}, |X_i|=p$. Suppose as well that there is some $q$ ...
1
vote
2answers
44 views

Number of circular permutation of word 'CIRCULAR' [closed]

Hey please help me with this question... Find the number of circular permutation of the word 'CIRCULAR'. Number of circular permutaion is (n-1)!
2
votes
2answers
46 views

Letters of the word “PARAMETER” [closed]

I have one question that bothers me. The total number of words that can be made by writing the letters of the word PARAMETER so that no vowel is between two consonants. The answer is 1800. I couldn't ...
1
vote
1answer
37 views

Proof By Induction Using Binomial Coefficients

I'm having a really hard time with this proof by induction: Prove this formula by induction: $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$. Easy enough, right? Wrong. I have to do it using ...
0
votes
2answers
25 views

Possible number of throws in nonagonal dice (ie. two nine-sided dice) [closed]

I have two nine-sided die. Or, in other words, a single pair of nonagonal dice. I was hoping someone could help me with two questions…. How many combinations can be possibly thrown (in a single ...
1
vote
1answer
23 views

Finding the coefficient of a power series

How would I find the coefficient of: $[x^{10}]x^6(1-2x)^{-5}$ I know that I can simplify this as follows: $[x^4](1-2x)^{-5}$ and that generally the following formula would be used to solve this: ...
0
votes
1answer
21 views

The Probability of 4 heads given the first toss is a head

The Question Alice tosses a fair coin seven times. Find the probability that she tosses 4 heads given her first toss is a head. Then, find the probability that she tosses 4 heads given her first and ...
4
votes
6answers
2k views

A die is rolled 3 times. What is the probability that a five is rolled at least twice?

The probability of not getting a five is $(\frac56)^3$, and I figure the probability of getting at least one 5 is $1-(\frac56)^3$, but I don't know how to figure out if it is rolled at least twice. ...
0
votes
0answers
35 views

On rank $r$ $0$-$1$ matrices

Is it possible to transform a rank $r$, $0$-$1$ matrix of size $n \times n$ into a $0$-$1$ matrix of size $n \times n$ with almost every entry $0$ except a $0-1$ submatrix of size $r \times r$ having ...
1
vote
1answer
39 views

Simple Combinatorics - drawing aces from a deck of cards

Suppose you have a deck of cards which contains 52 cards with 4 different sets which consist of 13 cards each. We write a series of $n$ cards like this: We draw a card, write it as the next cards in ...
0
votes
2answers
39 views

Probability using combinatorics problem

The problem is simple: "Find the probability of getting no aces with four dice". Now, i'm supposed to solve this using combinatorics. So, I see two ways of doing this. First: considering my sample ...
0
votes
1answer
74 views

Generating Functions of Partitions?

Show that $2(1-x)^{-3} [(1-x)^{-3} + (1+x)^{-3}]$ is the generating function for the number of ways to toss $r$ identical dice and obtain an even sum. Workings: I'm not too sure on this problem. ...
0
votes
0answers
11 views

Optimal solution for maximizing product of combination under product constraint

Suppose we have to choose $mm_1$ items out of $m_1$ and $mm_2$ items out of $m_2$ such that $mm_1 * mm_2 = k$ where $k$ is fixed and known. This also constrains us such that $mm_1 < m_1$ and $mm_2 ...
1
vote
2answers
165 views

How many ways to reorder a string's letters

If we have to have exactly 7 letters out of which two are "M"s, Two are "X"s and Three are "E"s, without having any consecutive "E"s. I arrived to the number 10*C(4,2) by just brute forcing the ...
1
vote
0answers
12 views

Counting distinct positive valued k-tuples that sum to n where each entry can be no greater than some value.

This is motivated by the desire to count the number of ways two dice can form the sums 2,3,4,...,12 respectively. We can safely use the stars and bars method for 2,3,4,...,7 where the number of ways ...
1
vote
0answers
41 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities (part 2)

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $A=A(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \geq A n^{-1/2}2^{n ...