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
0answers
27 views

Combinatorial express of n^3 [duplicate]

I know following expression $$n = {n\choose 1 } $$ $$n^2 = {n\choose 2 } + {n+1\choose 2 }$$ but how about $n^3 = $? Are there simple expression?
2
votes
2answers
24 views

Computing the $n^{\textrm{th}}$ permutation of bits.

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT ...
2
votes
1answer
70 views

Impossible Math Riddle

Mathematician A asks Mathematician B to guess the age of his three sons. Mathematician A starts off by giving Mathematician B two clues. The two clues are: The product of their ages is 72. When you ...
0
votes
1answer
23 views

All possible variants of representation natural number N as product of natural numbers

Task : describe a predicate (on Prolog) that count all possible variants of representation of natural number N as product of natural numbers. For example, 6 = 6*1 = 2*3, so answer is 2. The program ...
0
votes
1answer
46 views

How many combinations are there?

I have $4$ electrons to place in $7$ orbitals. Each orbital can hold up to some maximum number of electrons. Let's name the orbitals $a,b,c,d,e,f,g$ for reference. Let's say the maximums are ...
2
votes
2answers
34 views

Probability and Combinatorics without replacement

If I have a sample space of $A$ and I randomly select $a$ elements, mark them, put them back into the sample space, then randomly select $b$ elements and I want to know what the probability is that ...
2
votes
2answers
25 views

Proof that repeated sum equals binomial formula

Let $s, d$ be positive integers. Can you prove the following general formula for the repeated sum? I developed this problem on my own, but is it a well known result? $$\sum_{i_1 = 0}^s \sum_{i_2 = ...
0
votes
1answer
24 views

Multinomial Joint Probability: Red *and* blue balls

Say that there is an urn with balls of different colors. $P(R)$ and $P(B)$ are the probabilities of drawing red or blue balls. These do not add up to one. Say I have $N$ draws (with putting back the ...
1
vote
1answer
21 views

Distributing infinite supply of $n$ distinct objects into $k$ identical urns

I have $n$ distinct objects, namely {$n_{1\le i \le n}$} with an infinite supply of each of them, and I have $k$ identical, indistinguishable urns to place the objects in. Each urn will contain ...
1
vote
0answers
24 views

Solution to a combinatorial constraint system

I am facing a combinatorial problem where I am interested in the minimum number of constraints of a certain type that uniquely determine a solution. I realize that my problem is highly specific (and I ...
0
votes
1answer
28 views

Word problem in linear equation

I just can't figure it out how to solve this one.The problem is as follows: Of 28 students taking at least one subject, the number taking Math and English but not History equals the number ...
1
vote
0answers
8 views

An optimization problem with a simplex constraint

Suppose $X^i=[0,1]$ for $i=1,2,3$. $X=\prod_i X^i$ and $\mu_i$ is a measure on $B([0,1])$ and $\mu$ is the product measure. Let $f,g,h$ be $L^2(\mu)$ integrable functions satisfying $$0\leq ...
0
votes
1answer
23 views

Dirichlet series generating function of a sequence

To find the dirichlet series generating function of the following sequence $\left\{\sum_{n/d}d^q\right\}_{n=1}^\infty$ The series is like this $\frac{1^q}{1^s} + \frac{1^q+2^q}{2^s} + ...
1
vote
1answer
25 views

What is $n>1$ so that there is an $n\times n$ board with a perfect square number of squares?

There is an $n\times n$ board ($n>1$) such that the total number of different squares it contains is a square of an integer. For example, a $2\times 2$ board contains $5$ different squares. Find ...
3
votes
1answer
42 views

Permutations of cards with no adjacent pairs

We have a standard 52-card deck, and are looking at the possible shuffles/permutations of this deck. However, we have rubbed off the suits from the cards, so for every rank (aces, tens, etc.) all ...
0
votes
0answers
39 views

What is the algorithm to generate the cards in the game “Dobble” ( known as “Spot it” in the USA )?h

In the game Dobble ( known in the USA as "Spot it" ) , there is a pack of 55 playing cards, each with 8 different symbols on them. What is remarkable ( mathematically ) is that any two cards chosen at ...
5
votes
2answers
92 views

How many ways to select $k$ vertices of an $n$-gon?

I have a regular $n$-gon, of which I have to select $k$ vertices. The selections must be rotationally distinct; two selections would be considered equivalent if one is a rotation of the other. For ...
2
votes
2answers
43 views

the number of copy of 6-cycles in petersen graph

the number of copy of 6-cycles in petersen graph.I know that Petersen graph has ten copy of 6-cycles but I can't prove it.
1
vote
2answers
32 views

Arranging the word CLASSICS [on hold]

The letters of the word CLASSICS are to be arranged in a row. How many of the arrangements end with a letter other than S?
0
votes
1answer
14 views

Subdivide Unconditional Probability

Say, I have 6 urns, and balls of different color in each. I would like to compute the unconditional probability of drawing a red ball, when I somehow randomize over all urns. Now, my intuition tells ...
5
votes
1answer
105 views

Prove by combinatorial method that $ \frac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $ is an integer [duplicate]

Prove that $$ \dfrac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $$ is a positive integer, where $(m,n) \in \mathbb{Z^{+}}$ I have already solved it using Legendre's Formula ...
1
vote
0answers
10 views

VC-dimension for conjunctions with negations

I need any hint in the following problem. Let $\mathcal{F}_k$ be a set of all possible conjunctions of binary variables $x_1, \dots, x_k$ and their negations. How could I prove that ...
2
votes
3answers
47 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
24 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
25 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
20 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
2answers
51 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
46 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
35 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
37 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 ? (order not important)
1
vote
1answer
33 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
38 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
37 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
49 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 ...
0
votes
0answers
37 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
41 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
47 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
40 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
38 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 ...
9
votes
1answer
126 views

A logic problem about set theory

In a group of n people, subgroups with common interest are formed (football,tennis,snooker). The number of subgroups equals $2^{n-1}$. Any 3 subgroups have a common member. Prove that there is a ...
1
vote
2answers
46 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
14 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
32 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
26 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
25 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
76 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
71 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
37 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 ...