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

Do you have to use Latin Squares to solve the Social Golfer's problem?

I'm trying to write a program to solve the social golfers program constrained to a certain number of weeks and so far I've been using the Latin Squares method detailed here: ...
1
vote
3answers
43 views

number of subsets of even and odd

Let $A$ be a finite set. Prove or disprove: the number of subsets of $A$ whose size is even is equal to the number of subsets of $A$ whose size is odd. Example: $A = {1,2}$. The subsets of $A$ are ...
0
votes
2answers
35 views

Counting question proof involving binomial

Let $x,y,z,n$ be positive integers such that $x\leq y\leq z\leq n$. Prove (by counting in two different ways) that: $\binom {n} {x} \binom {n-x} {y-x} \binom {n-y} {z-y} = \binom {n} {z} \binom {z} ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
2
votes
0answers
24 views

Partitioning a set with intersections

Imagine that we want to give an exam consisting of $m$ problems to $n$ students in such a way that every two sets of problems have one or zero problems in common. Is there a closed formula to compute ...
1
vote
2answers
35 views

Move elements in a grid (Combinatorics)

Here's an interesting and fairly simple problem I encountered a couple of weeks ago. There is a grid with 11 rows and 11 columns with a ball in every cell. Move every ball to an adjacent cell (up, ...
2
votes
1answer
71 views

Learning Combinatorics Further

I have completed most of the basic parts in Combinatorics like Generalised Permutation & Combination, Recurrence relations, Pigeonhole Principle, Formal power series, Stirling no, Catalan no, ...
2
votes
1answer
22 views

weak compositions of $n$ with $2m$ parts and extra conditions

A weak composition of $n$ into $k$ parts is a sum $$\displaystyle \sum_{i=0}^k x_i=n$$ such that $x_i\in \mathbb{Z}$ and $x_i\geq 0$ for each $i$. I am trying to figure out the number of weak ...
3
votes
0answers
42 views

Coefficients of (generating) function

If I have the generating function \begin{equation*} A(x)= \frac{1}{(1-x^{10})\cdot(1-x^5)\cdot(1-x) }\,, \end{equation*} what is a clean way to find the coefficients of $x^{n}$. This coefficient ...
0
votes
1answer
41 views

Combinatorics Question about combining rows in a table

I have a table of rows, some rows I want to combine, but not others, for example because the number of cases in adjoining rows is small. If I have separate rows $A,B,C$, I can combine them into $AB,C; ...
3
votes
0answers
42 views

Extremal problem with infinite cardinals

Made up, but somewhat interesting: Let $\lambda\leq\kappa$ be infinite cardinals. Let $X$ be a set of cardinality $\kappa$. Let $F\subseteq [X]^\kappa$ be a family of $2^\kappa$ subsets, which is ...
0
votes
2answers
70 views

Sum of squares of distances between all vertices in tree

Given the adjacency list of unweighted undirected graph without cycles, calculate sum of squares of distances between every two vertices. How to do this fast? (programming task)
0
votes
0answers
24 views

Upper and lower bounds on probability in binomial distribution.

Suppose i have a random variable $X \sim \mathrm{Bin}(n,p)$ and some $1 \leq l \leq n$ can i obtain good upper and lower bounds on the probability that $$\mathbb{P}(X \geq l)?$$ After some research I ...
3
votes
1answer
41 views

How many ways 5 different books be distributed among 5 students

I've seen this question in a book and can't figure it out correctly. Let 5 different books be distributed among 5 students. Suppose the books are returned and distributed to the students again ...
0
votes
1answer
27 views

(combinatorics) 2 problems using signless Stirling number of the first kind

For every subset of [n-1], take the products of all its elements (empty products being taken to be 1) and then,sum of all 2^(n-1) products. What is this value? 2.For every k-element subsets of ...
4
votes
1answer
47 views

Probability of picking at least one of each of $x$ items in $y$ tries from possible $z$ options

As stated in title, there are $z$ things to pick from, and you get $y$ picks, with replacement. What's the probability of picking such that you get at least one of each of $x$ things? Assume $x \leq ...
5
votes
4answers
220 views

(combinatorics) prove that on average, n-permutations have Hn cycles without mathematical induction.

Prove that on average, n-permutations have $H_n$ cycles, where $H_n=1+1/2+1/3+...+1/n$ without mathematical induction. I think that on average, the number of cycles of length i (1≤i≤n) should be ...
2
votes
1answer
22 views

