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
1answer
18 views

Combinations for pairing groups

I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask ...
3
votes
0answers
27 views

Is there an established notation for this “replacement” operation?

If $S$ is a set, define $$(x \to y) \cdot S := \begin{cases} (S \setminus \{x\}) \cup \{y\} & \text{ if } x \in S \text{ and } y \not \in S; \\ S & \text{ otherwise.} \end{cases}$$ In other ...
1
vote
1answer
3k views

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn't work. How do I approach this?
1
vote
5answers
98 views

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000$.

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000.$ My attempt: False, Let set $z = \{1,2,3\}$ then $|z|^{|x|}$ is set of function $y:x\to z.$ $|x| = n$ and $|z| = ...
11
votes
4answers
294 views

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon and no vertice ...
1
vote
2answers
36 views

How many die would I need to get an $n$ of a kind 100% of the time?

For example, if I wanted to get two of a kind, I would need seven dice. This is because even if the first six were 1, 2, 3, 4, 5, 6, the next one would have to make a pair out of the previous dice. ...
2
votes
2answers
76 views

Reducing the form of $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$.

I've been toying around with simplifying the expression $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$ (for integer only $n$) for a while, as I was hoping it ...
0
votes
0answers
8 views

Size of remaining search space for Vehicle Routing Problem given a partial solution

The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form ...
1
vote
3answers
23 views

Probability of choosing two bulbs with the same rating given that one has a specific rating

I am trying to teach myself statistics, and working through Jay DeVore's excellent text of "Probability and Statistics for Engineering and the Sciences". The problem is as follows: We have box of the ...
0
votes
1answer
25 views

Counting Positive Integer Divisors

Let $A$ be the set of all positive integer divisors of $3^6 5^8 11^{10} 17^{15}$. Define the relation $R$ on $A$ as follows. For $x, y \in A, xRy$ when $x | y$. Determine the number of ordered pairs ...
1
vote
1answer
18 views

Determining how many combinations there are when every item has a pair it can't exist with.

If we had 25 people all who have 2 different balls, how would you work out how many combinations there would be if we want to choose 25 balls, but no person can have both of their balls in the choice? ...
1
vote
1answer
260 views

How many different ways are there to organize 2 groups?

In how many different ways can you split 10 people into two groups with the same amount of people? My attempt: Since the order in which you choose someone doesn't matter, I chose to calculate the ...
0
votes
1answer
24 views

What is maximum value of “m” for following equation?

