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)

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$, ...
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
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 ...
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$ ...
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 ...
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
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 ...
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
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 ...
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
137 views

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^{m}x_i=10$ [closed]

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^m x_i=10$ A. $89$, B. $91$, C. $92$, D. $120.$
7
votes
2answers
3k views

How can I assign weights to coins so that they can be counted in a single weighing?

I was sorting out the coins in my loose-change jar the other day, and the following thought crossed my head: Is it possible to deduce the number of each type of coin in this pile by simply weighing ...
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)!
-4
votes
0answers
40 views

Sequence and Divisibility

Consider a sequence $a_1$, $a_2$, ..., $a_9$, $a_{10}$, with $a_1=a_{10}$, such that for $i \neq j$, $a_ia_j$ is divisible by $n$ if and only if $|i-j| \neq 1$. What is the minimum value of $n$?
2
votes
3answers
685 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
1
vote
1answer
38 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 ...
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
25 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
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 ...
0
votes
2answers
40 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
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 ...
0
votes
1answer
98 views

Minimum number of knights so that every cell is attacked

Given a chess board of dimensions $7\times 7$ what is the minimal number of knights needed to be placed on the board so that every cell is attacked by at least one knight. I have no idea on this one.I ...
1
vote
1answer
40 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
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 ...
2
votes
0answers
40 views

Counting rings of order $p^3$

MathWorld states that there are exactly 52 rings of order 8 (multiplication in rings may be not commutative and perhaps there will be no neutral element) and 53 rings of order $p^3$ where $p$ is an ...
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 ...
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 ...
2
votes
5answers
64 views

Finding the combination

I have this formula: $$\frac{(N-K)(N-K-1)\cdots(N-K-n+1)}{N(N-1)\cdots(N-n+1)}$$ and my book says it can be written like this: $$ \frac{\binom {N-n}K}{\binom N K} $$ The problem is i cannot ...
2
votes
0answers
25 views

Largest chunk in a partition

Let $S$ be the set of all ways of splitting a sequence of $m$ elements into $k$ non-empty chunks. (Of course, $|S| = \binom{m-1}{k-1}$.) Say $m=2k$, for instance. What would be an $L$ such that only a ...
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 ...
10
votes
2answers
206 views

Gardner riddle on mathemagicians

A cute riddle (but maybe not so easy!) from Gardner: At a gathering of mathemagicians, the Grand Master and his 8 disciples are seated at a round table. The Grand Master will judge each of his ...
13
votes
2answers
230 views

When $\frac{C(n, k)}{n^{k-1}} > 1$?

I came across this while considering the subset sum problem in relation to another problem. Define the ratio, $$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$ and the integer ...
3
votes
2answers
28 views

simple combinatorics question about object division

In how many ways you can solve the equation $X_1+X_2+ \cdots +X_{15} = 300$ ($X_1,X_2, \ldots, X_{15}$ are natural numbers) so that : a) for every $1 \leq i \leq 15$, $X_i \leq 19$ b) for every $1 ...
0
votes
1answer
48 views

Prove that $nCr = n(n-1)(n-2)\cdots(n-r+1)/ 1\cdot2\cdot3 \cdots r$ is an integer for all positive integral $n$ and for all integers $r \geq 0$.

Prove that $nCr =\frac{ n(n-1)(n-2)\cdots(n-r+1)}{ 1\cdot2\cdot3 \cdots r}$, is an integer for all positive integral values of $n$ and for all integers $r \geq 0$. Can someone please explain it to ...
0
votes
1answer
20 views

Combinatorics deck of card question

In a deck of cards there are $4$ sets, each set has $13$ cards. you choose a series of n cards like this : you choose a card, you write it as the next in the series, you put it back in and you ...
0
votes
0answers
6 views

Volume of bounded regions in a hyperplane arrangement

I am given a hyperplane arrangement $\mathcal{H}_0$ in $\mathbb{R}^n$ and a function $\phi \colon \mathbb{R}^n \to \mathbb{Q}.$ I choose any enumeration on the set of primitive vectors (i.e. vectors ...
2
votes
1answer
49 views

Strings from an alphabet of $k$ symbols with no consecutive repeated symbols?

Let $\Sigma = \{1,\cdots,k\}$ be an alphabet with $k$ characters. Consider the set of all strings such that no consecutive entries are the same character. Let $F(n_1,\cdots,n_k)$ count the number of ...
7
votes
1answer
162 views

$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large) There are $N$ perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the ...
5
votes
0answers
82 views

number at the circumference

Determine all natural numbers $n$ such that the numbers $1,2,3, . . . ,n$ can be placed on the circumference of a circle, such that for any natural number $s$ with $1 \le s \le \frac{n(n+1)}{2}$ there ...
2
votes
1answer
58 views

Biggest number of creatures in forest

In crazy forest there are 6 werewolf's,17 unicorns and 55 spiders. Werewolf can eat unicorn and spider,but can't eat another werewolf. Spider can eat unicorn,but can't eat werewolf or another spider ...
0
votes
1answer
37 views

Number of words of length n which contain the sequence (aa) at least once

Let $A = {a,b,c}$ be the alphabet to use for the words. Number words of length n which contain the sequence $(aa)$ at least once. $n = 0$ and $n = 1$ yield no words, because they do not contain ...
1
vote
0answers
25 views

In how many ways can I move $M$ steps such that I do not leave the $N$-dimensional space at any point?

Suppose that currently I am at some position $(p_1,p_2,p_3 \dots p_N)$ in an $N$-dimensional space. The dimensions of the space is $(d_1,d_2, \dots d_N)$. In a step, I can walk one step ahead or ...
2
votes
1answer
260 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
0
votes
1answer
23 views

How many sets of 2 without duplicates out of these options?

So there are twelve signs of the zodiac: Aries, Taurus, Gemini, Cancer, Leo, Virgo, Libra, Scorpio, Sagittarius, Capricorn, Aquarius and Pisces I want to know how many possible sets of 2 I can make ...
1
vote
0answers
16 views

Simple clarification on probability of events

I am rather new to probability and its concepts and would appreciate a clarification for the following very simple problem, mainly for understanding purposes: If we had to form a word of 4 letters ...
4
votes
1answer
436 views

Permutations of a set with a conditional subset

Using the digits 1, 2, 3, 5, 6, 8, 0 only once, how many 4-digit numbers could be constructed if the number is even? This is an exercise from an online course I'm taking. The given solution suggests ...
1
vote
1answer
58 views

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side? My approach: Since each side of the table seats two people, there are ...
1
vote
0answers
42 views

Limit of $\frac{1}{n}\log({n\choose np})$ without using Stirling's formula

I am trying to evaluate the following limit: $$ \forall p\in(0,1) ,\lim_{n\rightarrow \infty} \frac{1}{n}\log{n\choose \lfloor np \rfloor} =H(p),$$ where $\lfloor x\rfloor$ means the greatest integer ...
1
vote
1answer
14 views

Experiments with random selection: when to respect order?

I have a hard time imagining experiments of this nature without noting the arrangements (I draw that ball with my left hand, the other with my right. I draw that ball first, the other second) so I'm ...