probability of choosing an object at least once in $3$ drawings

So there are $4$ objects in total, and I want to know the probability of choosing object A at least once in $3$ drawings. What I did was add $3C1 + 3C2 + 3C3$ and got $7$ and, as a final answer, I ...
-2
votes
1answer
36 views

Expressing $\frac {x^n}{(1-x)^n}$ as a generating function [closed]

How did they get the following: $$\frac {x^n}{(1-x)^n} = \sum\limits_{m}{m-1 \choose n-1}{x^m}$$
1
vote
1answer
26 views

The fundamental counting principle in reverse

How many natural odd numbers are between $100$ and $999$ that have all different digits? There are two conditions in this question: $(1)$the number must be odd and $(2)$must have all different ...
0
votes
1answer
22 views

number of possible strings of length 4 with exactly 1 digit repeated?

I am trying to find the number of string that have a length of 4 and have 1 digit repeated (ex. 7181). What i did was I found the total number of permutations and got 12, since there is a pair of ...
4
votes
0answers
51 views

What are some other examples of this phenomenon: if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets).

Finite sets have the amazing property that if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets). Said another way: finite totally-ordered sets that are ...
1
vote
1answer
39 views

Evaluate $\sum\limits_{k=m}^n (-1)^k {n \choose k} {k \choose m}$

By using generating functions and snake-oil I got to Also what is the implication of $\sum \limits_ {k<={n}}$? I am told that this is equivalent to: But I'm not sure how to do that step, ...
1
vote
1answer
20 views

How many different paths are there on a lattice that pass through a given point?

When Looking at A to C by ${4\choose 2}$ we are ordering, right-r up-u 4 times, so ordering 2 r's or 2 u's determine the other 2 moves? And same with C to B ${3\choose 2}$ ordering the 2 r's ...
0
votes
2answers
75 views

Subset Counting question

How many subsets of [20] consist of 3 odd integers and any number of even integers? This question was asked in an interview today and I wasn't able to solve it. Please help, thanks in advance
2
votes
0answers
29 views

Inviting People To A Party With Limitations

A person has 8 friends, of whom 5 will be invited to a party. (b) How many choices if 2 of the friends will only attend together? Using inclusion-exclusion there are ${8\choose 5}-{2\choose ...
2
votes
2answers
41 views

Counting Problem - Strings

What is the number of strings of four decimal digits that contain exactly one digit repeated twice? (e.g 1198) My intuition was to first place the digits that aren't repeated and then place the ...
1
vote
0answers
19 views

Total probability distribution of multiple random lotteries

My question: Imagine $d$ identical lotteries. Each individual lottery picks a cost $c_{i}$ between $0$ and $1$. Picking a costs occurs with probability distribution $f(c)$. The total cost of these ...
3
votes
1answer
26 views

Choosing People For A Committee With Limitations

From a group of 8 women and 6 men, a committee consisting of 3 men and 3 women is to be formed. How many different committees are possible if (c) 1 man and 1 woman refuse to serve together? ...
1
vote
0answers
31 views

Derangements question

Let $D_n$ be the number of derangements of $n$ objects and $P_{n,k}$ be the number of permutations of $n$ objects with exactly $k$ fixed points. Give a formula for $P_{n,k}$ in terms of $D_{n−k}$. ...
4
votes
1answer
35 views

How many strings of $\{0,1,2,3\}$ of length $n$ are there such that $0$ appears exactly once and $1$ appears an even number of times?

How many strings of length $n$ of the digits $\{0,1,2,3\}$ are there such that $0$ appears exactly once and $1$ appears an even number of times? My attempt: define $a_n$ to be a sequence of such ...
1
vote
2answers
27 views

In how many ways can a $5 \times 5$ matrix be formed such that sum of row elements and column elements are $4$ and entries are $0$ or $1$?

Let we have a $5 \times 5$ matrix and the elements can be either $0$ or $1$ and the sum of elements of each row and column is $4$ then in how many ways can the matrix be formed ? I tried doing it in ...
2
votes
3answers
131 views

Number of ways to express a number as the sum of different integers

Given a number $n$, then $P_k(n)$ is the number of ways to express $n$ as the sum of $k$ integers. For example $P_2(6)=7$ $0+6=6$ $1+5=6$ $2+4=6$ $3+3=6$ $4+2=6$ $5+1=6$ $6+0=6$ Now I worked ...
2
votes
2answers
28 views

Four Athletes run a race

Four Athletes $A,B,C$ and $D$ run in a race. They have equal abilities so that all place orderings have equal probabilities. There are no ties (i) What is the probability that the first two places ...
1
vote
1answer
54 views

Is my graph a tree?

Let M be a smooth connected manifold. G is a group act on M cocompactly and suppose there is a harmonic function $h$ on M with minimal energy.$h:\rightarrow [0,1]$ such that h is nonconstant and ...
0
votes
1answer
40 views

Game with matches. Very interesting mathematical problem.

Suppose you have a set of matches. You arrange them in 9 rows such that the first row has one match the second two matches the third three and so on until the ninth row which has nine matches. There ...
0
votes
0answers
17 views

Rectangular Grid Walk Question

I learned a trick that for rectangular fields, one can use combinations and define $u$ as up and $r$ as right. I saw that the total steps needed to get to $B$ is $4$ no matter which way you go. So I ...
1
vote
3answers
58 views

How to prove $\sum_{i=1}^{n}\binom{n}{i}p^i(1-p)^{n-i}i = np$?

How to prove, when $p\in[0, 1]$, $$\sum_{i=1}^{n}\binom{n}{i}p^i(1-p)^{n-i}i = np$$ Is there a name for this formula?
1
vote
1answer
36 views

Coloring the 6 vertices of a regular hexagon with a limited use per color

I want to solve to following two-part problem. I solved the first part but I am not sure how to start on part B. A) How many ways are there to color the 6 vertices of a regular hexagon using 4 colors ...
1
vote
0answers
31 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
0
votes
1answer
21 views

