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)

4
votes
4answers
62 views

Finding all possible combination **patterns** - as opposed to all possible combinations

I start off with trying to find the number of possible combinations for a 5x5 grid (25 spaces), where each space could be a color from 1-4 (so 1, 2, 3, or 4) I do ...
1
vote
2answers
51 views

Lottery based counting problem based on uniqueness and monotonicity

I was solving this problem and have prepared a solution here. Problem summary: Consider choosing Blank number of integers from 1 to ...
0
votes
1answer
25 views

How restrictions reduce the number of possible arrangements

A company has five departments. The company is establishing a board consisting of five members that represent a distinct department each. Suppose that every employee is a candidate to represent his ...
4
votes
2answers
383 views

Where can the knight be?

The answer is 33. I get $24$. Because of $8 \cdot 3 = 24$? How can I do this using combinatorics?
2
votes
2answers
52 views

Counting bit strings of length 10 contain either 5 consecutive 0's or 5 consecutive 1's

How many bit strings of length 10 contain either five consecutive 0's or five consecutive 1's ? My Solution: for 5 consecutive 0's After we have filled 0's from $1^{st}$ position we have 2 ...
1
vote
1answer
26 views

Maximal Multiplication of All Possible Summands

I have recently got interested in the following problem: Give a decomposition of a natural number to natural summands whose multiplication is maximal. I have tried to solve this problem, and ...
2
votes
3answers
1k views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
1
vote
2answers
43 views

Combinatorics using a geometric diagram

How can I do this without trial-and-error? It has something to do with a triangle and summing the next row?
2
votes
2answers
45 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?
4
votes
2answers
750 views

Outcome of rolling a fair die 6 times

I'm failing to understand how to come to the answer to this question. If you roll a fair die six times, what is the probability that the numbers recorded are $1$, $2$, $3$, $4$, $5$, and $6$ in any ...
0
votes
1answer
33 views

How many possible paths?

The answer is $32$. Its supposed to be $2^5$ but I do not see how you get that? The way I see it, there are $5$ ways to go up and $5$ ways to go right, total ways = $5x5= 25$
0
votes
1answer
29 views

An interesting mathematics task.

Find the number of different ways of arrangement of all natural numbers from 1 to 9 inclusive, one in table cells measuring 3 by 3 such that the sum of the numbers in each row and each column are ...
0
votes
1answer
28 views

Probability of getting an average of 3 or more by rolling 4 sided die twice

What I understood is the sample mean of two rolls of all sample space(16) as given below: ...
1
vote
2answers
35 views

Pairs of integeres for which the arithmetic mean exceeds the geometric mean exactly by $2$

Suppose $0<x<y<2015$ are integers. How many pairs of $x$ and $y$ are there for which the arithmetic mean exceeds the geometric mean exactly by $2$? Progress Obtained the equation ...
1
vote
2answers
92 views

Number of lists at some Kendall-Tau distance

Given a ranked list (permutation) $R$ of $n$ elements, how many permutations of the same elements are there at Kendall-Tau distance $d$ from $R$ $(0 \le d \le \frac{n(n-1)}{2})$? Example: If $R = ...
0
votes
0answers
12 views

Ways of partitioning n points into some cubes

Assume there're $n$ fixed points in $\mathbb{R}^d$ contained in a ball with radius $M$,and you can partition the space by cubic grid with cube's edge length $h>\epsilon$. How many different ways of ...
3
votes
2answers
295 views

Combinatorics help. Palindromic 6 letter sequences.

The genetic code can be viewed as a sequence of four letters T, A, G, and C. There were two parts to the question: (a) How many 6-letter sequences are there? I just said $\binom{4}{1}^6$, or ...
0
votes
2answers
6k views

Drawer contains socks. If I randomly pull 2, what is the probability that I will get a matching pair?

My drawer contains 4 blue socks, 7 red socks, and 3 yellow socks. If I randomly pull 2 socks at the same time, what is the probability that the socks are the same color? I know that the probability ...
3
votes
1answer
47 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 ...
2
votes
1answer
37 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 ...
5
votes
0answers
47 views

A set of integers whose elements all divide $2015^{200}$ but do not divide each other

