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
68 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 ...
4
votes
2answers
393 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?
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?
0
votes
1answer
34 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$
1
vote
1answer
28 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 ...
0
votes
1answer
32 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 ...
2
votes
2answers
56 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 ...
0
votes
1answer
29 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: ...
0
votes
0answers
14 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 ...
1
vote
2answers
36 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 ...
8
votes
1answer
162 views
+50

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 ...
1
vote
2answers
30 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
31 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 ...
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 ...
2
votes
1answer
47 views

tricky question in combinatorics - deck of cards [closed]

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 ...
0
votes
2answers
41 views

Counting number ways of expressing a given integer as a sum of other integers

Consider this counting problems ...
6
votes
2answers
434 views

Is there a planar graph that (almost) all its vertices have 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 ...
2
votes
2answers
63 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 ...
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? $$
-3
votes
2answers
32 views

a Combinatorics problem in series [closed]

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 ...
2
votes
1answer
22 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 ...
0
votes
1answer
32 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$?
3
votes
4answers
96 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 ...
3
votes
1answer
31 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 ...
3
votes
2answers
353 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
53 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
38 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
68 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
49 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
49 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
44 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
77 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 ...