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
53 views

How many different box combinations can you get?

I have 12 books, all different. Four of them are fiction, and eight of them are non-fiction. I want to send you a gift. I'm going to send you five books - two fiction, three non-fiction. You will get ...
1
vote
1answer
254 views

How many ways can you distribute 3 types of candies to 8 children?

I have a big bag of candy. Peppermints, Chocolates, and Caramels. There are eight sweet children who deserve candy. One each, they are not that sweet. So I give each child a candy. How many ways are ...
2
votes
1answer
68 views

Signs of products of permutations with given values sums

There is a funny property of permutations, which is valid for $n=2,3,4$, but it would be interesting to know if it is a general fact. Let $\sigma_1,\sigma_2,\sigma_3$ be three permutations of numbers ...
1
vote
1answer
28 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
0
votes
3answers
46 views

Combinatorial Algebra with Variables

The problem is ${m+1} \choose {m-1}$. The answer is $\frac{m(m+1)}{2}$. I am stuck on solving this algebraically. If someone could tell me where the two comes from I would be helped, because I know ...
0
votes
2answers
466 views

To find the number of onto functions in a different way

Suppose there are two sets $A\ \&\ B$ between which to define a surjective map $f: A\to B$. Here let's say $A$ is $[n]\ \&\ B$ is $[k]$, where $[i]$ is $\{1,2,3,\ldots ,i\}$. I need to find ...
0
votes
1answer
49 views

Binomial Type sequence

If $p_0(n),p_1(n)\ldots$ is a sequence of polynomials satisfying $$\sum_{k \geq 0}p_k(n) \frac {x^k}{k!}= \left ( \sum_{ k \geq 0}p_k(1) \frac {x^k}{k!} \right )^n$$ then $$p_k(m+n)= \sum_{i=0}^{k} ...
1
vote
1answer
94 views

Permutations with repetition for some elements

Suppose we have $N$ slots, each of which can be filled with $X$ options, but $2$ of these slots can only be filled in $1$ way (out of $X$ ways), then what is the number of permutations possible ? For ...
1
vote
1answer
27 views

adjustment of Prof.,s in Round Table

In How many ways can $5$ Professors of Physics Including Prof. Hardy and $3$ Three Professors of Chemistry Including Prof. Julian be seated on a Round table, If Prof. hardy and Prof. Julian are not ...
1
vote
1answer
33 views

Given symbols $x$ and $y$, how many sequences of length $n$ are there such that the last symbol is $y$, there are at least as many $y$'s as $x$'s?

Given symbols $x$ and $y$, how many sequences of length $n$ are there such that the last symbol is $y$, there are at least as many $y$'s as $x$'s? Is there a closed formula? Any help would be ...
0
votes
3answers
159 views

Using the last 4 digits of a phone number [closed]

Using the last 4 digits of a phone number , how many times will the first three digits add up to the final digit?
0
votes
2answers
34 views

Hiding Eggs Combinatorics

How can I figure out if I have 6 red eggs, 3 blue eggs, 1 green egg, and 2 yellow eggs. Aside from their color, they are identical. I have 12 different hiding spots, each big enough for 1 egg. How ...
2
votes
1answer
232 views

Proof of summation of Stirling's Numbers of the first kind

"Stirling's number of the first kind $s(n,k)$ is the number of permutations of ${1,2,...,n}$ with $k$-cycles. Prove that $n! = \sum s(n,k)$ (from k = 1 to $\infty$) " After checking a the first few ...
2
votes
3answers
532 views

Find number no of ways to fill a grid with balls[Part 2]

Find the number of ways to fill a 3*3 grid (with corners indistinguishable) if you have 3 black and 6 white marbles. Approach till now[Incorrect]: No. of ways of arranging 3 black marbles or 6 white ...
0
votes
1answer
392 views

Number of ways to fill a grid with balls

Find the number of ways to fill a $3\times 3$ grid (with corners defined as $a,b,c,d$) if you have 3 black and 6 white marbles. Note: This question was asked in an e-litmus exam and is not an ...
2
votes
1answer
68 views

Number of permutation with non-consecutive blocks

How many strings are there consisting of exactly M A's, N B's, and K C's so that the string BC does not appear? For example, when M=3, N=1, K=1, $$ABACA$$ counts as a valid string whereas ...
1
vote
0answers
50 views