Let $S$ be a set of natural numbers,such that each element divides $2015^{200}$ but for no two elements $a$ and $b$, $a|b$. Find the maximum number of elements in $S$ . $2015^{200}=(5\cdot ...
3
votes
4answers
82 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
6
votes
0answers
48 views

Finding a separating family of subsets of $[n]$ of size $n+1$.

I have this friend who always tells me problems I can't solve. Here is the latest one. We are given a family $\mathcal F$ of at least $2^{n-1}+1 $ subsets $[n]$. We must prove that we can ...
1
vote
2answers
27 views

Number of 5 letter words with at least one double letter

How many 5 letter words have at least one double letter, i.e. two consecutive letters that are the same? Answer is: $26^5 – 26*25^4 = 1,725,126 $ But how can i solve? I don't understand. The book ...
1
vote
1answer
30 views

Is there an upper bound on Bell numbers?

For some reason my intuition is that $n^n$ might be an upper bound for Bell numbers, but I can't find anything to confirm that. Sorry if this is a simple question! (it's been a while since my ...
0
votes
0answers
29 views

How to display one to one correspondence for all bit strings not containing the bit O?

This is a problem from Discrete Mathematics and its Applications From the onset I saw that this set was countable was that you could physically count these out - 1, 11, 111, 1111 and perhaps ...
2
votes
1answer
389 views

Number of permutations with a single fixed point

I know that the number of permutations with no fixed points over a set with $n$ elements approaches $\frac{n!}e$ as $n$ grows. I'm interested in finding a limit (if there's exist) for the number of ...
0
votes
0answers
30 views

Solving a proof by combinatoric method

Any good questions you guys have in mind?: prove the following equation by coming up with a combinatoric problem and solving it step by step (Solve combinatoric method): $$ {n \choose 1} + 14{n ...
1
vote
1answer
46 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 ...
2
votes
1answer
47 views

tricky question in combinatorics - deck of cards [on hold]

A deck of cards with $4$ sets, each set contains $13$ cards. We want to create a new sequence of $n$ cards: each time we choose a card, write it down as the next element in the sequence, put it back ...
0
votes
1answer
26 views

Finding the combination between 2 sets

8 balls are pulled at random from a bag of 32. Each ball is numbered 1-32. Balls that are 1-16 go into set $S_1$. $x_i \in \{1,2,3...16\}$ $S_1 = \{x_1, x_2, x_3, x_4\}$ Balls that are ...
18
votes
2answers
12k views

A comprehensive list of binomial identities?

Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
0
votes
3answers
520 views

How many different phone numbers are possible within an area code?

A phone number is composed of 10 digits. The first three are the area code the other 7 are the local telephone number which cannot begin with a 0. How many different telephone numbers are possible ...
1
vote
2answers
60 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 ...
1
vote
1answer
35 views

Is there a set of integers where all differences are relatively prime?

Is there an infinite subset $\mathcal S\subset \mathbb Z$ with the property that for any 4-tuple of distinct elements $x,y,z,w\in \mathcal S$ $$ \gcd(x-y,z-w)=1? $$
6
votes
2answers
427 views

Is there a planar graph that (almost) all its vertices has degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
1
vote
0answers
23 views

Enumeration of points with infinite dimensions

A well known way to enumerate points with finite support in an infinite dimensions space $N \times N \times ...$ and avoid duplicates is to use the exponents of the factorization of $n$ as the ...
0
votes
1answer
529 views

What is the probability of picking Exactly 1 red marble and than not 1 red marble? without rep.

A urn has 3 red marbles, 2 blue marbles, 1white, 1 black 1 brown. What is the probability of getting exactly 1 red marble than not 1 red marble? What is the probability of getting at least 1 red ...
2
votes
2answers
59 views

How many arrangements do we have?

We have $N$ boxes and an inexhaustible supply of objects belonging to $k$ distinct classes such that $N\gt k$. How many different arrangements of the objects in the boxes are there if (a) each of ...
0
votes
1answer
56 views
+50

Help with developing equation with combinatorial numbers

How can I get from $$k^{4} = a*\binom{k}{1}+b*\binom{k}{2}+c*\binom{k}{3}+d*\binom{k}{4}$$ to \begin{equation} k^{4} = \frac{(24a-12b+8c-6d)k+(12b-12c+11d)k^{2}+(4c-6d)k^{3}+dk^{4}}{4!} ...
2
votes
1answer
21 views

Algorithm to partition a set into subsets of max weight

I have a big set $S$ of elements $e_i$, each $e_i$ characterized by an integer weight $w_i$. I would like an algorithm to split set $S$ into subsets $S_j$ such that: The sum of weights in each ...
-3
votes
2answers
32 views

a Combinatorics problem in series [on hold]

Hey everyone i was having a problem with the following question: in how many ways is it possible to solve the following equation using natural numbers: $$ x_1+x_2+x_3...+x_{15}=300 $$ that for every ...
0
votes
1answer
22 views

largest independent set in a circuit of length $n$

largest independent set in a circuit of length $7$ and $n$? For $7$, I guessed it's $3$. Guidance on finding for $n$?
8
votes
2answers
112 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
3
votes
1answer
30 views

Combinatorial Identities

I am trying to prove the following identities: a. $$\sum_{k=0}^n(-1)^k{n\choose k}^2 = \bigg\{^{0 \ \text{if k is odd}}_{(-1)^m{2m\choose m} \ \text{if n = 2m}}$$ b. $$\sum^k_{i=0} {n+i ...
5
votes
2answers
816 views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
0
votes
0answers
29 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
2answers
348 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
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 ...