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.

learn more… | top users | synonyms (4)

0
votes
0answers
5 views

Nice embedding of the permutohedron of order $n$ in ${\mathbb R}^{n-1}$

The permutohedron $P_n$ of order $n$ ($n\geqslant 2$) is the convex hull of the points $P_\pi=(\pi(1),\dots,\pi(n))$ where $\pi$ ranges over all permutations of $\{1,2,\dots,n\}$. Obviously, since ...
0
votes
1answer
13 views

Probability - very difficult combinatorial question - don't have the theoretical background

Combinatorics - a (very) old question (which I hope I have remembered correctly) from a Cambridge Math Tripos. "A student sits 6 examination papers, each worth 100 marks. In how many possible ways can ...
-2
votes
0answers
18 views

How to evaluate this counting problem

40 slips of paper numbered 1 to 40 are placed in a hat and two are drawn out. How many different unordered pairs of numbers can be drawn. I assume this is a combination type of prob since order is ...
-2
votes
1answer
20 views

number of strings of length n with an odd number of 0's

I need to find the number of strings of length n from the alphabet {0,1} that contain an odd number of 0's. Can anyone help? Thanks!
2
votes
1answer
16 views

Steiner Triple System

A Steiner Triple System, denoted by $STS(v),$ is a pair $(S,T)$ consisting of a set $S$ with $v$ elements, and a set $T$ consisting of triples of $S$ such that every pair of elements of $S$ appear ...
1
vote
1answer
19 views

Four different green balls and red balls

In how many ways can $4$ different Green balls and $4$ different Red balls be Distributed to $4$ persons equally such that each will get balls of same color. My Try: Let Green balls be $G_1$, $G_2$, ...
2
votes
1answer
34 views

composition of an integer number

Given two positive integers $m$ and $n$. I would like one special non-negative solution to the following system (which is related to a composition of an integer number): $$\begin{cases} \sum a_i = m ...
-1
votes
1answer
16 views

Combinatorial Proof with Integer Partitions

Give a combinatorial proof of the equality $p_{n}(2n) = p(n)$. I know I have to do some kind of bijection, but I am new to integer partitions and I do not have a book for this class... ...
1
vote
1answer
24 views

Circular arrangements of identical objects

Q> In how many ways can 5 identical red beads, 3 identical green beads and 2 identical blue beads be arranged in a necklace?
2
votes
2answers
27 views

Compute Using Binomial Theorem [duplicate]

$$\sum_{k=1}^{10} \binom{10}{k} $$ I know the answer is $2^{10} - 1$ but I don't know how to get to the answer.
2
votes
1answer
18 views

Changing order of summation including a min in the summation

Lets say I have the following expression: $$ h(x) = \sum_{k=1}^n \sum_{v=1}^{\min\{k,j\}} \frac{(-1)^{n-k}k!}{(k-v)!} {n \brack k}f(x)^{k-v} B_{n,v}^f(x) $$ Now my goal is to have the $v$ ...
2
votes
2answers
45 views

What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?

Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$ containing $2$ consecutive $0$'s. I've determined the total number of possible bit ...
2
votes
3answers
73 views

Number of functions verifying $f(f(x))=f(x)$.

Find the number of functions $f:\{1,2,3,4\}\to \{1,2,3,4\}$ that verify $f(f(x))=f(x)$. I'm not sure if the answer is $41$ or $29$.
-2
votes
0answers
19 views

Ribbon and colours [on hold]

A ribbon is composed from 9 square fabric pieces (i.e. is $1\times9$ rectangle). How many different ribbons can be made if there are fabrics of two colors and $5$ cells should be red and $4$ cells ...
0
votes
0answers
21 views

Recurrence relation for a mortgage