Discriminating integer partitions

Given a fixed positive integer, say $n$, letn $P_n$ be the set all partitions of $n$, where each partition itself is a set i.e. order is discarded and each part is less than 5. Can we establish a ...
0
votes
1answer
202 views

Number of ways of arranging numbers with given max difference

How many ways are the there to arrange n numbers out of m numbers (1 to m) so that the difference between the max and min numbers of those n numbers is D which is given. For example : n = 4 m = 3 ...
0
votes
2answers
635 views

Ways to select 3 members from 5 candidates

At an election there are 5 candidates and 3 members are to be selected. In how many ways a voter can vote? My attempt: 1st member can be chosen in 5 ways, 2nd in 4 and 3rd in 3. So, $5*4*3=60$. ...
0
votes
1answer
58 views

The intersections of three polygons in a square with area $=6$

Let three convex polygons with areas equal to $3$, in a square with area equals to $6$. We need to prove that there are two of them which has their intersection with area is at least $1$. I have no ...
0
votes
3answers
61 views

No of strings of 'N' letters that can be formed using 'k' symbols

No of strings of 'N' letters that can be formed using 'k' symbols(they can be repeated). 2 of the given k symbols must always be present. e.g for N=2 and k=2 Let Symbols be 'a','b' of which 'a' and ...
3
votes
1answer
75 views

Sets, Sequences, and counting

Let $A$ denote all $k$-subets of $\{1,\dots,n\}$ where $0 < k \le n$ and let $B$ denote all increasing $k$ sequences on $\{1,\dots,n\}$. Show that the number of $k$-subsets in $A$ equals the number ...
3
votes
2answers
1k views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
4
votes
4answers
2k views

Count of 3-digit numbers with at least one digit as 9

Find the number of $3$ digit numbers (repetitions allowed) such that at least one of the digit is $9.​$ I've posted my answer below. If there is a better way to solve this question, I would be ...
1
vote
3answers
358 views

Ranking athletes by nationality

In an international track competition, there are five United States athletes, four Russian athletes, three French athletes, and one German athlete. How many rankings of the 13 athletes are there when ...
0
votes
1answer
159 views

Number of ways to arrange a set of numbers

I have two numbers say $a$ and $b$. There are $n$ slots. Given numbers $[a, b]$ i.e. all numbers between $a$ and $b$ (inclusive). In how mane ways can I arrange or place these ($b - a + 1$) numbers in ...
0
votes
1answer
861 views

Pick 9 balls from piles of different balls

How many ways are there to pick nine balls from large piles of (identical) red, white, and blue balls plus one pink ball, one lavender ball, and one tan ball? What is correct answer? Is it ...
2
votes
1answer
156 views

Non combinatorial proof of Jacobi triple product?

The jacobi triple product identity in the form given below - $$\prod_{n\geq 1}(1-q^n) (1-xq^{n-1}) (1-\frac{1}{x}q^n) = \sum_{k\geq 0} (-x)^k q^{k \choose 2}$$ can be proved as follows, Let the LHS ...
1
vote
0answers
57 views

Question about the combinations of an alphabet with a fixed number of positions

Let $\{A_i\}_{i=1}^n, \{B_i\}_{i=1}^m$ be two finite collections. If I select $k$ elements from $\{A_i\}$ from the first collection without replacement, and $k$ elements in $\{B_i\}$ with replacement, ...
2
votes
1answer
232 views

Tennis balls counting problem

On a Friday morning, the pro shop of a tennis club has 14 identical cans of tennis balls. If they are all sold by Sunday night and we are interested only in how many were sold in each day, in how many ...
2
votes
0answers
155 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
0
votes
3answers
702 views

Number of ways $n$ distinct objects can be put into two identical boxes

The number of ways in $n$ distinct objects can be put into two identical boxes, so that neither box remains empty. My Try:: If the question is the numbers of ways in $n$ distinct objects can be put ...
0
votes
1answer
37 views

Permutations with some fixed numbers

You have to fill 4 spaces with 3 numbers (4, 5, 6) such that the numbers 4 and 6 appear atleast once in every case. Find the number of such unique permutations. [Ans. 50] How do you go about solving ...
3
votes
0answers
44 views

