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)

2
votes
3answers
88 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
78 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
46 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
33 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
40 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 ...
0
votes
2answers
150 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
23 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
36 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
49 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
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
49 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
36 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
26 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
81 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
49 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
47 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
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 ...
0
votes
2answers
26 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
27 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
22 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
36 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
41 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
42 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
78 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
167 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 ...
0
votes
1answer
49 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 ...
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 ...
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
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 ...
2
votes
0answers
26 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 ...
2
votes
0answers
40 views

Zeilbergers algorithm in Maple

I try to prove several hard combinatorial identities. One of them is following \begin{align*} \sum_{s=0}^{\min\{k,n-1\}} \sum_{i=0}^{k-s} (-1)^{i} {2n+k-i-1 \choose k-s-i} {i-n \choose s} {n+i-1 ...
6
votes
1answer
58 views

Number of ways to pick N numbers from 0,1,…,N-1, with possible duplication, with sum equal 0 mod N

We have the numbers $0,1,2,....,N-1$ in $\mathbb Z_N.$ I want to pick $N$ numbers from these. These are the rules: Duplication may occur We don't care about ordering, $00041$ is equivalent to ...
0
votes
1answer
39 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
27 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 ...
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
26 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 ...
1
vote
1answer
61 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
44 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 ...
2
votes
2answers
42 views

Counting problem - I seem to be counting double

If we have a group of $10$ men, and $4$ women, and we want to separate these $14$ people to $2$ groups of $7$ such that each group has at least $1$ women, in how many different ways can we achieve ...
4
votes
2answers
96 views

How many new subsets may be created?

I've got a following problem. We have got 10 subsets of X. How many new ( max. number ) subsets may be created using 4 operations : union, intersection, complement, symetric difference? The first ...
3
votes
1answer
41 views

$\sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i} =\binom{m+n}{k}$ [duplicate]

I'm trying to show that the equality $$\sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i} =\binom{m+n}{k}$$ Is true. I know it is since there is a good combinatorical argument for it. If we have a group of ...
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 ...
3
votes
1answer
65 views

Simple Combinations Binomial

There is a little sum I am stuck with. Find the value of $${1 \choose 0}+{4 \choose 1}+{7 \choose 2} +\ldots+{3n+1 \choose n}$$ where ${n \choose r}$ is the usual combination. A little hint will be ...
3
votes
2answers
29 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 ...