Find a recurrence relation for the amount of money outstanding on a \$40,000 mortgage after n years. The interest rate on the mortgage is 10% and the yearly payment is \$2,000( the yearly payment is ...
-2
votes
0answers
24 views

Polya theorem and necklaces [on hold]

How many $10-$ bead necklaces can you make out of $2$ red bead, $3$ blue beads and $5$ white beads $|G| = |D_{10}| = 20 $
2
votes
1answer
22 views

Combinatorics/Probability unordered lists

I don't really understand these unordered lists problems such as... Q: John goes to a store and buys 10 pieces of fruit from the selection of apples, bananas,peaches and pears at random. What is the ...
-1
votes
1answer
28 views

Pigeonhole principle subsets question [on hold]

A set X has 11 elements. Prove that in any 10 4 element subsets which can be formed from X, some two subsets must have two common elements.
2
votes
1answer
34 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
-1
votes
1answer
36 views

To add the following pair of combinatorials

How to write sum of these combinatorials as one combination term $$\binom{N-1}{y} + \binom{N-2}{y-1}$$
2
votes
1answer
14 views

number of weak compositions modulo prime $p$

For $n\in \mathbb{N}$ and some prime $p$, consider $(\mathbb{F}_p)^n$. Is it known how many weak compositions $$x_1+x_2+\ldots +x_n\equiv 0 \pmod p$$ in $\mathbb{F}_p$ there are, where $(x_1, \ldots, ...
1
vote
1answer
13 views

How can we tell from looking at a problem that multiplication principle fails to solve it? And why does MP fail(?) in the first place?

Three officers—a president, a treasurer, and a secretary— are to be chosen from among four people: Ann, Bob, Cyd, and Dan. Suppose that Bob is not qualified to be treasurer and Cyd’s other ...
5
votes
0answers
38 views

In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem: "In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?" Here is my attempt: Since $1000000 = 2^6 \cdot ...
0
votes
1answer
19 views

Rectangle tilling with smaller rectangles

To find the no of ways a rectangle of size 2 $\times $ n can be filled using 1 $\times $ 2 and 2 $\times$ 2 pieces. $$\quad$$ I tried to solve it as a recurrence relation, $a_{2 \times (n+2)} = a_{2 ...
0
votes
1answer
36 views

Finding the sum of special multiplications

Let $n$ be an integer and $a_1, \dots, a_n$ positive reals. $\forall 1 \leq i < j \leq n$ let $a_{i, j}$ be a positive number. Let $k \leq n$ be a positive integer. I would like to find an ...
3
votes
2answers
31 views

Stuck in a problem in permutation and combination.

I am solving problems in permutation & combination and stuck in this problem. Two players $P_1$ and $P_2$ play a series of $2n$ games. Each game can result in either a win or a loss for $P_1$. ...
1
vote
1answer
17 views

Inclusion Exclusion with 4 sets: How many integers between 1 and 100 are divisible by 2 or 3 or 5 or 7?

How many numbers between 1 and 100 are divisible by 2 or 3 or 5 or 7? The solution I had gives a different answer from what was provided, so I was wandering if anyone could tell me what mistake I ...
0
votes
0answers
20 views

Intersection of balls in Hamming space

Let $B(x_1, r)$ and $B(x_2,r)$ be balls in $\{0,1\}^n$ (in Hamming distance). Denote by $d$ Hamming distance between $x_1$ and $x_2$. What is $|B(x_1, r) \cap B(x_2, r)|$ (asymptotically)? Upd: I ...
0
votes
0answers
24 views

A combinatorics question about selection strategies

I am given a set of balls--red and blue. In each set, there are three kinds of balls--small, medium and large. In each set there are 10 balls of each color: 10 Red balls (2 small + 3 medium + 5 ...
0
votes
2answers
26 views

Defining a combinatorial problem for a given equation

I was given the following task: define a combinatorial problem to the following equation, and say how each side of the equation solves the given problem. The equation is: $$ n\binom{n}{r} ...
-3
votes
0answers
19 views

Largest subset with certain Hamming distance. [on hold]

The problem is about finding a largest subset such that each pair of its element is "far enough". Suppose $A\subset \{0,1\}^n$ and for any $x,y\in A$, the hamming distance between $x$ and $y$ is ...
4
votes
3answers
33 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
2
votes
1answer
39 views

How many numbers must be selected from 100…999 so that three of them have the same sum of digits?

A box contains 900 cards enumerated from 100 to 999 (Each number appears once and just in one card). I took some random cards without looking at them and calculated the sum of the digits in each one. ...
1
vote
2answers
26 views

Need help with figuring out what this definition of permutations actually means.

Here is a direct screenshot of the book: First of all, what does type mean? Does the author mean that the set with $r$ elements can be partitioned into $n$ subsets? Secondly, an $r$ permutation of ...
1
vote
3answers
39 views

Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are ...
0
votes
1answer
34 views

Composition of n into k parts, one part is odd and the rest are even

My task is to determine the number of compositions of $n$ into $k$ parts, such that exactly one part is odd and the rest are positive and even. I am trying to determine the set itself that I am ...
1
vote
1answer
18 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
-1
votes
0answers
49 views

Choosing M cards from N decks

Alice and Bob are playing cards. They have N decks of cards. Each deck of cards contain 52 cards: ...
-1
votes
0answers
54 views

How to simplify $\sum_{r=1}^{y} \binom{x-1}{r}\binom{y-1}{r}$? [on hold]

To find sum of the product of two combination terms $$\sum_{r=1}^{y-1} \binom{x-1}{r}\binom{y-1}{r}$$
6
votes
1answer
77 views

How many topologies exist on a finite set?

In my topology class we are asked to list all topologies on a $3$ element set. I have found $29$ and this should be the correct result. Now I wonder whether there is some formula that determines this ...
0
votes
1answer
34 views

to simplify the following combinatorial terms [on hold]

To simplify the following summation involving product of combinations $$\sum_{r=1}^{y}\left(\begin{array}{c} x-1 \\ r \end{array}\right) \left(\begin{array}{c} y-1 \\ r-1 ...
2
votes
1answer
59 views

How many five-digit number $ABCDE$ exist

How many five-digit numbers $ABCDE$ exist if, a) $A>B>C>D>E$ or b) $A≥B≥C≥D≥E $
5
votes
5answers
74 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
2
votes
1answer
24 views

Difference table for a sequence.

Let the sequence $h_0,h_1, ... h_n$ be defined by $h_n = 2n^2- n+3~(n \geq 0)$. Determine the difference table, and find a formula for summation of $h_0$ through $h_n$ I encountered this ...
1
vote
1answer
80 views

A math contest question related to Ramsey numbers

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the ...
3
votes
2answers
42 views

Counting $3$ digit even integers between $1$ and $1000$ with distinct digits

$5$ choices for the last digit, $9$ choices for the second digit and $7$ choices for the first digit: $5 * 9 * 7$ integers with the given property. Or $5$ choices for the last digit, $8$ choices for ...
2
votes
1answer
18 views

How do I read this equation related to Combinations with repetitions in natural language?

Here's an Article from TopCoder about Combinatorics, that starts by introducing some basic concepts such as: Combinations and permutations. That part I understood just fine, but then the article ...
1
vote
1answer
33 views

Is there any upper bound of this sum?

$a_1,a_2,\ldots,a_n,k$ are all integers. Is there any upper bound of the following sum $$\sum_{a_1+a_2+\cdots+a_n=k\textrm{ and } a_1,a_2,\ldots,a_n\ge 0} \frac{1}{a_1!a_2!\cdots a_n!},$$ which is a ...
0
votes
1answer
16 views

Restricted Derangement - Envelope Letter Problem

There are 5 envelopes numbered from 1 to 5 and 5 letters numbered 1 to 5.Letter numbered 1 is always placed in envelope number 2.In how many ways the all the letters can be put in wrong envelopes? ...
0
votes
1answer
30 views

Formula for numerating the elements of the set

Is there a formula for numerating the elements of the set $$ D = \{ (i_1, i_2, \ldots, i_k): 1 \leq i_1 <i_2 < \ldots <i_k \leq n \} $$ (here $ n, k $ are positive integers, $ n> k $; $ ...