How to select four points so that origin is not contained in convex hull of these points?

I have a regular 12-gon $A_1A_2...A_{12}$ with centre $O$. How to select four points so that centre $O$ doesn't lie in and lie on quadrilateral? I tried. With diameter $A_{12}A_6$, consider ...
2
votes
1answer
40 views

Dividing $8$ Children into $4$ teams of $2$ players each

In how many ways can you divide $8$ children into $4$ teams of $2$ players each? My attempt: $$ \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}$$ $$ = 4 \times 7 \times 3 ...
7
votes
3answers
70 views

How many $n-$digit number that contain only digits $ 1,2,3,4,5,6$

How many $n- $digit numbers can be formed from the digits $1,2,3,4,5$ and 6, which contains the numbers $1$ and $2$ as neighbours. Let $p_n$ be the number of n-digit numbers which consist only of ...
2
votes
3answers
51 views

Generating function for $a_n= a_{n-1}+2a_{n-2}$+3

How do I find a generating function for $a_n= a_{n-1}+2a_{n-2}$+3 using sigma notation? with initial conditions $a_0$ =2 and $a_1$ = 2. I'm mainly confused by how to deal with the "+3" at the end. ...
1
vote
0answers
37 views

movement of knight in a game of chess

This question arose in my brain while playing a game of chess. We all know how a knight moves in a game of chess. I wanted to calculate the minimum no. of moves required by a knight to cover all the ...
0
votes
0answers
48 views

finding number of subsets such that for given $(a,b)$ $a$ is the minimum element and $b$ is maximum element in that subset

I have a set of size $n$ which is sorted in ascending order. This is the process I followed: The largest element of the set is largest in $2^{n-1}$ subsets and the second largest is largest in ...
1
vote
0answers
16 views

Approximating Number of members in a set after union

I am not sure whether it is possible to this or not, but what I am trying to do is calculate the number of members in a set union (of large size N) without actually forming the set physically. For ...
1
vote
1answer
34 views

All Combinations Of Pairs

A dance class consists of 22 students, of which 10 are women and 12 are men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? First there are 5 ...
0
votes
0answers
16 views

How to assemble rook polynomials?

I have a problem. I need to assemble a rook polynomial for the chessboard (6x6 boards). Black boards are 1, white boards are 0. ...
1
vote
1answer
40 views

Intuitive explanation for Derangement

The recurrence relation for Derangement is as follows: Let $D_n$ denote the number of derangements of a set $\{1,2,3...n\}$ $D_n=(n-1)D_{n-1}+(n-1)D_{n-2}$ Can someone give and intuitive ...