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)

1
vote
1answer
654 views

Given n girls and boys how many ways are there to arrange them such that any two boys have atleast 'k' girls between them.

Professor X wants to position $1 \leq N \leq 100,000$ girls and boys in a single row to present at the annual fair. Professor has observed that the boys have been quite pugnacious lately; if two ...
3
votes
1answer
101 views
+100

Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$

I'm trying to characterize the behavior of the the quantity: $$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$ subject to the constraints that $$ \sum \limits_{i = 1}^N ...
2
votes
1answer
46 views

How many odd numbers can be formed using the digits $0, 4, 5, 7$?

How many odd numbers can be formed using digits $0,4,5,7$. I am getting answer $12$ but the actual answer is $14$.
4
votes
0answers
24 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
1
vote
2answers
40 views

Circular arrangements of identical objects [duplicate]

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

Partitioning a graph such that size of cut is maximum for number of vertices odd

Given a graph $G$ with $n$ vertices and $m$ edges, a cut $C$ of the graph are two disjoint subsets of the vertices $V_1$ and $V_2$ such that number of edges from $V_1$ to $V_2$ is maximum. This number ...
2
votes
1answer
28 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
0answers
51 views

Why is unit circle not sufficient to bound the partial sums?

I want to find vectors $\textbf{v}_1, \dots,\textbf{v}_n$ in $\mathbb{R}^2$ with that $\sum_{i=1}^n\textbf{v}_i=\textbf{0}$ and $\Vert \textbf{v}_i\Vert\leq 1$ for all $i=1,\dots,n$, such that for ...
1
vote
2answers
32 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
10 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 ...
-2
votes
1answer
23 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
0answers
23 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
43 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
votes
1answer
25 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
votes
1answer
39 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
26 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$ ...
8
votes
2answers
108 views

Probability of getting A to K on single scan of shuffled deck

Let us say we have a regular 52-card well-shuffled deck. We scan through the deck (first to last) till we find an Ace. Then we continue (from that Ace) till we find a 2. Then we scan (from the 2) ...
2
votes
2answers
30 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
2answers
69 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
79 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$.
0
votes
1answer
44 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 ...
-2
votes
0answers
21 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 ...
-3
votes
0answers
29 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 $
-1
votes
1answer
32 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
15 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, ...
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 ...
2
votes
1answer
37 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 ...
0
votes
1answer
82 views
+50

Result of a $2D$ random walk with position dependent probabilities of step

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk:- A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
1
vote
1answer
16 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 ...
0
votes
1answer
23 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 ...
3
votes
2answers
33 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 ...
1
vote
1answer
84 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 ...
0
votes
0answers
21 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 ...
1
vote
3answers
1k views

How many strings of length 12 can we compose using letters A, B, C, and D if every letter should appear at least once?

How many strings of length 12 can we compose using letters A,B,C, and D if every letter should appear at least once? can someone walk me through this? I believe using the concept of the sieve formula ...
0
votes
0answers
26 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 ...
-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 ...
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} ...
4
votes
3answers
35 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 ...
1
vote
3answers
41 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 ...
1
vote
1answer
21 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
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
1answer
35 views

Number of labeled graphs satisfying a degree sequence

Say we have two sequences of integers $d^\text{in}$ and $d^\text{out}$ representing the in- and out-degree sequences of a directed graph. How many (possibly isomorphic) graphs are there that satisfy ...
0
votes
1answer
39 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 ...
5
votes
5answers
75 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!
0
votes
0answers
60 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: ...
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
votes
0answers
57 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}$$
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 $
0
votes
2answers
30 views

How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contain at least 1 object?

How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contain at least 1 object? Can anyone tell me how should I approach this ...