QUESTION: What is maximum value of "m" for following equation? $$\Sigma\ (^{10}C_i)( ^{20}C_{m-i})$$ where i is from 0 to m. (A) 5 (B) 10 (C) 15 (D) 20 MY ATTEMPT: I have written equation as, ...
0
votes
0answers
97 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a strongly $k $ regular graph G(srg($n,k,\lambda ,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ ...
-1
votes
1answer
19 views

College Students Seated at a Dinner Table [on hold]

A group of college students are going to a party. They are all sitting at the dinner table. Suppose that: There are $7$ girls who have a girl on their right side $12$ girls who have a guy on their ...
5
votes
3answers
70 views

Suppose a city with Three type of coins ?!

in a city we have tree type 1 dollar, 2 dollar, 3 dollar of coins. we want to pay for a 20 dollar product. how many ways we can pay for a 20 dollar product, if the seller has no money and number of 1 ...
1
vote
0answers
60 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
11
votes
3answers
800 views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
1
vote
2answers
62 views

Closed form of sum with binomial

I want to find closed form of the following expression : $$\sum\limits_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{2k+1}$$ I have no idea how to do it.
2
votes
1answer
77 views
+50

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

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

Combinatorics, distributing distinctive balls into identical containers

Here is a problem I am trying to solve: Determine the number of ways to distribute 6 balls into 5 containers if the balls are all different and the containers are all identical. The answer is, that ...
5
votes
0answers
127 views
+50

The recurrence $a_k(n) = \sum_{0\leqslant j<n} a_{k-1}(n+j)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a_k(0) = 0, \quad \forall k\geqslant 1; \\ &a_k(1) = 1, \quad \forall k\geqslant 1; \\ ...
1
vote
0answers
32 views

Most efficient algorithm to distribute n n-bit strings among n people [on hold]

If there are N people, and a corresponding set of subsets K, what is the most efficient algorithmic approach I can use to give everyone a (not necessarily unique) N-bit string (leading zeroes ...
0
votes
1answer
34 views

How many different groups of two people can be selected from a group containing $n$ people? [on hold]

Lets say you 2 men and 1 women. Isn't there some formula for calculating how many different groups of 2 there are? I know I can manually write it with this small sample but when it gets bigger this is ...
1
vote
1answer
33 views

Sum of the series with Stirling numbers of the first kind.

Yesterday I worked on one problem in discrete math and in the process of decision I came across this series. Try to do it with generating functions, but there is no success for me. So, what do you ...
-4
votes
1answer
28 views

Four letters {A, B, C, D} are arranged in a line. What is the probability that A and B will be next to each other? [on hold]

Four letters $\{A, B, C, D\}$ are arranged, with no repetitions and always using the four. What is the probability that $A$ and $B$ will be next to each other?
2
votes
2answers
258 views

Combinatorics of a tournament where one wins by taking either three games in a row or four in total

Two teams play each other repeatedly until either one of them wins three games in a row or one of them wins a total of four games. What are all the ways in which the tournament can be played? What ...
4
votes
1answer
31 views

Counting problem - verification please?

A question we did in class asks: "In how many ways can we put 4 girls and 4 boys on a row (so order matters) so that a certain girl and a certain boy are always seated next to each other, and no 2 ...
0
votes
3answers
2k 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 ...
0
votes
0answers
25 views

In how many ways can five different keys be put in a flat leather key case? [on hold]

In how many ways can five different keys be put in a flat leather key case?
-4
votes
1answer
33 views

In how many ways can two chocolate chip, three raisin, and one peanut butter cookie be distributed to six children? [on hold]

A mother has six cookies, two chocolate chip, three raisin, and one peanut butter. In how many distinct ways can she pass them out to six children so that each gets one? Assume that those of the ...
2
votes
0answers
26 views

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
1
vote
2answers
27 views

Conditional probability with students seating

There are 14 students and 9 of them are friends. Students purchased tickets to movie and they got seats in a row of 14 seats. 8 friends got seats next to each other. What is the probability that ...
-2
votes
1answer
17 views

Questions regarding seating arrangements [on hold]

Consider there are $9$ people and $3$ tables that sits the following way ($5$ chairs, $3$ chairs and $2$ chairs). How many combinations if order matters to the people being seated and no chair can be ...
0
votes
1answer
56 views

combinatorics contest problem

Question: Calvin has a bag containing $50$ red balls, $50$ blue balls, and $30$ yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out $5$ more red ...
1
vote
2answers
71 views

Probability in a Restaurant

In a revolving restaurant, there are four round tables each with three seats. How many different ways can $12$ people sit in this restaurant? This is what I think the answer is: $$\binom{12}{4} ...
1
vote
0answers
23 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
4
votes
3answers
56 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
3
votes
1answer
43 views

Why this solution of the birthday problem is wrong? [duplicate]

If we have $n$ people there are $n(n-1)/2$ possible pairs that we can find. The probability that any two people have the same birthday is $1/365$. So for $n$ people the probability of finding at least ...
1
vote
4answers
39 views

How many ways can you choose $4$ teams of $2$ from $8$ people.

How many ways can you choose $4$ teams of $2$ from $8$ people. My thoughts were that you have $8$ slots to be filled so you have $8!$ ways to arrange them but this overcounts by a factor of $2$ since ...
0
votes
0answers
43 views

When will the game end? [on hold]

Two men are playing a game. They have a card deck consisting of exactly 10 cards, numbered from 1 to 10, and all values are different. On each turn a fight happens. Each of them picks one card from ...
3
votes
4answers
41 views

6 people are holding a show, one at a time, such that person $x$ has to go after person $y$ and person $z$. How many ways could the show be held?

Let's say the people are called $a$, $b$, $c$, $x$, $y$, $z$ My initial thinking was to go by fixing "$x$" in a certain position, so: $\underline {} \underline {} \underline {}\underline ...
1
vote
0answers
17 views

Lines and planes-recursive formula

A family of $n$ lines is drawn in the plane such that each pair of lines cross and no $3$ dinstinct lines have a point in common Let $r(n)$ denote the number of regions into ...
0
votes
1answer
64 views

Tricky question about binomial expansions. [duplicate]

State the binomial expansion of $(1+x)^n$ So I can do this $$(1+x)^n=\sum_{i=0}^{n} {n\choose i}x^i$$ Then given $n=2k$ is even. Derive an expression for $$\sum_{i=0}^{2k} (-1)^i{2k\choose i}$$ ...
2
votes
1answer
71 views

Trirectangular tetrahedron

Looking at http://mathworld.wolfram.com/TrirectangularTetrahedron.html I wonder what the symmetry group of a trirectangular tetrahedron is?
0
votes
1answer
73 views

How to find weight function using generating series?

How to find the weight function and corresponding set given the generating series? Is there a general method for this kind of problems, I am preparing for an olympiad. Consider the below example: ...
1
vote
1answer
41 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
6
votes
2answers
137 views

Proof of an identity of $n!$

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is: \begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n ...
1
vote
0answers
43 views

Lights out - foobar - optimise python implementation beyond binary matrix solver

I'm looking for further details on solving 'Lights out' puzzle, as asked in foobar challenge. Sorry I don't have enough credit to add/comment on existing threads, but I'm interested in a specific ...
1
vote
0answers
14 views

Number of ways to connect sets of k vertices in a perfect n-gon [duplicate]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...