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)

2
votes
3answers
39 views

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays each. Miklos Bona rates this question as "less difficult than average" while I am stuck on it although I ...
0
votes
1answer
22 views

Number of subsets of $\{0,1,2,…,9\}$ with symmetric difference $\leq 2$

There is a problem asking to prove that among any 100 subsets of $\{0, 2, 3, \dots , 9\}$ there will be two with cardinality of their symmetric difference less than or equal to two. It is proven by ...
2
votes
0answers
21 views

Maximum independent sets of $k$-partite graphs

Consider a $k$-partite graph $G=(V,E)$. This means that its vertices can be partitioned into $k$ different independent sets, say $V_1,\dots, V_k$. Assume further that $|V_1|=\dots = |V_k|$. Under ...
0
votes
1answer
16 views

Solving a series in the proof of the expectation of the binomial distribution

I am studying the expectations and variances of the most common distributions. For the binomial distribution the mean is equal to $np$. Considering $p$ and $q$ independent variables and ...
2
votes
1answer
30 views

Nested sum $\sum_{i<j< \cdots < k} ij \cdots k$

I am wondering if there is any known closed form for the following nested sum? : $$ \sum_{i<j<\cdots <k} ij\cdots k $$ where each $i,j,\cdots,k =1, \cdots, n$ I tried the first one: $$ ...
0
votes
2answers
32 views

How many 2 digit even numbers can be formed from these numbers?

How many even 2 digit numbers can be formed from the numbers 3,4,5,6,7? The digits cannot repeat (you can't have 44 or 66 for example). I know the answer to this is 8, because I just wrote them all ...
2
votes
1answer
31 views

Proof Bell-Number $B(n+1)=\sum\limits_{i=0}^n\binom{n}{i}B(i)$

Let B(0) := 1 und B(n) for n$\geq$1 the counts of all sets partitions of [n]. The numbers B(n) are the Bell-numbers. For $n \geq 0$ prove that: \begin{equation} ...
-3
votes
0answers
33 views

Counting the number of ways. [on hold]

In how many ways can a person select $3m$ objects from a collection of '$2m$' distinct pens and '$(4m)$'identical pencils ?
1
vote
1answer
31 views

Closed formula for ordinary power series generating function

To find the ordinary power series generating function of $\left\{\frac{1}{n+1}\right\}_2^\infty$, I tried to solve it like this, let $$\begin{align} f &= \frac{x^{n-2}}{n+1}, \text{ where }n \ge ...
1
vote
1answer
37 views

How many class schedules are possible?

You have $5$ choices of a math class, $2$ choices of history class, and $6$ choices of writing class. If you are planning to take one of each class, how many possible schedules could you have? What I ...
4
votes
2answers
29 views

Multiplication Principle and Inclusion-Exclusion: $2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}$

I began to compose an unnecessarily complicated answer to this question: 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 ...
4
votes
5answers
47 views

Counting clarification

In the text I am reading there's a question: From the digits $0, 1, 2, 3, 4, 5, 6$, how many four-digit numbers with distinct digits can be constructed? How many of these are even numbers? I get the ...
1
vote
0answers
32 views

A Good book for Combinatorial Theory

I am looking for a good book on Elementary Combinatorics (Olympiad level). For some reason I do not like Lint. I am currently reading "A Walk Through Combinatorics" by Miklos Bona and I find it really ...
1
vote
1answer
22 views

Incomplete beta integral

Let n be greater than one, and B be the beta integral, $$\sum _{j=0}^{\infty } C_j B_{\frac{1}{n}}(j+1,j+2)=\frac{1}{n}$$ Is it correct to call this an inversion formula? What possible ideas are ...
1
vote
2answers
39 views

how many ways to partition a set with k subsets, each of fixed size?

if $(v_1,...,v_k)$ is a partition of $n$, how many ways $M((v_1,...,v_k),n)$ is there to create a set (partition) of $k$ elements, each of size $v_i$ , i=1,...,k from $n \geq k$ distinct elements ? ...
0
votes
1answer
46 views

prove $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

A descent in the permutation $\sigma = a_1 \cdots a_n \in S_n$ is an index $i\in[n-1$] for which $a_i > a_{i+1}$. Let A(n, k) be the number of permutations of $[n]$ with $k-1$ descents where $n ...
3
votes
0answers
37 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
35 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 ...
1
vote
2answers
44 views

How many dice 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. ...
0
votes
0answers
11 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 ...
0
votes
1answer
31 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
25 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
votes
1answer
21 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
74 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 ...
0
votes
1answer
28 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, ...
1
vote
2answers
69 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.
0
votes
0answers
32 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 ...
2
votes
2answers
52 views

Most efficient algorithm to distribute n n-bit strings among n people

We are given $n$ people, whom we identify with the elements of $[n]=\{1,\ldots,n\}$. We are also given a finite collection $\mathcal{K}$ of subsets of $[n]$. The problem is to (efficiently) ...
1
vote
1answer
265 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
35 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
36 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 ...
2
votes
2answers
88 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 ...
1
vote
3answers
27 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 ...
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
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 ...
6
votes
0answers
51 views
+50

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 ...
-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 ...
3
votes
1answer
44 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 ...
4
votes
3answers
58 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 ...
1
vote
0answers
62 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 ...
0
votes
0answers
44 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 ...
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 ...
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
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
73 views

Trirectangular tetrahedron

Looking at http://mathworld.wolfram.com/TrirectangularTetrahedron.html I wonder what the symmetry group of a trirectangular tetrahedron is?
1
vote
5answers
107 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| = ...
-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?
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 ...
1
vote
2answers
72 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} ...