Combinatorial proof of $\sum\limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} =4^n$ [duplicate]

$$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$$ Is there a combinatorial proof of above identity, without any arithmetic transformation? Thanks...
2
votes
2answers
76 views

Minimisation of a distance sum

I have a list $L$ of $N$ numbers, and I want to choose $k$ numbers $\{x_1,x_2, \ldots,x_k\} \subseteq L$ in such a way value $S$ of the those K numbers is minimum. $$ S = \sum_{0< i < j <= k} ...
1
vote
3answers
860 views

Integral points on a circle

Given radius $r$ which is an integer and center $(0,0)$, find the number of integral points on the circumference of the circle.
0
votes
1answer
134 views

inclusion exclusion principle basic question

Hello I have found a question about exclusion principle and I have love that you will help me with that question. Prove that for each 201 number from[1,300] we can find that there is always two ...
0
votes
1answer
2k views

A box contains 5 blue and 4 red balls. (probability problem)

A box contains 5 blue and 4 red balls. Two balls are drawn successively from the box without replacement, and it is noted that the second one is red. What is the probability that the ...
0
votes
1answer
51 views

ways to fill n places with fixed values in a given range and avoid diplicates formed.

what are the number of ways in which we can fill n places with 2 fixed values and rest places with values between the 2 selected ones such that we get no duplicates? example : n=4 , fixed values 1 ...
0
votes
3answers
1k views

Rolling 6 dice and 4 on the same side

Guys I made myself a question to answer and its this. What is the probability of having 4 dice land on the same side if I toss 6 dice. I got this answer, I don't know if its correct. I dont want to ...
2
votes
1answer
100 views

Normalizing a matrix with row and column swapping

How do you canonicalize a matrix over column- and row-swap operations? Or more specifically, does there exist a function f(M) such that ...
3
votes
2answers
265 views

How many ways are there to distribute 8 teachers to 4 schools where each school must get at least 1 teacher?

Additional details: the teachers are considered distinct from one another. So here is what I thought: 1) Choose four teachers to go to each one of the schools: $\binom{8}{4}\cdot4!$ 2) For each of ...
0
votes
1answer
74 views

$n$ points on a circle

Choose $n$ points on a circle so that no three of the $\binom{n}{2}$ chords have a common point inside the circle. Let $a_{n}$ be the number of regions formed inside the circle by drawing the cords. ...
0
votes
1answer
51 views

A question about a sequence.

I'm preparing for the subject exam in November. This is a question that I thought I had the correct answer to. Let $\left \{a_n \right \}_{n=1}^\infty$ be defined recursively by $a_1=1$ and ...
0
votes
1answer
54 views

Number of linear extensions of $\mathbb{P}([n])$ partially ordered by inclusion

A linear extension of $\mathbb{P}([n])$, i.e. all subsets of $\{1,2,\ldots,n\}$ is a total ordering of all the subsets where $A < B$ in the ordering if $A \subset B$. If $n=2$ the number of linear ...
0
votes
2answers
110 views

Counting the number of integer sequences

Count the number of sequences of integers, a(1), a(2), .... a(n), containing n positive integers such that...
1
vote
1answer
218 views

Combinatorics and Linear Extensions

I’m considering the partially ordered set (X, ⊆) of subsets of the set X={a,b,c} of three elements. How many linear extensions are there? I know that the subsets are: ∅, ...
2
votes
3answers
956 views

Solving a recurrence relation with the characteristic polynomial

Consider the sequence $\{a_n\}_{n=0}^\infty$ with $a_0 = 0, a_1 = 1, a_{n+2} = 6a_{n+1} - 9a_{n}$. Using the characteristic polynomial prove $a_{n} = n3^{n-1}$. So I really wasn't sure where to ...
3
votes
1answer
1k views

What is the formula for combinations with identical elements?

Given a set of $n$ objects that has $p_1$ identical objects of one kind, $p_2$ identical objects of another kind, and so on until $p_n$ objects of the $n$th kind, in how many ways can one select $r$ ...
5
votes
2answers
692 views

Using Exponential Generating Functions on Counting Problems

Is it possible to use exponential generating functions to solve problems where repetition is wanted? For example, if I wanted to solve the following problem which wants distinct possibilities... ...